2025/10/16 by An, Shinwoo, Im, Seonghyuk, Kim, Seokbeom +1
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.14674
Given a family F of graphs, a graph is \emphF-subgraph-free if it has no subgraph isomorphic to a member of F. We present a fixed-parameter linear-time algorithm that decides whether a planar graph can be made F-subgraph-free by deleting at most k vertices or k edges, where the parameters are k, | F |, and the maximum number of vertices in a member of F. The running time of our algorithm is double-exponential in the parameters, which is faster than the algorithm obtained by applying the first-order model checking result for graphs of bounded twin-width. To obtain this result, we develop a unified framework for designing algorithms for this problem on graphs with a ``product structure.'' Using this framework, we also design algorithms for other graph classes that generalize planar graphs. Specifically, the problem admits a fixed-parameter linear time algorithm on disk graphs of bounded local radius, and a fixed-parameter almost-linear time algorithm on graphs of bounded genus. Finally, we show that our result gives a tight fixed-parameter algorithm in the following sense: Even when F consists of a single graph F and the input is restricted to planar graphs, it is unlikely to drop any parameters k and | V(F) | while preserving fixed-parameter tractability, unless the Exponential-Time Hypothesis fails.