{"ID":2854646,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.14674","arxiv_id":"2510.14674","title":"An efficient algorithm for $\\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure","abstract":"Given a family $\\mathcal{F}$ of graphs, a graph is \\emph{$\\mathcal{F}$-subgraph-free} if it has no subgraph isomorphic to a member of $\\mathcal{F}$. We present a fixed-parameter linear-time algorithm that decides whether a planar graph can be made $\\mathcal{F}$-subgraph-free by deleting at most $k$ vertices or $k$ edges, where the parameters are $k$, $\\lvert \\mathcal{F} \\rvert$, and the maximum number of vertices in a member of $\\mathcal{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 $\\mathcal{F}$ consists of a single graph $F$ and the input is restricted to planar graphs, it is unlikely to drop any parameters $k$ and $\\lvert V(F) \\rvert$ while preserving fixed-parameter tractability, unless the Exponential-Time Hypothesis fails.","short_abstract":"Given a family $\\mathcal{F}$ of graphs, a graph is \\emph{$\\mathcal{F}$-subgraph-free} if it has no subgraph isomorphic to a member of $\\mathcal{F}$. We present a fixed-parameter linear-time algorithm that decides whether a planar graph can be made $\\mathcal{F}$-subgraph-free by deleting at most $k$ vertices or $k$ edge...","url_abs":"https://arxiv.org/abs/2510.14674","url_pdf":"https://arxiv.org/pdf/2510.14674v2","authors":"[\"Shinwoo An\",\"Seonghyuk Im\",\"Seokbeom Kim\",\"Myounghwan Lee\"]","published":"2025-10-16T13:30:41Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}