The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.

We revisit the k -Secluded Tree problem. Given a vertex-weighted undirected graph G , its objective is to find a maximum-weight induced subtree T whose open neighborhood has size at most k . We present a fixed-parameter tractable algorithm that solves the problem in time 2 O ( k log ⁡ k ) ⋅ n O ( 1 ) , improving on a double-exponential running time from earlier work by Golovach, Heggernes, Lima, and Montealegre. Starting from a single vertex, our algorithm grows a k -secluded tree by branching on vertices in the open neighborhood of the current tree T . To bound the branching depth, we prove a structural result that can be used to identify a vertex that belongs to the neighborhood of any k -secluded supertree T ′ ⊇ T once the open neighborhood of T becomes sufficiently large. We extend the algorithm to enumerate compact descriptions of all maximum-weight k -secluded trees, which allows us to count them as well.

Abstract We revisit the k-Secluded Tree problem. Given a vertex-weighted undirected graph G, its objective is to find a maximum-weight induced subtree T whose open neighborhood has size at most k. We present a fixed-parameter tractable algorithm that solves the problem in time $$2^{\mathcal {O} (k \log k)}\cdot n^{\mathcal {O} (1)}$$ , improving on a double-exponential running time from earlier work by Golovach, Heggernes, Lima, and Montealegre. Starting from a single vertex, our algorithm grows a k-secluded tree by branching on vertices in the open neighborhood of the current tree T. To bound the branching depth, we prove a structural result that can be used to identify a vertex that belongs to the neighborhood of any k-secluded supertree $$T' \supseteq T$$ once the open neighborhood of T becomes sufficiently large. We extend the algorithm to enumerate compact descriptions of all maximum-weight k-secluded trees, which allows us to count the number of such trees containing a specified vertex in the same running time.

Abstract In the $${\varvec{\mathcal {F}}}$$ F - Minor - Free Deletion problem one is given an undirected graph $${\varvec{G}}$$ G , an integer $${\varvec{k}}$$ k , and the task is to determine whether there exists a vertex set $${\varvec{S}}$$ S of size at most $${\varvec{k}}$$ k , so that $${\varvec{G}}-{\varvec{S}}$$ G - S contains no graph from the finite family $${\varvec{\mathcal {F}}}$$ F as a minor. It is known that whenever $${\varvec{\mathcal {F}}}$$ F contains at least one planar graph, then $${\varvec{\mathcal {F}}}$$ F - Minor - Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size $${\varvec{k}}^{{\varvec{\mathcal {O}}}{} {\textbf {(1)}}}$$ k O ( 1 ) [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size. We study the Outerplanar Deletion problem, in which we want to remove at most $${\varvec{k}}$$ k vertices from a graph to make it outerplanar. This is a special case of $${\varvec{\mathcal {F}}}$$ F - Minor - Free Deletion for the family $${\varvec{\mathcal {F}}} = \{{\varvec{K}}_{{\textbf {4}}}, {\varvec{K}}_{{{\textbf {2,3}}}}\}$$ F = { K 4 , K 2 , 3 } . The class of outerplanar graphs is arguably the simplest class of graphs

For a fixed finite family of graphs F, the F-Minor-Free Deletion problem takes as input a graph G and integer ℓ and asks whether a size-ℓ vertex set X exists such that G−X is F-minor-free. {K2}-Minor-Free Deletion and {K3}-Minor-Free Deletion encode Vertex Cover and Feedback Vertex Set respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. We show {P3}-Minor-Free Deletion parameterized by the feedback vertex number is MK[2]-hard. This rules out the existence of a polynomial kernel assuming NP⊈coNP/poly. Our hardness result generalizes to any F containing only graphs with a connected component of at least 3 vertices, using as parameter the vertex-deletion distance to treewidth min⁡tw(F), where min⁡tw(F) denotes the minimum treewidth of the graphs in F. For all other families F we present a polynomial Turing kernelization. Our results extend to F-Subgraph-Free Deletion.