Eindhoven University of Technology, The
<EMAIL_ADDRESS>University of
Technology, The<EMAIL_ADDRESS>project
has received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No 803421, ReduceSearch). Huib Donkers and Bart M. P.
Jansen[100]Theory of computation Graph algorithms analysis [100]Theory of
computation Parameterized complexity and exact algorithms An extended abstract
of this work appeared in the Proceedings of the 47th Workshop on Graph-
Theoretical Concepts in Computer Science, WG 2021John Q. Open and Joan R.
Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT
2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Preprocessing to Reduce the Search Space: Antler Structures for Feedback
Vertex Set

Huib Donkers  Bart M. P. Jansen

###### Abstract

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.

###### keywords:

kernelization, preprocessing, feedback vertex set, graph decomposition

###### category:

##  1 Introduction

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 [25, 30]. In a nutshell, this new direction can be
summarized as: how can an algorithm identify part of an optimal solution in an
efficient preprocessing phase? We explore this direction for the classic [37]
Feedback Vertex Set problem on undirected graphs, leading to a new graph
structure called _antler_ which reveals vertices that belong to an optimal
feedback vertex set.

We start by motivating the need for a new direction in the theoretical
analysis of preprocessing. The use of preprocessing, often via the repeated
application of reduction rules, has long been known [3, 4, 43] to speed up the
solution of algorithmic tasks in practice. The introduction of the framework
of parameterized complexity [20] in the 1990s made it possible to also analyze
the power of preprocessing _theoretically_ , through the notion of
kernelization. It applies to _parameterized decision problems_
$\Pi\subseteq\Sigma^{*}\times\mathbb{N}$, in which every instance
$x\in\Sigma^{*}$ has an associated integer parameter $k$ which captures one
dimension of its complexity. For Feedback Vertex Set, typical choices for the
parameter include the size of the desired solution or structural measures of
the complexity of the input graph. A kernelization for a parameterized problem
$\Pi$ is then a polynomial-time algorithm that reduces any instance with
parameter value $k$ to an equivalent instance, of the same problem, whose
total size is bounded by $f(k)$ for some computable function $f$ of the
parameter alone. The function $f$ is the _size_ of the kernelization.

A substantial theoretical framework has been built around the definition of
kernelization [16, 21, 26, 28, 30]. It includes deep techniques for obtaining
kernelization algorithms [10, 27, 38, 42], as well as tools for ruling out the
existence of small kernelizations [11, 18, 22, 29, 31] under complexity-
theoretic hypotheses. This body of work gives a good theoretical understanding
of polynomial-time data compression for NP-hard problems.

However, we argue that these results on kernelization _do not_ explain the
often exponential speed-ups (e.g. [3], [5, Table 6]) caused by applying
effective preprocessing steps to non-trivial algorithms. Why not? A
kernelization algorithm guarantees that the input _size_ is reduced to a
function of the parameter $k$; but the running time of modern parameterized
algorithms for NP-hard problems is not exponential in the total input size.
Instead, fixed-parameter tractable (FPT) algorithms have a running time that
scales polynomially with the input size, and which only depends exponentially
on a problem parameter such as the solution size or treewidth. Hence an
exponential speed-up of such algorithms cannot be explained by merely a
decrease in input size, but only by a decrease in the _parameter_!

We therefore propose the following novel research direction: to investigate
how preprocessing algorithms can decrease the parameter value (and hence
search space) of FPT algorithms, in a theoretically sound way. It is
nontrivial to phrase meaningful formal questions in this direction. To
illustrate this difficulty, note that strengthening the definition of
kernelization to “a preprocessing algorithm that is guaranteed to always
output an equivalent instance of the same problem with a strictly smaller
parameter” is useless. Under minor technical assumptions, such an algorithm
would allow the problem to be solved in polynomial time by repeatedly reducing
the parameter, and solving the problem using an FPT or XP algorithm once the
parameter value becomes constant. Hence NP-hard problems do not admit such
parameter-decreasing algorithms. To formalize a meaningful line of inquiry, we
take our inspiration from the Vertex Cover problem, the fruit fly of
parameterized algorithms.

A rich body of theoretical and applied algorithmic research has been devoted
to the exact solution of the Vertex Cover problem [5, 23, 32, 33]. A standard
2-way branching algorithm can test whether a graph $G$ has a vertex cover of
size $k$ in time $\mathcal{O}(2^{k}(n+m))$, which can be improved by more
sophisticated techniques [14]. The running time of the algorithm scales
linearly with the input size, and exponentially with the size $k$ of the
desired solution. This running time suggests that to speed up the algorithm by
a factor $1000$, one either has to decrease the input size by a factor $1000$,
or decrease $k$ by $\log_{2}(1000)\approx 10$.

It turns out that state-of-the-art preprocessing strategies for Vertex Cover
indeed often _succeed_ in decreasing the size of the solution that the follow-
up algorithm has to find, by means of crown-reduction [2, 15, 24], or the
intimately related Nemhauser-Trotter reduction based on the linear-programming
relaxation [41]. Recall that a vertex cover in a graph $G$ is a set
$S\subseteq V(G)$ such that each edge has at least one endpoint in $S$.
Observe that if $H\subseteq V(G)$ is a set of vertices with the property that
there exists a minimum vertex cover of $G$ containing all of $H$, then $G$ has
a vertex cover of size $k$ if and only if $G-H$ has a vertex cover of size
$k-|H|$. Therefore, if a preprocessing algorithm can identify a set of
vertices $H$ which are guaranteed to belong to an optimal solution, then it
can effectively reduce the parameter of the problem by restricting to a search
for a solution of size $k-|H|$ in $G-S$.

A _crown decomposition_ (cf. [1, 15, 24], [16, §2.3], [28, §4]) of a graph $G$
serves exactly this purpose. It consists of two disjoint vertex sets
$(\mathsf{head},\mathsf{crown})$, such that $\mathsf{crown}$ is a non-empty
independent set whose neighborhood is contained in $\mathsf{head}$, and such
that the graph $G[\mathsf{head}\cup\mathsf{crown}]$ has a matching $M$ of size
$|\mathsf{head}|$. As $\mathsf{crown}$ is an independent set, the matching $M$
assigns to each vertex of $\mathsf{head}$ a private neighbor in
$\mathsf{crown}$. It certifies that any vertex cover in $G$ contains at least
$|\mathsf{head}|$ vertices from $\mathsf{head}\cup\mathsf{crown}$, and as
$\mathsf{crown}$ is an independent set with
$N_{G}(\mathsf{crown})\subseteq\mathsf{head}$, a simple exchange argument
shows there is indeed an optimal vertex cover in $G$ containing all of
$\mathsf{head}$ and none of $\mathsf{crown}$. Since there is a polynomial-time
algorithm to find a crown decomposition if one exists [2, Thm. 11–12], this
yields the following preprocessing guarantee for Vertex Cover: if the input
instance $(G,k)$ has a crown decomposition $(\mathsf{head},\mathsf{crown})$,
then a polynomial-time algorithm can reduce the problem to an equivalent one
with parameter at most $k-|\mathsf{head}|$, thereby giving a formal guarantee
on reduction in the parameter based on the structure of the input.111The
effect of the crown reduction rule can also be theoretically explained by the
fact that interleaving basic 2-way branching with exhaustive crown reduction
yields an algorithm whose running time is only exponential in the _gap_
between the size of a minimum vertex cover and the cost of an optimal solution
to its linear-programming relaxation [39]. However, this type of result cannot
be generalized to Feedback Vertex Set since it is already NP-complete to
determine whether there is a feedback vertex set whose size matches the cost
of the linear-programming relaxation (Corollary A.6).

As the first step of our proposed research program into parameter reduction
(and thereby, search space reduction) by a preprocessing phase, we present a
graph decomposition for Feedback Vertex Set which can identify vertices $S$
that belong to an optimal solution; and which therefore facilitate a reduction
from finding a solution of size $k$ in graph $G$, to finding a solution of
size $k-|S|$ in $G-S$. While there has been a significant amount of work on
kernelization for Feedback Vertex Set [12, 13, 34, 36, 45], the corresponding
preprocessing algorithms do not succeed in finding vertices that belong to an
optimal solution, other than those for which there is a self-loop or those
which form the center a flower (consisting of $k+1$ otherwise vertex-disjoint
cycles [12, 13, 45], or a technical relaxation of this notion [34]). In
particular, apart from the trivial self-loop rule, earlier preprocessing
algorithms can only conclude a vertex $v$ belongs to all optimal solutions (of
a size $k$ which must be given in advance) if they find a suitable packing of
cycles witnessing that solutions without $v$ must have size larger than $k$.
In contrast, our argumentation will be based on _local_ exchange arguments,
which can be applied independently of the global solution size $k$.

We therefore introduce a new graph decomposition for preprocessing Feedback
Vertex Set. To motivate it, we distill the essential features of a crown
decomposition. Effectively, a crown decomposition of $G$ certifies that $G$
has a minimum vertex cover containing all of $\mathsf{head}$, because (i) any
vertex cover has to pick at least $|\mathsf{head}|$ vertices from
$\mathsf{head}\cup\mathsf{crown}$, as the matching $M$ certifies that
$\mathrm{\textsc{vc}}(G[\mathsf{head}\cup\mathsf{crown}])\geq|\mathsf{head}|$,
while (ii) any minimum vertex cover $S^{\prime}$ in
$G-(\mathsf{head}\cup\mathsf{crown})$ yields a minimum vertex cover
$S^{\prime}\cup\mathsf{head}$ in $G$, since
$N_{G}(\mathsf{crown})\subseteq\mathsf{head}$ and $\mathsf{crown}$ is an
independent set. To obtain similar guarantees for Feedback Vertex Set, we need
a decomposition to supply disjoint vertex sets
$(\mathsf{head},\mathsf{antler})$ such that (i) any minimum feedback vertex
set contains at least $|\mathsf{head}|$ vertices from
$\mathsf{head}\cup\mathsf{antler}$, and (ii) any minimum feedback vertex set
$S^{\prime}$ in $G-(\mathsf{head}\cup\mathsf{antler})$ yields a minimum
feedback vertex set $S^{\prime}\cup\mathsf{head}$ in $G$. To achieve (i), it
suffices for $G[\mathsf{head}\cup\mathsf{antler}]$ to contain a set of
$|\mathsf{head}|$ vertex-disjoint cycles (implying that each cycle contains
exactly one vertex of $\mathsf{head}$); to achieve (ii), it suffices for
$G[\mathsf{antler}]$ to be acyclic, with each tree $T$ of the forest
$G[\mathsf{antler}]$ connected to the remainder
$V(G)\setminus(\mathsf{head}\cup\mathsf{antler})$ by at most one edge
(implying that all cycles through $\mathsf{antler}$ intersect
$\mathsf{head}$). We call such a decomposition a 1-antler. Here _antler_
refers to the shape of the forest $G[\mathsf{antler}]$, which no longer
consists of isolated spikes of a crown (see Figure 1). The prefix $1$
indicates it is the simplest type of antler; we present a generalization
later. An antler is _non-empty_ if
$\mathsf{head}\cup\mathsf{crown}\neq\emptyset$, and the _width_ of the antler
is defined to be $|\mathsf{head}|$.

Figure 1: Graph structures showing there is an optimal solution containing all
black vertices and no gray vertices, certified by the bold subgraph. Left:
Crown decomposition for Vertex Cover. Right: Antler for Feedback Vertex Set.
For legibility, the number of edges in the drawing has been restricted. It
therefore has degree-2 vertices which make it reducible by standard reduction
rules; but adding all possible edges between gray and black vertices leads to
a structure of minimum degree at least three which is still a 1-antler.

Unfortunately, assuming $\mathsf{P}$ $\neq$ $\mathsf{NP}$ there is no
_polynomial-time_ algorithm that always outputs a non-empty 1-antler if one
exists. We prove this in Appendix A. However, for the purpose of making a
preprocessing algorithm that reduces the search space, we can allow FPT time
in a parameter such as $|\mathsf{head}|$ to find a decomposition. Each fixed
choice of $|\mathsf{head}|$ would then correspond to a reduction rule which
identifies a small ($|\mathsf{head}|$-sized) part of an optimal feedback
vertex set, for which there is a simple certificate for it being part of an
optimal solution. Such a reduction rule can then be iterated in the
preprocessing phase, thereby potentially decreasing the target solution size
(and search space) by an arbitrarily large amount. Hence we consider the
parameterized complexity of testing whether a graph admits a non-empty
1-antler with $|\mathsf{head}|\leq k$, parameterized by $k$. On the one hand,
we show this problem to be W[1]-hard in Appendix B. This hardness turns out to
be a technicality based on the forced bound on $|\mathsf{head}|$, though. We
provide the following FPT algorithm which yields a search-space reducing
preprocessing step.

######  Theorem 1.1.

There is an algorithm that runs in $2^{\mathcal{O}(k^{5})}\cdot
n^{\mathcal{O}(1)}$ time that, given an undirected multigraph $G$ on $n$
vertices and integer $k$, either correctly determines that $G$ does not admit
a non-empty 1-antler of width at most $k$, or outputs a set $S$ of at least
$k$ vertices such that there exists an optimal feedback vertex set in $G$
containing all vertices of $S$.

Hence if the input graph admits a non-empty 1-antler of width at most $k$, the
algorithm is guaranteed to find at least $k$ vertices that belong to an
optimal feedback vertex set, thereby reducing the search space.

Based on this positive result, we go further and generalize our approach
beyond 1-antlers. For a 1-antler $(\mathsf{head},\mathsf{antler})$ in $G$, the
set of $|\mathsf{head}|$ vertex-disjoint cycles in
$G[\mathsf{head}\cup\mathsf{antler}]$ forms a very simple certificate that any
feedback vertex set of $G$ contains at least $|\mathsf{head}|$ vertices from
$\mathsf{head}\cup\mathsf{antler}$. We can generalize our approach to identify
part of an optimal solution, by allowing more complex certificates of
optimality. The following interpretation of a 1-antler is the basis of the
generalization: for a 1-antler $(\mathsf{head},\mathsf{antler})$ in $G$, there
is a subgraph $G^{\prime}$ of $G[\mathsf{head}\cup\mathsf{antler}]$ (formed by
the $|\mathsf{head}|$ vertex-disjoint cycles) such that
$V(G^{\prime})\supseteq\mathsf{head}$ and $\mathsf{head}$ is an optimal
feedback vertex set of $G^{\prime}$; and furthermore this subgraph
$G^{\prime}$ is simple because all its connected components, being cycles,
have a feedback vertex set of size $1$. For an arbitrary integer $z$, we
therefore define a $z$-antler in an undirected multigraph graph $G$ as a pair
of disjoint vertex sets $(\mathsf{head},\mathsf{antler})$ such that (i) any
minimum feedback vertex set in $G$ contains at least $|\mathsf{head}|$
vertices from $\mathsf{head}\cup\mathsf{antler}$, as witnessed by the fact
that $G[\mathsf{head}\cup\mathsf{antler}]$ has a subgraph $G^{\prime}$ for
which $\mathsf{head}$ is an optimal feedback vertex set and with each
component of $G^{\prime}$ having a feedback vertex set of size at most $z$;
and (ii) the graph $G[\mathsf{antler}]$ is acyclic, with each tree $T$ of the
forest $G[\mathsf{antler}]$ connected to the remainder
$V(G)\setminus(\mathsf{head}\cup\mathsf{antler})$ by at most one edge. (So
condition (ii) is not changed compared to a 1-antler.) Our main result is the
following.

######  Theorem 1.2.

There is an algorithm that runs in $2^{\mathcal{O}(k^{5}z^{2})}\cdot
n^{\mathcal{O}(z)}$ time that, given an undirected multigraph $G$ on $n$
vertices and integers $k\geq z\geq 0$, either correctly determines that $G$
does not admit a non-empty $z$-antler of width at most $k$, or outputs a set
$S$ of at least $k$ vertices such that there exists an optimal feedback vertex
set in $G$ containing all vertices of $S$.

In fact, we prove a slightly stronger statement. If a graph $G$ can be reduced
to a graph $G^{\prime}$ by iteratively removing $z$-antlers, each of width at
most $k$, and the sum of the widths of this sequence of antlers is $t$, then
we can find in time $f(k,z)\cdot n^{\mathcal{O}(z)}$ a subset of at least $t$
vertices of $G$ that belong to an optimal feedback vertex set. This implies
that if a complete solution to Feedback Vertex Set can be assembled by
iteratively combining $\mathcal{O}(1)$-antlers of width at most $k$, then the
entire solution can be found in time $f^{\prime}(k)\cdot n^{\mathcal{O}(1)}$.
Hence our work uncovers a new parameterization in terms of the complexity of
the solution structure, rather than its size, in which Feedback Vertex Set is
fixed-parameter tractable.

Our algorithmic results are based on a combination of graph reduction and
color coding. We use reduction steps inspired by the kernelization algorithms
[12, 45] for Feedback Vertex Set to bound the size of $\mathsf{antler}$ in the
size of $\mathsf{head}$. After such reduction steps, we use color coding [6]
to help identify antler structures. A significant amount of effort goes into
proving that the reduction steps preserve antler structures and the optimal
solution size.

##  2 Preliminaries

For any family of sets $X_{1},\ldots,X_{\ell}$ indexed by
$\\{1,\ldots,\ell\\}$ we define for all $1\leq i\leq\ell$ the following
$X_{<i}:=\bigcup_{1\leq j<i}X_{j}$, $X_{>i}:=\bigcup_{i<j\leq\ell}X_{j}$,
$X_{\leq i}:=X_{i}\cup X_{<i}$ and $X_{\geq i}:=X_{i}\cup X_{>i}$. For a
function $f\colon A\to B$, let $f^{-1}\colon B\to 2^{A}$ denote the _preimage
function of $f$_, that is $f^{-1}(a)=\\{b\in B\mid f(b)=a\\}$. For some set
$D$ of size $n$ and integer $k$ with $n\geq k$ an  _$(n,k)$ -universal set for
$D$_ is a family $\mathcal{U}$ of subsets of $D$ such that for all $S\subseteq
D$ of size at most $k$ we have $\\{S\cap U\mid U\in\mathcal{U}\\}=2^{S}$.

######  Theorem 2.1 ([40, Thm. 6], cf. [16, Thm. 5.20]).

For any set $D$ and integers $n$ and $k$ with $|D|=n\geq k$, an
$(n,k)$-universal set $\mathcal{U}$ for $D$ with
$|\mathcal{U}|=2^{\mathcal{O}(k)}\log n$ can be created in
$2^{\mathcal{O}(k)}n\log n$ time.

All graphs considered in this paper are undirected multigraphs, which may have
loops. Based on the incidence representation of multigraphs (cf. [26, Example
4.9]) we represent a multigraph $G$ by a vertex set $V(G)$, an edge set
$E(G)$, and a function $\iota\colon E(G)\to 2^{V(G)}$ where $\iota(e)$ is the
set of one or two vertices incident to $e$ for all $e\in E(G)$. In the context
of an algorithm with input graph $G$ we use $n=|V(G)|$ and $m=|E(G)|$. We
assume we can retrieve and update number of edges between two vertices in
constant time, hence we can ensure in $\mathcal{O}(n^{2})$ time that there are
at most two edges between any to vertices, meaning $m\in\mathcal{O}(n^{2})$.
For a vertex set $X\subseteq V(G)$ let $G[X]$ denote the subgraph of $G$
induced by $X$. For a set of vertices and edges $Y\subseteq V(G)\cup E(G)$ let
$G-Y$ denote the graph obtained from $G[V(G)\setminus Y]$ by removing all
edges in $Y$. For a singleton set $\\{v\\}$ we write $G-v$ instead of
$G-\\{v\\}$. For two graphs $G$ and $H$ the graph $G\cap H$ is the graph on
vertex set $V(G)\cap V(H)$ and edge set $E(G)\cap E(H)$. For $v\in V(G)$ the
open neighborhood of $v$ in $G$ is $N_{G}(v):=\\{u\in V(G)\mid\exists e\in
E(G)\colon\\{u,v\\}=\iota(e)\\}$. For $X\subseteq V(G)$ let
$N_{G}(X):=\bigcup_{v\in X}N_{G}(v)\setminus X$. The degree $\deg_{G}(v)$ of a
vertex $v$ in $G$ is the number of edge-endpoints incident to $v$, where a
self-loop contributes two endpoints. For two disjoint vertex sets
$X,Y\subseteq V(G)$ the number of edges in $G$ with one endpoint in $X$ and
another in $Y$ is denoted by $e(X,Y)$. To simplify the presentation, in
expressions involving $N_{G}(..)$ and $e(..,..)$ we sometimes use a subgraph
$H$ as argument as a shorthand for the vertex set $V(H)$ that is formally
needed. For a vertex $v\in V(G)$ and an integer $k$, a _$v$ -flower of order
$k$_ is a collection of $k$ cycles in $G$ whose vertex sets only intersect in
$v$.

######  Lemma 2.2 (Cf. [L]emma 3.9).

RaymondT17] If $v$ is a vertex in an undirected multigraph $G$ such that $v$
does not have a self-loop and $G-v$ is acyclic, then we can find in
$\mathcal{O}(n)$ time a set $X\subseteq V(G)\setminus\\{v\\}$ such that $G-X$
is acyclic and $G$ contains a $v$-flower of order $|X|$.

######  Proof 2.3.

We prove the existence of such a set $X$ and $v$-flower by induction on
$|V(G)|$. The inductive proof can easily be translated into a linear-time
algorithm. If $G$ is acyclic, output $X=\emptyset$ and a $v$-flower of order
$0$. Otherwise, since $v$ does not have a self-loop there is a tree $T$ of the
forest $G-v$ such that $G[V(T)\cup\\{v\\}]$ contains a cycle. Root $T$ at an
arbitrary vertex and consider a deepest node $x$ in $T$ for which the graph
$G[V(T_{x})\cup\\{v\\}]$ contains a cycle $C$. Then any feedback vertex set of
$G$ that does not contain $v$, has to contain at least one vertex of $T_{x}$;
and the choice of $x$ as a deepest vertex implies that $x$ lies on all cycles
of $G$ that intersect $T_{x}$. By induction on $G^{\prime}:=G-V(T_{x})$ and
$v$, there is a feedback vertex set $X^{\prime}\subseteq
V(G^{\prime})\setminus\\{v\\}$ of $G^{\prime}$ and a $v$-flower in
$G^{\prime}$ of order $|X^{\prime}|$. We obtain a $v$-flower of order
$|X^{\prime}|+1$ in $G$ by adding $C$, while
$X:=X^{\prime}\cup\\{x\\}\subseteq V(G)\setminus\\{v\\}$ is a feedback vertex
set of size $|X^{\prime}|+1$.

##  3 Feedback Vertex Cuts and Antlers

In this section we present properties of antlers and related structures. A
Feedback Vertex Set (FVS) in a graph $G$ is a vertex set $X\subseteq V(G)$
such that $G-S$ is acyclic. The feedback vertex number of a graph $G$, denoted
by $\operatorname{\textsc{fvs}}(G)$, is the minimum size of a FVS in $G$. A
_Feedback Vertex Cut_ (FVC) in a graph $G$ is a pair of disjoint vertex sets
$(C,F)$ such that $C,F\subseteq V(G)$, $G[F]$ is a forest, and for each tree
$T$ in $G[F]$ we have $e(T,G-(C\cup F))\leq 1$. The _width_ of a FVC $(C,F)$
is $|C|$, and $(C,F)$ is _empty_ if $|C\cup F|=0$.

######  Observation 3.1.

If $(C,F)$ is a FVC in $G$ then any cycle in $G$ containing a vertex from $F$
also contains a vertex from $C$. The set $C$ is a FVS in $G[C\cup F]$, hence
$|C|\geq\operatorname{\textsc{fvs}}(G[C\cup F])$.

######  Observation 3.2.

If $(C,F)$ is a FVC in $G$ then for any $X\subseteq V(G)$ we have that
$(C\setminus X,F\setminus X)$ is a FVC in $G-X$. Additionally, for any
$Y\subseteq E(G)$ we have that $(C,F)$ is a FVC in $G-Y$.

We now present one of the main concepts for this work. An _antler_ in a graph
$G$ is a FVC $(C,F)$ in $G$ such that
$|C|\leq\operatorname{\textsc{fvs}}(G[C\cup F])$. Then by 3.1 the set $C$ is a
minimum FVS in $G[C\cup F]$ and no cycle in $G-C$ contains a vertex from $F$.
We observe:

######  Observation 3.3.

If $(C,F)$ is an antler in $G$, then
$\operatorname{\textsc{fvs}}(G)=|C|+\operatorname{\textsc{fvs}}(G-(C\cup F))$.

For a graph $G$ and vertex set $C\subseteq V(G)$, a _$C$ -certificate_ is a
subgraph $H$ of $G$ such that $C$ is a minimum FVS in $H$. We say a
$C$-certificate has _order_ $z$ if for each component $H^{\prime}$ of $H$ we
have $\operatorname{\textsc{fvs}}(H^{\prime})=|C\cap V(H^{\prime})|\leq z$.
For an integer $z\geq 0$, a $z$-antler in $G$ is an antler $(C,F)$ in $G$ such
that $G[C\cup F]$ contains a $C$-certificate of order $z$. Note that a
$0$-antler has width $0$.

######  Observation 3.4.

If $(C,F)$ is a $z$-antler in $G$ for some $z\geq 0$, then for any $X\subseteq
C$, we have that $(C\setminus X,F)$ is a $z$-antler in $G-X$.

While antlers may intersect in non-trivial ways, the following proposition
relates the sizes of the cross-intersections.

######  Proposition 3.5.

If $(C_{1},F_{1})$ and $(C_{2},F_{2})$ are antlers in $G$, then $|C_{1}\cap
F_{2}|=|C_{2}\cap F_{1}|$.

######  Proof 3.6.

We show $\operatorname{\textsc{fvs}}(G[F_{1}\cup F_{2}])=|C_{1}\cap F_{2}|$.
First we show $\operatorname{\textsc{fvs}}(G[F_{1}\cup F_{2}])\geq|C_{1}\cap
F_{2}|$ by showing $(C_{1}\cap F_{2},F_{1})$ is an antler in $G[F_{1}\cup
F_{2}]$. Clearly $(C_{1},F_{1})$ is an antler in $G[F_{1}\cup F_{2}\cup
C_{1}]$, so then by 3.4 $(C_{1}\cap F_{2},F_{1})$ is an antler in $G[F_{1}\cup
F_{2}\cup C_{1}]-(C_{1}\setminus F_{2})=G[F_{1}\cup F_{2}]$.

Second we show $\operatorname{\textsc{fvs}}(G[F_{1}\cup F_{2}])\leq|C_{1}\cap
F_{2}|$ by showing $G[F_{1}\cup F_{2}]-(C_{1}\cap F_{2})$ is acyclic. Note
that $G[F_{1}\cup F_{2}]-(C_{1}\cap F_{2})=G[F_{1}\cup F_{2}]-C_{1}$. Suppose
$G[F_{1}\cup F_{2}]-C_{1}$ contains a cycle. We know this cycle does not
contain a vertex from $C_{1}$, however it does contain at least one vertex
from $F_{1}$ since otherwise this cycle exists in $G[F_{2}]$ which is a
forest. We know from 3.1 that any cycle in $G$ containing a vertex from
$F_{1}$ also contains a vertex from $C_{1}$. Contradiction. The proof for
$\operatorname{\textsc{fvs}}(G[F_{1}\cup F_{2}])=|C_{2}\cap F_{1}|$ is
symmetric. It follows that $|C_{1}\cap
F_{2}|=\operatorname{\textsc{fvs}}(G[F_{1}\cup F_{2}])=|C_{2}\cup F_{1}|$.

Lemma 3.7 shows that what remains of a $z$-antler $(C_{1},F_{1})$ when
removing a different antler $(C_{2},F_{2})$, again forms a smaller $z$-antler.
We will rely on this lemma repeatedly to ensure that after having found and
removed an incomplete fragment of a width-$k$ $z$-antler, the remainder of
that antler persists as a $z$-antler to be found later.

######  Lemma 3.7.

For any integer $z\geq 0$, if a graph $G$ has a $z$-antler $(C_{1},F_{1})$ and
another antler $(C_{2},F_{2})$, then $(C_{1}\setminus(C_{2}\cup
F_{2}),F_{1}\setminus(C_{2}\cup F_{2}))$ is a $z$-antler in $G-(C_{2}\cup
F_{2})$.

Before we prove Lemma 3.7, we prove a weaker claim:

######  Proposition 3.8.

If $(C_{1},F_{1})$ and $(C_{2},F_{2})$ are antlers in $G$, then
$(C_{1}\setminus(C_{2}\cup F_{2}),F_{1}\setminus(C_{2}\cup F_{2}))$ is an
antler in $G-(C_{2}\cup F_{2})$.

######  Proof 3.9.

For brevity let $C_{1}^{\prime}:=C_{1}\setminus(C_{2}\cup F_{2})$ and
$F_{1}^{\prime}:=F_{1}\setminus(C_{2}\cup F_{2})$ and
$G^{\prime}:=G-(C_{2}\cup F_{2})$. First note that
$(C_{1}^{\prime},F_{1}^{\prime})$ is a FVC in $G^{\prime}$ by 3.2. We proceed
to show that $\operatorname{\textsc{fvs}}(G^{\prime}[C_{1}^{\prime}\cup
F_{1}^{\prime}])\geq|C_{1}^{\prime}|$. By 3.4 $(\emptyset,F_{2})$ is an antler
in $G-C_{2}$, so then by 3.2 we have $(\emptyset,F_{2}\cap(C_{1}\cup F_{1}))$
is a FVC in $G[C_{1}\cup F_{1}]-C_{2}$. Since a FVC of width $0$ is an antler
we can apply 3.3 and obtain $\operatorname{\textsc{fvs}}(G[C_{1}\cup
F_{1}]-C_{2})=\operatorname{\textsc{fvs}}(G[C_{1}\cup F_{1}]-(C_{2}\cup
F_{2}))=\operatorname{\textsc{fvs}}(G^{\prime}[C_{1}^{\prime}\cup
F_{1}^{\prime}])$. We derive

$\displaystyle\operatorname{\textsc{fvs}}(G^{\prime}[C_{1}^{\prime}\cup
F_{1}^{\prime}])$ $\displaystyle=\operatorname{\textsc{fvs}}(G[C_{1}\cup
F_{1}]-C_{2})$ $\displaystyle\geq\operatorname{\textsc{fvs}}(G[C_{1}\cup
F_{1}])-|C_{2}\cap(C_{1}\cup F_{1})|$ $\displaystyle=|C_{1}|-|C_{2}\cap
C_{1}|-|C_{2}\cap F_{1}|$ Since $C_{1}\cap F_{1}=\emptyset$
$\displaystyle=|C_{1}|-|C_{2}\cap C_{1}|-|C_{1}\cap F_{2}|$ By Proposition 3.5
$\displaystyle=|C_{1}|-|(C_{2}\cap C_{1})\cup(C_{1}\cap F_{2})|$ Since
$C_{2}\cap F_{2}=\emptyset$ $\displaystyle=|C_{1}\setminus(C_{2}\cup
F_{2})|=|C_{1}^{\prime}|.$

We can now prove Lemma 3.7.

######  Proof 3.10.

For brevity let $C_{1}^{\prime}:=C_{1}\setminus(C_{2}\cup F_{2})$ and
$F_{1}^{\prime}:=F_{1}\setminus(C_{2}\cup F_{2})$ and
$G^{\prime}:=G-(C_{2}\cup F_{2})$. By Proposition 3.8 we know
$(C_{1}^{\prime},F_{1}^{\prime})$ is an antler, so it remains to show that
$G^{\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ contains a
$C_{1}^{\prime}$-certificate of order $z$. Since $(C_{1},F_{1})$ is a
$z$-antler in $G$, we have that $G[C_{1}\cup F_{1}]$ contains a
$C_{1}$-certificate of order $z$. Let $H$ denote this $C_{1}$-certificate and
let $\overline{H}$ be the set of all edges and vertices in
$G^{\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ that are not in $H$. Now
$(C_{1},F_{1})$ is a $z$-antler in $G^{\prime\prime}:=G-\overline{H}$ since it
is a FVC by 3.2 and $G^{\prime\prime}[C_{1}\cup F_{1}]$ contains a
$C_{1}$-certificate of order $z$ since $H$ is a subgraph of
$G^{\prime\prime}$. Note that $(C_{2},F_{2})$ is also an antler in
$G^{\prime\prime}$ since $\overline{H}$ does not contain vertices or edges
from $G[C_{2}\cup F_{2}]$. It follows that $(C_{1}^{\prime},F_{1}^{\prime})$
is an antler in $G^{\prime\prime}$ by Proposition 3.8, so
$G^{\prime\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ is a
$C_{1}^{\prime}$-certificate in $G^{\prime\prime}$. Clearly this is a
$C_{1}^{\prime}$-certificate of order $z$ since
$G^{\prime\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ is a subgraph of $H$.
Since $G^{\prime\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ is a subgraph of
$G^{\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ it follows that
$G^{\prime}[C_{1}^{\prime}\cup F_{1}^{\prime}]$ contains a
$C_{1}^{\prime}$-certificate of order $z$.

Lemma 3.11 shows that we can consider consecutive removal of two $z$-antlers
as the removal of a single $z$-antler.

######  Lemma 3.11.

For any integer $z\geq 0$, if a graph $G$ has a $z$-antler $(C_{1},F_{1})$ and
$G-(C_{1}\cup F_{1})$ has a $z$-antler $(C_{2},F_{2})$ then $(C_{1}\cup
C_{2},F_{1}\cup F_{2})$ is a $z$-antler in $G$.

######  Proof 3.12.

Since $(C_{1},F_{1})$ is a $z$-antler in $G$ we know $G[C_{1}\cup F_{1}]$
contains a $C_{1}$-certificate of order $z$, similarly $(G-(C_{1}\cup
F_{1}))[C_{2}\cup F_{2}]$ contains a $C_{2}$-certificate of order $z$. The
union of these certificate forms a $(C_{1}\cup C_{2})$-certificate of order
$z$ in $G[C_{1}\cup C_{2}\cup F_{1}\cup F_{2}]$. It remains to show that
$(C_{1}\cup C_{2},F_{1}\cup F_{2})$ is a FVC in $G$.

First we show $G[F_{1}\cup F_{2}]$ is acyclic. Suppose for contradiction that
$G[F_{1}\cup F_{2}]$ contains a cycle $\mathcal{C}$. Since $(C_{1},F_{1})$ is
a FVC in $G$, any cycle containing a vertex from $F_{1}$ also contains a
vertex from $C_{1}$, hence $\mathcal{C}$ does not contain vertices from
$F_{1}$. Therefore $\mathcal{C}$ can only contain vertices from $F_{2}$. This
is a contradiction with the fact that $G[F_{2}]$ is acyclic.

Finally we show that for each tree $T$ in $G[F_{1}\cup F_{2}]$ we have
$e(T,G-(C_{1}\cup C_{2}\cup F_{1}\cup F_{2}))\leq 1$. If $V(T)\subseteq F_{2}$
this follows directly from the fact that $(C_{2},F_{2})$ is a FVC in
$G-(C_{1}\cup F_{1})$. Similarly if $V(T)\subseteq F_{1}$ this follows
directly from the fact that $(C_{1},F_{1})$ is a FVC in $G$. So suppose $T$ is
a tree that contains vertices from both $F_{1}$ and $F_{2}$. Since $T$ is
connected, each tree in $T[F_{1}]$ contains a neighbor of a vertex in a tree
in $T[F_{2}]$. Hence no tree in $T[F_{1}]$ contains a neighbor of
$V(G-(C_{1}\cup C_{2}\cup F_{1}\cup F_{2}))$, so $e(V(T)\cap
F_{1},G-(C_{1}\cup C_{2}\cup F_{1}\cup F_{2}))=0$. To complete the proof we
show $e(V(T)\cap F_{2},G-(C_{1}\cup C_{2}\cup F_{1}\cup F_{2}))\leq 1$. Recall
each tree in $G[F_{2}]$ has at most $1$ edge to $G-(C_{1}\cup C_{2}\cup
F_{1}\cup F_{2})$, so it suffices to show that $T[F_{2}]$ is connected.
Suppose $T[F_{2}]$ is not connected, then let $u,v\in F_{2}$ be vertices from
different components of $T[F_{2}]$. Since $T$ is connected, there is a path
from $u$ to $v$. This path must use a vertex $w\in V(T-F_{2})\subseteq F_{1}$.
Let $T^{\prime}$ denote the tree in $T[F_{1}]$ that contains this vertex.
Since $(C_{1},F_{1})$ is a FVC in $G$ we have that $e(T^{\prime},F_{2})\leq
e(T^{\prime},G-(C_{1}\cup F_{1}))\leq 1$ hence no vertex in $T^{\prime}$ can
be part of a path from $u$ to $v$ in $T$. This contradicts our choice of
$T^{\prime}$.

The last structural property of antlers, given in Lemma 3.15, derives a bound
on the number of trees of a forest $G[F]$ needed to witness that $C$ is an
optimal FVS of $G[C\cup F]$. Lemma 3.15 is a corollary to the following lemma.

######  Lemma 3.13.

If a graph $G$ contains a $C$-certificate $H$ of order $z\geq 0$ for some
$C\subseteq V(G)$, then $H$ contains a $C$-certificate $\hat{H}$ of order $z$
such that $\hat{H}-C$ has at most $\frac{|C|}{2}(z^{2}+2z-1)$ trees.

######  Proof 3.14.

Consider a tree $T$ in $H-C$, we show that
$\operatorname{\textsc{fvs}}(H-V(T))=\operatorname{\textsc{fvs}}(H)$ if

  1. 1.

for all $v\in C$ such that $H[V(T)\cup\\{v\\}]$ has a cycle, $H-V(T)$ contains
an order-$z$ $v$-flower, and

  2. 2.

for all $\\{u,v\\}\in\binom{N_{H}(T)}{2}$ there are at least $z+1$ other trees
in $H-C$ adjacent to $u$ and $v$.

Consider the component $H^{\prime}$ of $H$ that contains $T$. It suffices to
show that
$\operatorname{\textsc{fvs}}(H^{\prime}-V(T))=\operatorname{\textsc{fvs}}(H^{\prime})$.
Clearly
$\operatorname{\textsc{fvs}}(H^{\prime}-V(T))\leq\operatorname{\textsc{fvs}}(H^{\prime})$
so it remains to show that
$\operatorname{\textsc{fvs}}(H^{\prime}-V(T))\geq\operatorname{\textsc{fvs}}(H^{\prime})$.
Assume
$\operatorname{\textsc{fvs}}(H^{\prime}-V(T))<\operatorname{\textsc{fvs}}(H^{\prime})$,
then let $X$ be a FVS in $H^{\prime}-V(T)$ with
$|X|<\operatorname{\textsc{fvs}}(H^{\prime})=|C\cap V(H^{\prime})|\leq z$. For
any $v\in C\cap V(H^{\prime})$ such that $H[T\cup\\{v\\}]$ has a cycle we know
from condition 1 that $H^{\prime}-V(T)$ has $z>|X|$ cycles that intersect only
in $v$, hence $v\in X$. By condition 2 we have that all but possibly one
vertex in $N_{G}(T)$ must be contained in $X$, since if there are two vertices
$x,y\in N_{G}(T)\setminus X$ then $H-V(T)-X$ has at least $z+1-|X|\geq 2$
internally vertex-disjoint paths between $x$ and $y$ forming a cycle and
contradicting our choice of $X$. Since there is at most one vertex $v\in
N_{G}(T)\setminus X$ and $H[T\cup\\{v\\}]$ does not have a cycle, we have that
$H^{\prime}-X$ is acyclic, a contraction since
$|X|<\operatorname{\textsc{fvs}}(H^{\prime})$.

The desired $C$-certificate $\hat{H}$ can be obtained from $H$ by iteratively
removing trees from $H-C$ for which both conditions hold. We show that if no
such tree exists, then $H-C$ has at most $\frac{|C|}{2}(z^{2}+2z-1)$ trees.
Each tree $T$ for which condition 1 fails can be charged to a vertex $v\in C$
that witnesses this, i.e., $H[T\cup\\{v\\}]$ has a cycle and there are at most
$z$ trees $T^{\prime}$ such that $T^{\prime}\cup v$ has a cycle. Clearly each
vertex $v\in C$ can be charged at most $z$ times, hence there are at most
$z\cdot|C|$ trees violating condition 1. Similarly each tree $T$ for which
condition 2 fails can be charged to a pair of vertices
$\\{u,v\\}\in\binom{N_{H}(T)}{2}$ for which at most $z+1$ trees in $H-T$ are
adjacent to $u$ and $v$. Clearly each pair of vertices can be charged at most
$z+1$ times. Additionally each pair consists of vertices from the same
component of $H$. Let $H_{1},\ldots,H_{\ell}$ be the components in $H$, then
there are at most $\sum_{1\leq i\leq\ell}\binom{|C\cap
V(H_{i})|}{2}=\sum_{1\leq i\leq\ell}\frac{1}{2}|C\cap V(H_{i})|(|C\cap
V(H_{i})|-1)\leq\sum_{1\leq i\leq\ell}\frac{1}{2}|C\cap
V(H_{i})|(z-1)=\frac{|C|}{2}(z-1)$ such pairs. Thus $H-C$ has at most
$z\cdot|C|+(z+1)\cdot\frac{|C|}{2}(z-1)=\frac{|C|}{2}(z^{2}+2z-1)$ trees
violating condition 2.

We can now give an upper bound on the number of trees in $G[F]$ required for a
$z$-antler $(C,F)$.

######  Lemma 3.15.

Let $(C,F)$ be a $z$-antler in a graph $G$ for some $z\geq 0$. There exists an
$F^{\prime}\subseteq F$ such that $(C,F^{\prime})$ is a $z$-antler in $G$ and
$G[F^{\prime}]$ has at most $\frac{|C|}{2}(z^{2}+2z-1)$ trees.

######  Proof 3.16.

Since $(C,F)$ is a $z$-antler, $G[C\cup F]$ contains a $C$-certificate $H$ or
order $z$ and by Lemma 3.13 we know $H$ contains a $C$-certificate $\hat{H}$
of order $z$ such that $\hat{H}-C$ has at most $\frac{|C|}{2}(z^{2}+2z-1)$
components. Take $F^{\prime}:=V(H-C)$ then $G[F^{\prime}]$ has at most
$\frac{|C|}{2}(z^{2}+2z-1)$ components and $\hat{H}$ is a subgraph of $G[C\cup
F^{\prime}]$, meaning $(C,F^{\prime})$ is a $z$-antler.

##  4 Finding Feedback Vertex Cuts

As described in Section 1, our algorithm to identify vertices in antlers uses
color coding. To allow a relatively small family of colorings to identify an
entire antler structure $(C,F)$ with $|C|\leq k$, we need to bound $|F|$ in
terms of $k$ as well. We therefore use several graph reduction steps. In this
section, we show that if there is a width-$k$ antler whose forest $F$ is
significantly larger than $k$, then we can identify a reducible structure in
the graph. To identify a reducible structure we will also use color coding. In
Section 5 we show how to reduce such a structure while preserving antlers and
optimal feedback vertex sets.

Define the function $f_{r}\colon\mathbb{N}\to\mathbb{N}$ as
$f_{r}(x)=2x^{3}+3x^{2}-x$. We say a FVC $(C,F)$ is _reducible_ if
$|F|>f_{r}(|C|)$, and we say $(C,F)$ is a _single-tree_ FVC if $G[F]$ is
connected.

######  Definition 4.1.

A FVC $(C,F)$ is _simple_ if $|F|\leq 2f_{r}(|C|)$ and one of the following
holds: (a) $G[F]$ is connected, or (b) all trees in $G[F]$ have a common
neighbor $v$ and there exists a single-tree FVC $(C,F_{2})$ with $v\in
F_{2}\setminus F$ and $F\subseteq F_{2}$.

The algorithm we will present can identify a reducible FVC when it is also
simple. First we show that such a FVC always exists when the graph contains a
single-tree reducible FVS.

######  Lemma 4.2.

If a graph $G$ contains a reducible single-tree FVC $(C,F)$ there exists a
simple reducible FVC $(C,F^{\prime})$ with $F^{\prime}\subseteq F$.

######  Proof 4.3.

We use induction on $|F|$. If $|F|\leq 2f_{r}(|C|)$ then $(C,F)$ is simple by
condition (a). Assume $|F|>2f_{r}(|C|)$. Since $(C,F)$ is a FVC and $G[F]$ is
connected there is at most one vertex $v\in F$ that has a neighbor in
$V(G)\setminus(C\cup F)$. If no such vertex exists, take $v\in F$ to be any
other vertex. Observe that $(C,F\setminus\\{v\\})$ is a FVC. Consider the
following cases:

  * •

All trees in $G[F]-v$ contain at most $f_{r}(|C|)$ vertices. Let $F^{\prime}$
be the vertices of an inclusion minimal set of trees of $G[F]-v$ such that
$|F^{\prime}|>f_{r}(|C|)$. Clearly $|F^{\prime}|\leq 2f_{r}(|C|)$ since
otherwise the set is not inclusion minimal. Each tree in $G[F^{\prime}]$
contains a neighbor of $v$ and $F^{\prime}\subseteq F$, hence $(C,F^{\prime})$
is simple by condition (b), and $(C,F^{\prime})$ is reducible since
$|F^{\prime}|>f_{r}(|C|)$.

  * •

There is a tree $T$ in $G[F]-v$ that contains more than $f_{r}(|C|)$ vertices.
Now $(C,V(T))$ is a single-tree reducible FVC with $|V(T)|<|F|$, so the
induction hypothesis applies.

We proceed to show how a simple reducible FVC can be found using color coding.
A vertex coloring of $G$ is a function $\chi\colon
V(G)\to\\{\mathsf{\dot{C}},\mathsf{\dot{F}}\\}$. We say a simple FVC $(C,F)$
is _properly colored_ by a coloring $\chi$ if
$F\subseteq\chi^{-1}(\mathsf{\dot{F}})$ and $C\cup
N_{G}(F)\subseteq\chi^{-1}(\mathsf{\dot{C}})$.

######  Lemma 4.4.

Given a graph $G$ and coloring $\chi$ of $G$ that properly colors a simple
reducible FVC $(C,F)$, a reducible FVC $(C^{\prime},F^{\prime})$ can be found
in $\mathcal{O}(n^{3})$ time.

######  Proof 4.5.

If $(C,F)$ is simple by condition (a), i.e, $G[F]$ is connected, it is easily
verified that we can find a reducible FVC in $\mathcal{O}(n^{3})$ time as
follows: Consider the set $\mathcal{T}$ of all trees in
$G[\chi^{-1}(\mathsf{\dot{F}})]$. For each tree $T\in\mathcal{T}$, if there is
a vertex $u\in N_{G}(T)$ such that $e(\\{u\\},T)=1$ take
$C^{\prime}:=N_{G}(T)\setminus\\{u\\}$, otherwise take $C^{\prime}:=N_{G}(T)$.
If $|V(T)|>f_{r}(|C^{\prime}|)$ return $(C^{\prime},V(T))$.

In the remainder of the proof we assume that $(C,F)$ is simple by condition
(b).

### Algorithm

For each $u\in\chi^{-1}_{V}(\mathsf{\dot{C}})$ consider the set $\mathcal{T}$
of all trees $T$ in $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$ such that
$e(\\{u\\},T)=1$. Let
$C^{\prime}\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})\setminus\\{u\\}$ be the
set of vertices (excluding $u$) with a neighbor in at least two trees in
$\mathcal{T}$ and let $\mathcal{T}_{1}$ be the set of trees $T\in\mathcal{T}$
for which $N_{G}(T)\subseteq C^{\prime}\cup\\{u\\}$. Now consider the set of
trees $\mathcal{T}_{2}=\mathcal{T}\setminus\mathcal{T}_{1}$ as a set of
objects for a 0-1 knapsack problem where we define for each
$T\in\mathcal{T}_{2}$ its weight as
$|N_{G}(T)\setminus(C^{\prime}\cup\\{u\\})|$ and its value as $|V(T)|$. Using
the dynamic programming algorithm [46] for the 0-1 knapsack problem we compute
for all $0\leq
b\leq|N_{G}(V(\mathcal{T}_{2}))\setminus(C^{\prime}\cup\\{u\\})|$ a set of
trees $\mathcal{T}_{2}^{b}\subseteq\mathcal{T}_{2}$ with a combined weight
$\sum_{T\in\mathcal{T}_{2}^{b}}|N_{G}(T)\setminus(C^{\prime}\cup\\{u\\})|\leq
b$ such that the combined value $\sum_{T\in\mathcal{T}_{2}^{b}}|V(T)|$ is
maximized. If for any such $b$ we have
$|V(\mathcal{T}_{1})|+|V(\mathcal{T}_{2}^{b})|>f_{r}(|C^{\prime}|+b)$ then
take $\hat{C}:=C^{\prime}\cup N_{G}(V(\mathcal{T}_{2}^{b}))\setminus\\{u\\}$
and $\hat{F}:=V(\mathcal{T}_{1})\cup V(\mathcal{T}_{2}^{b})$ and return
$(\hat{C},\hat{F})$.

### Correctness

To show that $(\hat{C},\hat{F})$ is a FVC, first note that $G[\hat{F}]$ is a
forest. For each tree $T$ in this forest we have $e(T,\\{u\\})=1$ and
$N_{G}(T)\subseteq C^{\prime}\cup\\{u\\}\cup
N_{G}(V(\mathcal{T}_{2}^{b}))=\hat{C}\cup\\{u\\}$. It follows that
$e(T,G-(\hat{C}\cup\hat{F}))=e(T,\\{u\\})=1$. To show that $(\hat{C},\hat{F})$
indeed reducible observe that
$\sum_{T\in\mathcal{T}_{2}^{b}}|N_{G}(T)\setminus(C^{\prime}\cup\\{u\\})|=|\bigcup_{T\in\mathcal{T}_{2}^{b}}N_{G}(T)\setminus(C^{\prime}\cup\\{u\\})|$
since if two trees $T_{1},T_{2}\in\mathcal{T}_{2}^{b}$ have a common neighbor
that is not $u$, it must be in $C^{\prime}$ by definition, hence the
neighborhoods only intersect on $C^{\prime}\cup\\{u\\}$. We can now deduce
$|\hat{F}|=|V(\mathcal{T}_{1})|+|V(\mathcal{T}_{2}^{b})|>f_{r}(|C^{\prime}|+b)\geq
f_{r}(|C^{\prime}|+\sum_{T\in\mathcal{T}_{2}^{b}}|N_{G}(T)\setminus(C^{\prime}\cup\\{u\\})|)=f_{r}(|C^{\prime}\cup
N_{G}(V(\mathcal{T}_{2}^{b}))\setminus\\{u\\}|)=f_{r}(|\hat{C}|)$.

It remains to show that if $\chi$ properly colors a simple reducible FVC
$(C,F)$ then for some $u\in\chi^{-1}_{V}(\mathsf{\dot{C}})$ there exists a $b$
such that $|V(\mathcal{T}_{1})|+|V(\mathcal{T}_{2}^{b})|\geq
f_{r}(|C^{\prime}|+b)$. Recall that we assumed $(C,F)$ is simple by condition
(b), i.e., all trees in $G[F]$ have a common neighbor $v$ and there exists a
single-tree FVC $(C,F_{2})$ with $v\in F_{2}\setminus F$ and $F\subseteq
F_{2}$. Since $(C,F)$ is properly colored we know
$v\in\chi^{-1}(\mathsf{\dot{C}})$, so in some iteration we will have $u=v$.
Consider the sets $\mathcal{T}$, $\mathcal{T}_{1}$, $\mathcal{T}_{2}$, and
$C^{\prime}$ as defined in this iteration. We first show $C^{\prime}\subseteq
C$. If $w\in C^{\prime}$ then $w$ has a neighbor in two trees in
$\mathcal{T}$. This means there are two internally vertex disjoint paths
between $v$ and $w$, forming a cycle. Since $v\in F_{2}$ we have by 3.1 for
the FVC $(C,F_{2})$ that this cycle must contain a vertex in $C$ which is
therefore different from $v$. Recall that $(C,F)$ is properly colored, hence
all vertices in $C$ have color $\mathsf{\dot{C}}$. Note that the internal
vertices of these paths all have color $\mathsf{\dot{F}}$ because they are
vertices from trees in $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$. Hence $w\in C$
and therefore $C^{\prime}\subseteq C$. To complete the proof we show

######  Claim 1.

There exists a value $b$ such that
$|V(\mathcal{T}_{1})|+|V(\mathcal{T}_{2}^{b})|\geq f_{r}(|C^{\prime}|+b)$.

Recall that we assumed existence of a properly colored FVC $(C,F)$ that is
reducible and simple by condition (b) witnessed by the FVC $(C,F_{2})$.
Consider the set $\mathcal{T}^{\prime}$ of trees in $G[F]$. Note that any tree
$T^{\prime}$ in $\mathcal{T}^{\prime}$ is a tree in
$G[\chi^{-1}(\mathsf{\dot{F}})]$ since $(C,F)$ is properly colored and note
that $T^{\prime}$ contains a neighbor of $v$. If $e(T^{\prime},\\{v\\})>1$
then $G[F_{2}]$ contains a cycle, contradicting that $(C,F_{2})$ is a FVC in
$G$, hence $e(T^{\prime},\\{v\\})=1$. It follows that
$T^{\prime}\in\mathcal{T}$, meaning
$\mathcal{T^{\prime}}\subseteq\mathcal{T}$. Take
$\mathcal{T}^{\prime}_{2}=\mathcal{T}^{\prime}\setminus\mathcal{T}_{1}=\mathcal{T}^{\prime}\cap\mathcal{T}_{2}$
and
$b=\sum_{T\in\mathcal{T}^{\prime}_{2}}|N_{G}(V(T))\setminus(C^{\prime}\cup\\{v\\}|$.
Clearly $\mathcal{T}^{\prime}_{2}$ is a candidate solution for the 0-1
knapsack problem with capacity $b$, hence
$|V(\mathcal{T}_{2}^{b})|\geq|V(\mathcal{T}^{\prime}_{2})|$. We deduce

$\displaystyle|V(\mathcal{T}_{1})|+|V(\mathcal{T}_{2}^{b})|$
$\displaystyle\geq|V(\mathcal{T}_{1})|+|V(\mathcal{T}^{\prime}_{2})|\geq|V(\mathcal{T}^{\prime})|=|F|$
$\displaystyle>f_{r}(|C|)$ since $(C,F)$ is reducible
$\displaystyle=f_{r}(|C^{\prime}\cup C|)$ since $C^{\prime}\subseteq C$
$\displaystyle=f_{r}(|C^{\prime}\cup(N_{G}(F)\setminus\\{v\\})\cup C|)$ since
$N_{G}(\mathcal{T}^{\prime}_{2})\setminus\\{v\\}\subseteq C$
$\displaystyle\geq
f_{r}(|C^{\prime}\cup(N_{G}(\mathcal{T}^{\prime}_{2})\setminus\\{v\\})|)$
since $f_{r}$ is non-decreasing
$\displaystyle=f_{r}(|C^{\prime}|+|N_{G}(\mathcal{T}^{\prime}_{2})\setminus(C^{\prime}\cup\\{v\\})|)$
since $|A\cup B|=|A|+|B\setminus A|$ $\displaystyle>f_{r}(|C^{\prime}|+b)$

### Running time

For each $u\in\chi^{-1}_{V}(\mathsf{\dot{C}})$ we perform a number of
$\mathcal{O}(n+m)$ time operations and run the dynamic programming algorithm
for a problem with $\mathcal{O}(n)$ objects and a capacity of $\mathcal{O}(n)$
yielding a run time of $\mathcal{O}(n^{2})$ for each $u$ or
$\mathcal{O}(n^{3})$ for the algorithm as a whole.

It can be shown that whether a FVC of width $k$ is properly colored is
determined by at most $1+k+2f_{r}(k)=\mathcal{O}(k^{3})$ relevant vertices. By
creating an $(n,\mathcal{O}(k^{3}))$-universal set for $V(G)$ using Theorem
2.1, we can obtain in $2^{\mathcal{O}(k^{3})}\cdot n\log n$ time a set of
$2^{\mathcal{O}(k^{3})}\cdot\log n$ colorings that contains a coloring for
each possible assignment of colors for these relevant vertices. By applying
Lemma 4.4 for each coloring we obtain the following lemma:

######  Lemma 4.6.

There exists an algorithm that, given a graph $G$ and an integer $k$, outputs
a (possibly empty) FVC $(C,F)$ in $G$. If $G$ contains a reducible single-tree
FVC of width at most $k$ then $(C,F)$ is reducible. The algorithm runs in time
$2^{\mathcal{O}(k^{3})}\cdot n^{3}\log n$.

######  Proof 4.7.

Take $s=2f_{r}(k)+k+1$. By Theorem 2.1 an $(n,s)$-universal set $\mathcal{U}$
for $V(G)$ of size $2^{\mathcal{O}(s)}\log n$ can be created in
$2^{\mathcal{O}(s)}n\log n$ time. For each $Q\in\mathcal{U}$ let $\chi_{Q}$ be
the coloring of $G$ with $\chi^{-1}(\mathsf{\dot{C}})=Q$. Run the algorithm
from Lemma 4.4 on $\chi_{Q}$ for every $Q\in\mathcal{U}$ and return the first
reducible FVC. If no reducible FVC was found return $(\emptyset,\emptyset)$.
We obtain an overall run time of $2^{\mathcal{O}(s)}\cdot n^{3}\log
n=2^{\mathcal{O}(k^{3})}\cdot n^{3}\log n$.

To prove correctness assume $G$ contains a reducible single-tree FVC $(C,F)$
with $|C|\leq k$. By Lemma 4.2 we know $G$ contains a simple reducible FVC
$(C,F^{\prime})$. Coloring $\chi$ properly colors $(C,F^{\prime})$ if all
vertices in $F^{\prime}\cup C\cup N_{G}(F^{\prime})$ are assigned the correct
color. Hence at most $|F^{\prime}|+|C+N_{G}(F^{\prime})|\leq 2f_{r}(k)+k+1=s$
vertices need to have the correct color. By construction of $\mathcal{U}$,
there is a $Q\in\mathcal{U}$ such that $\chi_{Q}$ assigns the correct colors
to these vertices. Hence $\chi_{Q}$ properly colors $(C,F^{\prime})$ and by
Lemma 4.4 a reducible FVC is returned.

##  5 Reducing Feedback Vertex Cuts

We apply reduction operations inspired by [12, 45] on the subgraph $G[C\cup
F]$ for a FVC $(C,F)$ in $G$. We give 5 reduction operations and show at least
one is applicable if $|F|>f_{r}(|C|)$. The operations reduce the number of
vertices $v\in F$ with $\deg_{G}(v)<3$ or reduce $e(C,F)$. The following lemma
shows that this is sufficient to reduce the size of $F$.

######  Lemma 5.1.

Let $G$ be a multigraph with minimum degree at least $3$ and let $(C,F)$ be a
FVC in $G$. We have $|F|\leq e(C,F)$.

######  Proof 5.2.

We first show that the claim holds if $G[F]$ is a tree. For all $i\geq 0$ let
$V_{i}:=\\{v\in F\mid\operatorname{deg}_{G[F]}(v)=i\\}$. Note that since
$G[F]$ is connected, $V_{0}\neq\emptyset$ if and only if $|F|=1$ and the claim
is trivially true, so suppose $V_{0}=\emptyset$. We first show $|V_{\geq
3}|<|V_{1}|$.

$\displaystyle 2|E(G[F])|$ $\displaystyle=\sum_{v\in
F}\operatorname{deg}_{G[F]}(v)\geq|V_{1}|+2|V_{2}|+3|V_{\geq 3}|$
$\displaystyle 2|E(G[F])|$
$\displaystyle=2(|V(G[F])|-1)=2|V_{1}|+2|V_{2}|+2|V_{\geq 3}|-2$

We obtain $|V_{1}|+2|V_{2}|+3|V_{\geq 3}|\leq 2|V_{1}|+2|V_{2}|+2|V_{\geq
3}|-2$ hence $|V_{\geq 3}|<|V_{1}|$. We know all vertices in $F$ have degree
at least $3$ in $G$, so $e(V(G)\setminus F,F)\geq
2|V_{1}|+|V_{2}|>|V_{1}|+|V_{2}|+|V_{\geq 3}|=|F|$. By definition of FVC there
is at most one vertex in $F$ that has an edge to $V(G)\setminus(C\cup F)$, all
other edges must be between $C$ and $F$. We obtain $1+e(C,F)>|F|$.

If $G[F]$ is a forest, then let $F_{1},\ldots,F_{\ell}$ be the vertex sets for
each tree in $G[F]$. Since $(C,F_{i})$ is a FVC in $G$ for all $1\leq
i\leq\ell$, we know $e(C,F_{i})\geq|F_{i}|$ for all $1\leq i\leq\ell$, and
since $F_{1},\ldots,F_{\ell}$ is a partition of $F$ we conclude
$e(C,F)=\sum_{1\leq i\leq\ell}e(C,F_{i})\geq\sum_{1\leq
i\leq\ell}|F_{i}|=|F|$.

Next, we give the reduction operations. These operations apply to a graph $G$
and yield a new graph $G^{\prime}$ and vertex set $S\subseteq V(G)\setminus
V(G^{\prime})$. An operation is _FVS-safe_ if for any minimum feedback vertex
set $S^{\prime}$ of $G^{\prime}$, the set $S\cup S^{\prime}$ is a minimum
feedback vertex set of $G$. An operation is _antler-safe_ if for all $z\geq 0$
and any $z$-antler $(C,F)$ in $G$, there exists a $z$-antler
$(C^{\prime},F^{\prime})$ in $G^{\prime}$ with $C^{\prime}\cup
F^{\prime}=(C\cup F)\cap V(G^{\prime})$ and $|C^{\prime}|=|C|-|(C\cup F)\cap
S|$.

######  Operation 1.

If $u,v\in V(G)$ are connected by more than two edges, remove all but two of
these edges to obtain $G^{\prime}$ and take $S:=\emptyset$.

######  Operation 2.

If $v\in V(G)$ has degree exactly $2$ and no self-loop, obtain $G^{\prime}$ by
removing $v$ from $G$ and adding an edge $e$ with $\iota(e)=N_{G}(v)$. Take
$S:=\emptyset$.

Operations 1 and 2 are well established and FVS-safe. Additionally Operation 1
can easily be seen to be antler-safe. To see that Operation 2 is antler-safe,
consider a $z$-antler $(C,F)$ in $G$ for some $z\geq 0$. If $v\not\in C$ it is
easily verified that $(C,F\setminus\\{v\\})$ is a $z$-antler in $G^{\prime}$.
If $v\in C$ pick a vertex $u\in N_{G}(v)\cap F$ and observe that $(\\{u\\}\cup
C\setminus\\{v\\},F\setminus\\{u\\})$ is a $z$-antler in $G^{\prime}$.

######  Operation 3.

If $(C,F)$ is an antler in $G$, then $G^{\prime}:=G-(C\cup F)$ and $S:=C$.

######  Lemma 5.3.

Operation 3 is FVS-safe and antler-safe.

######  Proof 5.4.

To show Operation 3 is FVS-safe, let $Z$ be a minimum FVS of $G^{\prime}$. Now
$(Z,V(G^{\prime}-Z))$ is an antler in $G^{\prime}=G-(C\cup F)$ so then $G$
contains the antler $(Z\cup C,V(G^{\prime}-Z)\cup F)=(Z\cup S,V(G-(Z\cup S)))$
by Lemma 3.11. It follows that $Z\cup S$ is a minimum FVS of $G$.

To show Operation 3 is antler-safe, let $z\geq 0$ and let $(\hat{C},\hat{F})$
be an arbitrary $z$-antler in $G$, then by Lemma 3.7 $(\hat{C}\setminus(C\cup
F),\hat{F}\setminus(C\cup F)$ is a $z$-antler in $G^{\prime}=G-(C\cup F)$. We
deduce:

$\displaystyle|\hat{C}\setminus(C\cup F)|$
$\displaystyle=|\hat{C}|-|\hat{C}\cap C|-|\hat{C}\cap F|$ since $C\cap
F=\emptyset$ $\displaystyle=|\hat{C}|-|\hat{C}\cap C|-|C\cap\hat{F}|$ by
Proposition 3.5 $\displaystyle=|\hat{C}|-|(\hat{C}\cap C)\cup(C\cap\hat{F})|$
since $\hat{C}\cap\hat{F}=\emptyset$
$\displaystyle=|\hat{C}|-|(\hat{C}\cup\hat{F})\cap
C|=|\hat{C}|-|(\hat{C}\cup\hat{F})\cap\hat{S}^{\prime}|.$

######  Operation 4.

If $(C,F)$ is a FVC in $G$ and for some $v\in C$ the graph $G[F\cup\\{v\\}]$
contains a $v$-flower of order $|C|+1$, then $G^{\prime}:=G-v$ and
$S:=\\{v\\}$.

######  Lemma 5.5.

Operation 4 is FVS-safe and antler-safe.

######  Proof 5.6.

We first show that any minimum FVS in $G$ contains $v$. Let $X$ be a minimum
FVS in $G$. If $v\not\in X$ then $|F\cap X|>|C|$ since $G[F\cup\\{v\\}]$
contains a $v$-flower of order $|C|+1$. Take $X^{\prime}:=C\cup(X\setminus
F)$, clearly $|X^{\prime}|<|X|$ so $G-X^{\prime}$ must contain a cycle since
$X$ was minimum. This cycle must contain a vertex from $X\setminus
X^{\prime}\subseteq F$, so by 3.1 this cycle must contain a vertex from $C$,
but $C\subseteq X^{\prime}$. Contradiction.

To show Operation 4 is FVS-safe, suppose $Z$ is a minimum FVS of
$G^{\prime}=G-v$. Clearly $Z\cup\\{v\\}$ is a FVS in $G$. To show that
$Z\cup\\{v\\}$ is minimum suppose $Z^{\prime}$ is a smaller FVS in $G$. We
know $v\in Z$ so $Z^{\prime}\setminus\\{v\\}$ is a FVS in $G-v$, but
$|Z^{\prime}\setminus\\{v\\}|<|Z|$ contradicting optimality of $Z$.

To show Operation 4 is antler-safe, suppose $(\hat{C},\hat{F})$ is a
$z$-antler in $G$ for some $z\geq 0$. We show
$(\hat{C}\setminus\\{v\\},\hat{F})$ is a $z$-antler in $G^{\prime}$. If
$v\in\hat{C}$ then this follows directly from 3.4, so suppose
$v\not\in\hat{C}$. Note that $v\in\hat{F}$ would contradict that any minimum
FVS in $G$ contains $v$ by 3.3. So
$G[\hat{C}\cup\hat{F}]=G^{\prime}[\hat{C}\cup\hat{F}]$ and
$(\hat{C}\setminus\\{v\\},\hat{F})=(\hat{C},\hat{F})$ is a FVC in
$G^{\prime}=G-v$ by 3.2, hence $(\hat{C}\setminus\\{v\\},\hat{F})$ is a
$z$-antler in $G^{\prime}$.

######  Operation 5.

If $(C,F)$ is a FVC in $G$, $v\in C$, and $X\subseteq F$ such that
$G[F\cup\\{v\\}]-X$ is acyclic, and if $T$ is a tree in $G[F]-X$ containing a
vertex $w\in N_{G}(v)$ such that for each $u\in N_{G}(T)\setminus\\{v\\}$
there are more than $|C|$ other trees $T^{\prime}\neq T$ in $G[F]-X$ for which
$\\{u,v\\}\subseteq N_{G}(T^{\prime})$, then take $S:=\emptyset$ and obtain
$G^{\prime}$ by removing the unique edge between $v$ and $w$, and adding
double-edges between $v$ and $u$ for all $u\in N_{G}(V(T))\setminus\\{v\\}$.

######  Lemma 5.7.

Operation 5 is FVS-safe and antler-safe.

######  Proof 5.8.

Suppose $(\hat{C},\hat{F})$ is a $z$-antler in $G$ for some $z\geq 0$. We
first prove the following claim:

######  Claim 2.

For all $u\in N_{G}(T)\setminus\\{v\\}$ we have $v\in\hat{F}\Rightarrow
u\in\hat{C}$ and $u\in\hat{F}\Rightarrow v\in\hat{C}$.

Each tree of $G[F]-X$ supplies a path between $u$ and $v$, hence there are
more than $|C|+1$ internally vertex-disjoint paths between $u$ and $v$.
Suppose $v\in\hat{F}$, we show $u\in\hat{C}$. The proof of the second
implication is symmetric. Suppose for contradiction that $u\not\in\hat{C}$.
All except possibly one of the disjoint paths between $u$ and $v$ must contain
a vertex in $\hat{C}$ by 3.1 since any two disjoint paths form a cycle
containing a vertex from $\hat{F}$. Let $Y\subseteq\hat{C}$ be the set of
vertices in $\hat{C}$ that are in a tree of $G[F]-X$ with neighbors of $u$ and
$v$, so $|Y|>|C|$. Then $|C\cup\hat{C}\setminus Y|<|\hat{C}|$ we derive a
contradiction by showing $G[\hat{C}\cup\hat{F}]-(C\cup\hat{C}\setminus Y)$ is
acyclic. We know $Y\subseteq F$, so any cycle in $G$ containing a vertex from
$Y$ also contains a vertex from $C$ by 3.1. So if
$G[\hat{C}\cup\hat{F}]-(C\cup\hat{C}\setminus Y)$ contains a cycle, then so
does $G[\hat{C}\cup\hat{F}]-(C\cup\hat{C})$ which contradicts that $\hat{C}$
is a (minimum) FVS in $G[\hat{C}\cup\hat{F}]$ since $(\hat{C},\hat{F})$ is an
antler in $G$.

To prove Operation 5 is antler-safe, we show that $(\hat{C},\hat{F})$ is also
a $z$-antler in $G^{\prime}$. Suppose $v\not\in\hat{C}\cup\hat{F}$, then
$G[\hat{C}\cup\hat{F}]=G^{\prime}[\hat{C}\cup\hat{F}]$ as $G$ and $G^{\prime}$
only differ on edges incident to $v$. It remains to show that for each tree
$T^{\prime}$ in $G^{\prime}[\hat{F}]$ we have
$e(T^{\prime},G^{\prime}-(\hat{C}\cup\hat{F}))\leq 1$. Suppose $T^{\prime}$ is
a tree in $G^{\prime}[\hat{F}]$ with
$e(T^{\prime},G^{\prime}-(\hat{C}\cup\hat{F}))>1$. Since
$e(T^{\prime},G-(\hat{C}\cup\hat{F}))\leq 1$ we know that at least one of the
edges added between $v$ and some $u\in N_{G}(T)$ has an endpoint in
$V(T^{\prime})\subseteq\hat{F}$. Since $v\not\in\hat{F}$ we have
$u\in\hat{F}$, so $v\in\hat{C}$ by 2 contradicting our assumption
$v\not\in\hat{C}\cup\hat{F}$.

Suppose $v\in\hat{C}\cup\hat{F}$, we first show that $(\hat{C},\hat{F})$ is a
FVC in $G^{\prime}$. If $v\in\hat{C}$ this is clearly the case, so suppose
$v\in\hat{F}$. From 2 it follows that
$N_{G}(T)\setminus\\{v\\}\subseteq\hat{C}$, so all edges added in $G^{\prime}$
are incident to vertices in $\hat{C}$ hence $(\hat{C},\hat{F})$ is still a FVC
in $G^{\prime}$. We now show that $G^{\prime}[\hat{C}\cup\hat{F}]$ contains an
$\hat{C}$-certificate of order $z$. We know $G[\hat{C}\cup\hat{F}]$ contains
an $\hat{C}$-certificate of order $z$. Let $H$ be an arbitrary component of
this certificate. Take $Y:=V(H)\cap\hat{C}$, so $Y$ is a minimum FVS in $H$.
It suffices to show that $Y$ is also a minimum FVS of $G^{\prime}\cap H$. This
is easily seen to be true when $v\not\in V(H)$, so suppose $v\in V(H)$. First
we argue that $(G^{\prime}\cap H)-Y$ is acyclic. This is easily seen to be
true when $v\in Y$ since $G$ and $G^{\prime}$ only differ in edges incident to
$v$, so suppose $v\not\in Y$. Then $v\not\in\hat{C}$ hence $v\in\hat{F}$ and
by 2 $N_{G}(T)\setminus\\{v\\}\subseteq\hat{C}$. It follows that
$V(H)\cap(N_{G}(T)\setminus\\{v\\})\subseteq Y$ so clearly $(G^{\prime}\cap
H)-Y$ is acyclic since all edges in $G^{\prime}\cap H$ that are not in $H$ are
incident to a vertex in $Y$.

To show $Y$ is a minimum FVS, suppose there is a FVS $Y^{\prime}$ of
$G^{\prime}\cap H$ with $|Y^{\prime}|<|Y|$. Since $H-v$ is a subgraph of
$G^{\prime}\cap H$ we know $H-(Y^{\prime}\cup\\{v\\})$ is acyclic, but since
$|Y^{\prime}|<|Y|=\operatorname{\textsc{fvs}}(H)$ we also know $H-Y^{\prime}$
contains a cycle. This cycle must contain the edge $\\{v,w\\}$ since otherwise
this cycle is also present in $(G^{\prime}\cap H)-Y^{\prime}$. Then there must
be some $u\in N_{G}(T)\setminus\\{v\\}$ on the cycle, so $u,v\not\in
Y^{\prime}$. But $G^{\prime}$ contains a double-edge between $u$ and $v$ so
$(G^{\prime}\cap H)-Y^{\prime}$ contains a cycle, contradicting that
$Y^{\prime}$ is a FVS in $G^{\prime}\cap H$.

We finally show Operation 5 is FVS-safe. Let $Z^{\prime}$ be a minimum FVS in
$G^{\prime}$, and suppose $Z^{\prime}$ is not a FVS in $G$. Then
$G-Z^{\prime}$ contains a cycle. This cycle contains the edge $\\{v,w\\}$
since otherwise $G^{\prime}-Z^{\prime}$ also contains this cycle. Since
$G^{\prime}$ contains double-edges between $v$ and all $u\in
N_{G}(T)\setminus\\{v\\}$ and $v\not\in Z^{\prime}$, it follows that
$N_{G}(T)\setminus\\{v\\}\subseteq Z^{\prime}$, but then no cycle in
$G-Z^{\prime}$ can intersect $T$ and $\\{v,w\\}$ is not part of a cycle in
$G-Z^{\prime}$. We conclude by contradiction that $Z^{\prime}$ is a FVS in
$G$. To prove optimality, consider a minimum FVS $Z$ in $G$ and observe that
$(Z,V(G-Z))$ is an antler in $G$. Since Operation 5 is antler-safe we know
$G^{\prime}$ contains an antler $(C^{\prime},F^{\prime})$ with $C^{\prime}\cup
F^{\prime}=(Z\cup V(G-Z))\cap V(G^{\prime})=V(G^{\prime})$ and
$|C^{\prime}|=|Z|-|(Z\cup V(G-Z))\cap S|=|Z|$. Since $C^{\prime}\cup
F^{\prime}=V(G^{\prime})$ we know $C^{\prime}$ is a FVS in $G^{\prime}$, hence
$\operatorname{\textsc{fvs}}(G^{\prime})\leq|C^{\prime}|=|Z|$, hence
$\operatorname{\textsc{fvs}}(G)=|Z|\geq\operatorname{\textsc{fvs}}(G^{\prime})=|Z^{\prime}|$.

Finally we show that when we are given a reducible FVC $(C,F)$ in $G$, then we
can find and apply an operation in $\mathcal{O}(n^{2})$ time. With a more
careful analysis better running time bounds can be shown, but this does not
affect the final running time of the main algorithm.

######  Lemma 5.9.

Given a graph $G$ and a reducible FVC $(C,F)$ in $G$, we can find and apply an
operation in $\mathcal{O}(n^{2})$ time.

######  Proof 5.10.

Note that if a vertex $v\in V(G)$ has a self-loop then $(\\{v\\},\emptyset)$
is an antler in $G$ and we can apply Operation 3. If a vertex $v$ has degree 0
or 1 then $(\emptyset,\\{v\\})$ is an antler in $G$. Hence Operations 1,
LABEL:, 2, LABEL:, and 3 can always be applied if the graph contains a self-
loop, a vertex with degree less than 3, or more than 2 edges between two
vertices. So assume $G$ is a graph with no self-loops, minimum degree at least
3, and at most two edges between any pair of vertices.

By Lemma 5.1 we have $e(C,F)\geq|F|>2|C|^{3}+3|C|^{2}-|C|$ so then there must
be a vertex $v$ in $C$ with more than
$\frac{1}{|C|}\cdot(2|C|^{3}+3|C|^{2}-|C|)=2|C|^{2}+3|C|-1$ edges to $F$. By
Lemma 2.2 we can find a set $X\subseteq F$ such that $G[F\cup\\{v\\}]-X$ is
acyclic and $G[F\cup\\{v\\}]$ contains a $v$-flower of order $|X|$. Hence if
$|X|\geq|C|+1$ Operation 4 can be applied, so assume $|X|\leq|C|$. For each
$u\in X\cup C\setminus\\{v\\}$ that is not connected to $v$ by a double-edge,
mark up to $|C|+1$ trees $T^{\prime}$ in $G[F]-X$ for which $\\{u,v\\}\in
N_{G}(T)$. Note that we marked at most $(|C|+1)\cdot|X\cup
C\setminus\\{v\\}|\leq(|C|+1)\cdot(2|C|-1)=2|C|^{2}+|C|-1$ trees. Since $v$
has exactly one edge to each marked tree ($G[F\cup\\{v\\}]-X$ is acyclic) and
at most two edges to each vertex in $X$, this accounts for at most
$2|C|^{2}+3|C|-1$ edges from $v$ to $F$, so there must be at least one more
edge from $v$ to a vertex $w\in F$, hence Operation 5 applies.

It can easily be verified that all operations described can be performed in
$\mathcal{O}(n^{2})$ time.

##  6 Finding and Removing Antlers

We will find antlers using color coding, using coloring functions of the form
$\chi\colon V(G)\cup
E(G)\to\\{\mathsf{\dot{F}},\mathsf{\dot{C}},\mathsf{\dot{R}}\\}$. For all
$c\in\\{\mathsf{\dot{F}},\mathsf{\dot{C}},\mathsf{\dot{R}}\\}$ let
$\chi^{-1}_{V}(c)=\chi^{-1}(c)\cap V(G)$. For any integer $z\geq 0$, a
$z$-antler $(C,F)$ in a graph $G$ is _$z$ -properly colored_ by a coloring
$\chi$ if all of the following hold: (i)
$F\subseteq\chi^{-1}_{V}(\mathsf{\dot{F}})$, (ii)
$C\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})$, (iii) $N_{G}(F)\setminus
C\subseteq\chi^{-1}_{V}(\mathsf{\dot{R}})$, and (iv) $G[C\cup
F]-\chi^{-1}(\mathsf{\dot{R}})$ is a $C$-certificate of order $z$. Recall that
$\chi^{-1}(\mathsf{\dot{R}})$ can contain edges as well as vertices so for any
subgraph $H$ of $G$ the graph $H-\chi^{-1}(\mathsf{\dot{R}})$ is obtained from
$H$ by removing both vertices and edges. It can be seen that if $(C,F)$ is a
$z$-antler, then there exists a coloring that $z$-properly colors it. Consider
for example a coloring where a vertex $v$ is colored $\mathsf{\dot{C}}$ (resp.
$\mathsf{\dot{F}}$) if $v\in C$ (resp. $v\in F$), all other vertices are
colored $\mathsf{\dot{R}}$, and for some $C$-certificate $H$ of order $z$ in
$G[C\cup F]$ all edges in $H$ have color $\mathsf{\dot{F}}$ and all other
edges have color $\mathsf{\dot{R}}$. The property in of a properly colored
$z$-antler described in Lemma 6.1 will be useful to prove correctness of the
color coding algorithm.

######  Lemma 6.1.

For any $z\geq 0$, if a $z$-antler $(C,F)$ in graph $G$ is $z$-properly
colored by a coloring $\chi$ and $H$ is a component of $G[C\cup
F]-\chi^{-1}(\mathsf{\dot{R}})$ then each component $H^{\prime}$ of $H-C$ is a
component of $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]-\chi^{-1}(\mathsf{\dot{R}})$
with $N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})\subseteq C\cap V(H)$.

######  Proof 6.2.

Note that since $C\cap\chi^{-1}_{V}(\mathsf{\dot{F}})=\emptyset$ we have that
the statement $N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})\subseteq C\cap
V(H)$ implies that
$N_{G[\chi^{-1}_{V}(\mathsf{\dot{F}})]-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})=\emptyset$
and hence that $H^{\prime}$ is a component of
$G[\chi^{-1}_{V}(\mathsf{\dot{F}})]-\chi^{-1}(\mathsf{\dot{R}})$. We show
$N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})\subseteq C\cap V(H)$.

Suppose $v\in N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})$ and let $u\in
V(H^{\prime})$ be a neighbor of $v$ in $G-\chi^{-1}(\mathsf{\dot{R}})$. Since
$V(H^{\prime})\subseteq F$ we know $u\in F$. Since $(C,F)$ is $z$-properly
colored we also have $N_{G}(F)\setminus C=\chi^{-1}(\mathsf{\dot{R}})$, hence
$N_{G}(u)\subseteq C\cup F\cup\chi^{-1}(\mathsf{\dot{R}})$ so then
$N_{G-\chi^{-1}}(u)\subseteq C\cup F$. By choice of $u$ we have $v\in
N_{G-\chi^{-1}}(u)\subseteq C\cup F$. So since $u,v\in C\cup F$, and $u$ and
$v$ are neighbors in $G-\chi^{-1}(\mathsf{\dot{R}})$ we know $u$ and $v$ are
in the same component of $G[C\cup F]-\chi^{-1}(\mathsf{\dot{R}})$, hence $v\in
V(H)$.

Suppose $v\not\in C$, so $v\in F$. Since also $u\in F$ we know that $u$ and
$v$ are in the same component of $G[F]-\chi^{-1}(\mathsf{\dot{R}})$, so $v\in
H^{\prime}$, but then $v\not\in N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})$
contradicting our choice of $v$. It follows that $v\in C$ hence $v\in C\cap
V(H)$. Since $v\in N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})$ was
arbitrary $N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})\subseteq C\cap V(H)$.

We now show that a $z$-antler can be obtained from a suitable coloring of the
graph.

######  Lemma 6.3 ($\bigstar$).

A $n^{\mathcal{O}(z)}$ time algorithm exists taking as input an integer $z\geq
0$, a graph $G$, and a coloring $\chi$ and producing as output a $z$-antler
$(C,F)$ in $G$, such that for any $z$-antler $(\hat{C},\hat{F})$ that is
$z$-properly colored by $\chi$ we have $\hat{C}\subseteq C$ and
$\hat{F}\subseteq F$.

######  Proof 6.4.

We define a function $W_{\chi}\colon 2^{\chi^{-1}_{V}(\mathsf{\dot{C}})}\to
2^{\chi^{-1}_{V}(\mathsf{\dot{F}})}$ as follows: for any
$C\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})$ let $W_{\chi}(C)$ denote the set
of all vertices that are in a component $H$ of
$G[\chi^{-1}_{V}(\mathsf{\dot{F}})]-\chi^{-1}(\mathsf{\dot{R}})$ for which
$N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H)\subseteq C$. The algorithm we describe
updates the coloring $\chi$ and recolors any vertex or edge that is not part
of a $z$-properly colored antler to color $\mathsf{\dot{R}}$.

  1. 1.

Recolor all edges to color $\mathsf{\dot{R}}$ when one of its endpoints has
color $\mathsf{\dot{R}}$.

  2. 2.

For each component $H$ of $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$ we recolor all
vertices of $H$ and their incident edges to color $\mathsf{\dot{R}}$ if $H$ is
not a tree or $e(H,\chi^{-1}_{V}(\mathsf{\dot{R}}))>1$.

  3. 3.

For each subset $C\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})$ of size at most
$z$, mark all vertices in $C$ if $\operatorname{\textsc{fvs}}(G[C\cup
W_{\chi}(C)]-\chi^{-1}(\mathsf{\dot{R}}))=|C|$.

  4. 4.

If $\chi^{-1}_{V}(\mathsf{\dot{C}})$ contains unmarked vertices we recolor
them to color $\mathsf{\dot{R}}$, remove markings made in step 3 and repeat
from step 1.

  5. 5.

If all vertices in $\chi^{-1}_{V}(\mathsf{\dot{C}})$ are marked in step 3,
return $(\chi^{-1}_{V}(\mathsf{\dot{C}}),\chi^{-1}_{V}(\mathsf{\dot{F}}))$.

### Running time

The algorithm will terminate after at most $n$ iterations since in every
iteration the number of vertices in $\chi^{-1}_{V}(\mathsf{\dot{R}})$
increases. Steps 1, 2, 4, and 5 can easily be seen to take no more than
$\mathcal{O}(n^{2})$ time. Step 3 can be performed in $\mathcal{O}(4^{z}\cdot
n^{z+1})$ time by checking for all $\mathcal{O}(n^{z})$ subsets
$C\in\chi^{-1}_{V}(\mathsf{\dot{C}})$ of size at most $z$ whether the graph
$G[C\cup W_{\chi}(C)]-\chi^{-1}(\mathsf{\dot{R}})$ has feedback vertex number
$z$. This can be done in time $\mathcal{O}(4^{z}\cdot n)$ [35]. Hence the
algorithm runs in time $n^{\mathcal{O}(z)}$.

### Correctness

We show that any $z$-properly colored antler prior to executing the algorithm
remains $z$-properly colored after termination and that in step 5,
$(\chi^{-1}_{V}(\mathsf{\dot{C}}),\chi^{-1}_{V}(\mathsf{\dot{F}}))$ is a
$z$-antler in $G$. Since
$(\chi^{-1}_{V}(\mathsf{\dot{C}}),\chi^{-1}_{V}(\mathsf{\dot{F}}))$ contains
all properly colored antlers this proves correctness.

######  Claim 3 ($\bigstar$).

All $z$-antlers $(\hat{C},\hat{F})$ that are $z$-properly colored by $\chi$
prior to executing the algorithm are also $z$-properly colored by $\chi$ after
termination of the algorithm.

To show the algorithm preserves properness of the coloring, we show that every
individual recoloring preserves properness, that is, if an arbitrary
$z$-antler is $z$-properly colored prior to the recoloring, it is also
$z$-properly colored after the recoloring.

Suppose an arbitrary $z$-antler $(\hat{C},\hat{F})$ is $z$-properly colored by
$\chi$. An edge is only recolored when one of its endpoints has color
$\mathsf{\dot{R}}$. Since these edges are not in $G[\hat{C}\cup\hat{F}]$ its
color does change whether $(\hat{C},\hat{F})$ is colored $z$-properly. All
other operations done by the algorithm are recolorings of vertices to color
$\mathsf{\dot{R}}$. We show that any time a vertex $v$ is recolored we have
that $v\not\in\hat{C}\cup\hat{F}$, meaning $(\hat{C},\hat{F})$ remains colored
$z$-properly.

Suppose $v$ is recolored in step 2, then we know $\chi(v)=\mathsf{\dot{F}}$,
and $v$ is part of a component $H$ of $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$.
Since $\chi$ $z$-properly colors $(\hat{C},\hat{F})$ we have
$\hat{F}\subseteq\chi^{-1}_{V}(\mathsf{\dot{F}})$ but
$N_{G}(\hat{F})\cap\chi^{-1}_{V}(\mathsf{\dot{F}})=\emptyset$, so since $H$ is
a component of $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$ we know either
$V(H)\subseteq\hat{F}$ or $V(H)\cap\hat{F}=\emptyset$. If
$V(H)\cap\hat{F}=\emptyset$ then clearly $v\not\in\hat{C}\cup\hat{F}$. So
suppose $V(H)\subseteq\hat{F}$, then $H$ is a tree in $G[\hat{F}]$. Since $v$
was recolored and $H$ is a tree it must be that
$e(H,\chi^{-1}_{C}(\mathsf{\dot{R}}))>1$ but this contradicts that
$(\hat{C},\hat{F})$ is a FVC.

Suppose $v$ is recolored in step 4, then we know $v$ was not marked during
step 3 and $\chi(v)=\mathsf{\dot{C}}$, so $v\not\in\hat{F}$. Suppose that
$v\in\hat{C}$. We derive a contradiction by showing that $v$ was marked in
step 3. Since $(\hat{C},\hat{F})$ is $z$-properly colored, we know that
$G[\hat{C}\cup\hat{F}]-\chi^{-1}(\mathsf{\dot{R}})$ is a $\hat{C}$-certificate
of order $z$, so if $H$ is the component of
$G[\hat{C}\cup\hat{F}]-\chi^{-1}(\mathsf{\dot{R}})$ containing $v$ then
$\operatorname{\textsc{fvs}}(H)=|\hat{C}\cap V(H)|\leq z$. Since $\hat{C}\cap
V(H)\subseteq\hat{C}\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})$ we know that in
some iteration in step 3 we have $C=\hat{C}\cap V(H)$. To show that $v$ was
marked, we show that $\operatorname{\textsc{fvs}}(G[C\cup
W_{\chi}(C))]-\chi^{-1}(\mathsf{\dot{R}}))=|C|$. We know
$G[W_{\chi}(C)]-\chi^{-1}(\mathsf{\dot{R}})$ is a forest since it is a
subgraph of $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$ which is a forest by step 2,
so we have that $\operatorname{\textsc{fvs}}(G[C\cup
W_{\chi}(C)]-\chi^{-1}(\mathsf{\dot{R}}))\leq|C|$. To show
$\operatorname{\textsc{fvs}}(G[C\cup
W_{\chi}(C))]-\chi^{-1}(\mathsf{\dot{R}}))\geq|C|$ we show that $H$ is a
subgraph of $G[C\cup W_{\chi}(C))]-\chi^{-1}(\mathsf{\dot{R}})$. By Lemma 6.1
we have that each component $H^{\prime}$ of $H-\hat{C}$ is also a component of
$G[\chi^{-1}_{V}(\mathsf{\dot{F}})]-\chi^{-1}(\mathsf{\dot{R}})$ with
$N_{G-\chi^{-1}(\mathsf{\dot{R}})}(H^{\prime})\subseteq\hat{C}\cap V(H)=C$.
Hence $V(H-\hat{C})=V(H-C)\subseteq W_{\chi}(C)$ so $H$ is a subgraph of
$G[C\cup W_{\chi}(C)]$. Since $H$ is also a subgraph of
$G[\hat{C}\cup\hat{F}]-\chi^{-1}(\mathsf{\dot{R}})$ we conclude that $H$ is a
subgraph of $G[C\cup W_{\chi}(C))]-\chi^{-1}(\mathsf{\dot{R}})$ and therefore
$\operatorname{\textsc{fvs}}(G[C\cup
W_{\chi}(C))]-\chi^{-1}(\mathsf{\dot{R}}))\geq\operatorname{\textsc{fvs}}(H)=|C|$.

######  Claim 4 ($\bigstar$).

In step 5, $(\chi^{-1}_{V}(\mathsf{\dot{C}}),\chi^{-1}_{V}(\mathsf{\dot{F}}))$
is a $z$-antler in $G$.

We know $(\chi^{-1}_{V}(\mathsf{\dot{C}}),\chi^{-1}_{V}(\mathsf{\dot{F}}))$ is
a FVC in $G$ because each component of $G[\chi^{-1}_{V}(\mathsf{\dot{F}})]$ is
a tree and has at most one edge to a vertex not in
$\chi^{-1}_{V}(\mathsf{\dot{C}})$ by step 2. It remains to show that
$G[\chi^{-1}_{V}(\mathsf{\dot{C}})\cup\chi^{-1}_{V}(\mathsf{\dot{F}})]$
contains a $\chi^{-1}_{V}(\mathsf{\dot{C}})$-certificate of order $z$. Note
that in step 5 the coloring $\chi$ is the same as in the last execution of
step 3. Let $\mathcal{C}\subseteq 2^{\chi^{-1}_{V}(\mathsf{\dot{C}})}$ be the
family of all subsets $C\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})$ that have
been considered in step 3 and met the conditions for marking all vertices in
$C$, i.e., $\operatorname{\textsc{fvs}}(G[C\cup
W_{\chi}(C)]-\chi^{-1}(\mathsf{\dot{R}}))=|C|\leq z$. Since all vertices in
$\chi^{-1}_{V}(\mathsf{\dot{C}})$ have been marked during the last execution
of step 3 we know
$\bigcup_{C\in\mathcal{C}}C=\chi^{-1}_{V}(\mathsf{\dot{C}})$.

Let $C_{1},\ldots,C_{|\mathcal{C}|}$ be the sets in $\mathcal{C}$ in an
arbitrary order and define $D_{i}:=C_{i}\setminus C_{<i}$ for all $1\leq
i\leq|\mathcal{C}|$. Observe that $D_{1},\ldots,D_{|\mathcal{C}|}$ is a
partition of $\chi^{-1}_{V}(\mathsf{\dot{C}})$ with $|D_{i}|\leq z$ and
$C_{i}\subseteq D_{\leq i}$ for all $1\leq i\leq|\mathcal{C}|$. Note that
$D_{i}$ may be empty for some $i$. We now show that
$G[\chi^{-1}_{V}(\mathsf{\dot{C}})\cup\chi^{-1}_{V}(\mathsf{\dot{F}})]$
contains a $\chi^{-1}_{V}(\mathsf{\dot{C}})$-certificate of order $z$. We do
this by showing there are $|\mathcal{C}|$ vertex disjoint subgraphs of
$G[\chi^{-1}_{V}(\mathsf{\dot{C}})\cup\chi^{-1}_{V}(\mathsf{\dot{F}})]$, call
them $G_{1},\ldots,G_{|\mathcal{C}|}$, such that
$\operatorname{\textsc{fvs}}(G_{i})=|D_{i}|\leq z$ for each $1\leq
i\leq|\mathcal{C}|$. Take $G_{i}:=G[D_{i}\cup(W_{\chi}(D_{\leq i})\setminus
W_{\chi}(D_{<i}))]-\chi^{-1}(\mathsf{\dot{R}})$ for all $1\leq
i\leq|\mathcal{C}|$. First we show that for any $i\neq j$ the graphs $G_{i}$
and $G_{j}$ are vertex disjoint. Clearly $D_{i}\cap D_{j}=\emptyset$. We can
assume $i<j$, so $D_{\leq i}\subseteq D_{<j}$ and then $W_{\chi}(D_{\leq
i})\subseteq W_{\chi}(D_{<j})$. By successively dropping two terms, we deduce

$\displaystyle(W_{\chi}(D_{\leq i})\setminus
W_{\chi}(D_{<i}))\cap(W_{\chi}(D_{\leq j})\setminus W_{\chi}(D_{<j}))$
$\displaystyle\subseteq W_{\chi}(D_{\leq i})\cap(W_{\chi}(D_{\leq j})\setminus
W_{\chi}(D_{<j}))$ $\displaystyle\subseteq W_{\chi}(D_{\leq i})\setminus
W_{\chi}(D_{<j})=\emptyset.$

We complete the proof by showing $\operatorname{\textsc{fvs}}(G_{i})=|D_{i}|$
for all $1\leq i\leq\ell$. Recall that $D_{i}=C_{i}\setminus C_{<i}$. Since
$C_{i}\in\mathcal{C}$ we know $C_{i}$ is an optimal FVS in $G[C_{i}\cup
W_{\chi}(C_{i})]-\chi^{-1}(\mathsf{\dot{R}})$, so then clearly $D_{i}$ is an
optimal FVS in $G[C_{i}\cup
W_{\chi}(C_{i})]-\chi^{-1}(\mathsf{\dot{R}})-C_{<i}=G[D_{i}\cup
W_{\chi}(C_{i})]-\chi^{-1}(\mathsf{\dot{R}})$. We know that $C_{i}\subseteq
D_{\leq i}$ so then also $W_{\chi}(C_{i})\subseteq W_{\chi}(D_{\leq i})$. It
follows that $D_{i}$ is an optimal FVS in $G[D_{i}\cup W_{\chi}(D_{\leq
i})]-\chi^{-1}(\mathsf{\dot{R}})$. In this graph, all vertices in
$W_{\chi}(D_{<i})$ must be in a component that does not contain any vertices
from $D_{i}$, so this component is a tree and we obtain
$|D_{i}|=\operatorname{\textsc{fvs}}(G[D_{i}\cup W_{\chi}(D_{\leq
i})]-\chi^{-1}(\mathsf{\dot{R}}))=\operatorname{\textsc{fvs}}(G[D_{i}\cup
W_{\chi}(D_{\leq
i})]-\chi^{-1}(\mathsf{\dot{R}})-W_{\chi}(D_{<i}))=\operatorname{\textsc{fvs}}(G[D_{i}\cup(W_{\chi}(D_{\leq
i})\setminus
W_{\chi}(D_{<i}))]-\chi^{-1}(\mathsf{\dot{R}}))=\operatorname{\textsc{fvs}}(G_{i})$.

It can be seen from 3 that for any $z$-properly colored antler
$(\hat{C},\hat{F})$ we have $\hat{C}\subseteq\chi^{-1}_{V}(\mathsf{\dot{C}})$
and $\hat{F}\subseteq\chi^{-1}_{V}(\mathsf{\dot{F}})$. 4 completes the
correctness argument.

If a graph $G$ contains a reducible single-tree FVC of width at most $k$ then
we can find and apply an operation by Lemma 4.6 and Lemma 5.9. If $G$ does not
contain such a FVC, but $G$ does contain a non-empty $z$-antler $(C,F)$ of
width at most $k$, then using Lemma 3.15 we can prove that whether $(C,F)$ is
$z$-properly colored is determined by the color of at most $26k^{5}z^{2}$
relevant vertices and edges. Using two $(n+m,26k^{5}z^{2})$-universal sets, we
can create a set of colorings that is guaranteed to contain a coloring that
$z$-properly colors $(C,F)$. Using Lemma 6.3 we find a non-empty $z$-antler
and apply Operation 3. We obtain the following:

######  Lemma 6.5 ($\bigstar$).

Given a graph $G$ and integers $k\geq z\geq 0$. If $G$ contains a non-empty
$z$-antler of width at most $k$ we can find and apply an operation in
$2^{\mathcal{O}(k^{5}z^{2})}\cdot n^{\mathcal{O}(z)}$time.

######  Proof 6.6.

Consider the following algorithm: Use Lemma 4.6 to obtain a FVC
$(C_{1},F_{1})$ in $2^{\mathcal{O}(k^{3})}\cdot n^{3}\log n$ time. If
$(C_{1},F_{1})$ is reducible we can find and apply an operation in
$\mathcal{O}(n^{2})$ time by Lemma 5.9 so assume $(C_{1},F_{1})$ is not
reducible. Create two $(n+m,26k^{5}z^{2})$-universal sets $\mathcal{U}_{1}$
and $\mathcal{U}_{2}$ for $V(G)\cup E(G)$ using Theorem 2.1. Define for each
pair $(Q_{1},Q_{2})\in\mathcal{U}_{1}\times\mathcal{U}_{2}$ the coloring
$\chi_{Q_{1},Q_{2}}$ of $G$ that assigns all vertices and edges in $Q_{1}$
color $\mathsf{\dot{C}}$, all vertices and edges in $Q_{2}\setminus Q_{1}$
color $\mathsf{\dot{F}}$, and all vertices and edges not in $Q_{1}\cup Q_{2}$
color $\mathsf{\dot{R}}$. For each
$(Q_{1},Q_{2})\in\mathcal{U}_{1}\times\mathcal{U}_{2}$ obtain in
$n^{\mathcal{O}(z)}$ time a $z$-antler $(C_{2},F_{2})$ by running the
algorithm from Lemma 6.3 on $G$ and $\chi_{Q_{1},Q_{2}}$. If $(C_{2},F_{2})$
is not empty, apply Operation 3 to remove $(C_{2},F_{2})$, otherwise report
$G$ does not contain a $z$-antler of width at most $k$.

### Running time

By Theorem 2.1, the sets $\mathcal{U}_{1}$ and $\mathcal{U}_{2}$ have size
$2^{\mathcal{O}(k^{5}z^{2})}\log n$ and can be created in
$2^{\mathcal{O}(k^{5}z^{2})}\cdot n\log n$ time. It follows that there are
$|\mathcal{U}_{1}\times\mathcal{U}_{2}|=2^{\mathcal{O}(k^{5}z^{2})}\log^{2}n$
colorings for which we apply the $n^{\mathcal{O}(z)}$ time algorithm from
Lemma 6.3. We obtain an overall running time of
$2^{\mathcal{O}(k^{5}z^{2})}\cdot n^{\mathcal{O}(z)}$. Since a $z$-antler has
width at least $z$, we can assume $k\geq z$, hence
$2^{\mathcal{O}(k^{5}z^{2})}\cdot n^{\mathcal{O}(z)}\leq
2^{\mathcal{O}(k^{7})}\cdot n^{\mathcal{O}(z)}$.

### Correctness

Suppose $G$ contains a $z$-antler $(C,F)$ of width at most $k$, we show the
algorithm finds an operation to apply. By Lemma 3.15 we know that there exists
an $F^{\prime}\subseteq F$ such that $(C,F^{\prime})$ is a $z$-antler where
$G[F^{\prime}]$ has at most $\frac{|C|}{2}(z^{2}+2z-1)$ trees. For each tree
$T$ in $G[F^{\prime}]$ note that $(C,V(T))$ is a single-tree FVC of width
$|C|\leq k$. If for some tree $T$ in $G$ the FVC $(C,V(T))$ is reducible, then
$(C_{1},F_{1})$ is reducible by Lemma 4.6 and we find an operation using Lemma
5.9, so suppose for all trees $T$ in $G[F^{\prime}]$ that $|V(T)|\leq
f_{r}(|C|)$. So then $|F^{\prime}|\leq\frac{|C|}{2}(z^{2}+2z-1)\cdot
f_{r}(|C|)$. We show that in this case there exists a pair
$(Q_{1},Q_{2})\in\mathcal{U}_{1}\times\mathcal{U}_{2}$ such that
$\chi_{Q_{1},Q_{2}}$ $z$-properly colors $(C,F^{\prime})$.

Whether a coloring $z$-properly colors $(C,F^{\prime})$ is only determined by
the colors of $C\cup F^{\prime}\cup N_{G}(F^{\prime})\cup E(G[C\cup
F^{\prime}])$.

######  Claim 5.

$|C\cup F^{\prime}\cup N_{G}(F^{\prime})\cup E(G[C\cup F^{\prime}])|\leq
26k^{5}z^{2}$.

Note that $|N_{G}(F^{\prime})\setminus C|\leq\frac{|C|}{2}(z^{2}+2z-1)$ since
no tree in $G[F^{\prime}]$ can have more than one neighbor outside $C$.
Additionally we have

$\displaystyle|E(G[C\cup F^{\prime}])|$
$\displaystyle\leq|E(G[C])|+|E(G[F^{\prime}])|+e(C,F^{\prime})$
$\displaystyle\leq|E(G[C])|+|F^{\prime}|+|C|\cdot|F^{\prime}|$ since
$G[F^{\prime}]$ is a forest
$\displaystyle\leq|C|^{2}+(|C|+1)\cdot|F^{\prime}|$
$\displaystyle\leq|C|^{2}+(|C|+1)\cdot\frac{|C|}{2}(z^{2}+2z-1)\cdot
f_{r}(|C|)$ $\displaystyle\leq
k^{2}+(k+1)\cdot\frac{k}{2}(z^{2}+2z-1)\cdot(2k^{3}+3k^{2}-k)$
$\displaystyle\leq
k^{2}+\frac{z^{2}+2z-1}{2}\cdot(k^{2}+k)\cdot(2k^{3}+3k^{2}-k)$
$\displaystyle\leq k^{2}+\frac{z^{2}+2z-1}{2}\cdot 2k^{2}\cdot 5k^{3}$ since
$k=0$ or $k\geq 1$ $\displaystyle\leq k^{2}+\frac{3z^{2}}{2}\cdot 10k^{5}$
since $z=0$ or $z\geq 1$ $\displaystyle\leq k^{2}+15k^{5}z^{2}\leq
16k^{5}z^{2},$

hence

$\displaystyle|C\cup F^{\prime}\cup N_{G}(F^{\prime})\cup E(G[C\cup
F^{\prime}])|$ $\displaystyle=|C|+|F^{\prime}|+|N_{G}(F^{\prime})\setminus
C|+|E(G[C\cup F^{\prime}])|$
$\displaystyle\leq|C|+\frac{z^{2}+2z+1}{2}f_{r}(|C|)+\frac{|C|}{2}(z^{2}+2z-1)+16k^{5}z^{2}$
$\displaystyle\leq
k+\frac{3z^{2}}{2}f_{r}(k)+\frac{k}{2}(2z^{2})+16k^{5}z^{2}$
$\displaystyle\leq k+\frac{3}{2}z^{2}\cdot(2k^{3}+3k^{2}-k)+z^{2}\cdot
k+16k^{5}z^{2}$ $\displaystyle\leq k+\frac{3}{2}z^{2}\cdot 5k^{3}+z^{2}\cdot
k+16k^{5}z^{2}\leq 26k^{5}z^{2}.$

By construction of $\mathcal{U}_{1}$ and $\mathcal{U}_{2}$ there exist
$Q_{1}\in\mathcal{U}_{1}$ and $Q_{2}\in\mathcal{U}_{2}$ such that
$\chi_{Q_{1},Q_{2}}$ $z$-properly colors $(C,F^{\prime})$. Therefore the
algorithm from Lemma 6.3 returns a non-empty $z$-antler for
$\chi_{Q_{1},Q_{2}}$ and Operation 3 can be executed.

Note that applying an operation reduces the number of vertices or increases
the number of double-edges. Hence by repeatedly using Lemma 6.5 to apply an
operation we obtain, after at most $\mathcal{O}(n^{2})$ iterations, a graph in
which no operation applies. By Lemma 6.5 this graph does not contain a non-
empty $z$-antler of width at most $k$. We show that this method reduces the
solution size at least as much as iteratively removing $z$-antlers of width at
most $k$. We first describe the behavior of such a sequence of antlers. For
integer $k\geq 0$ and $z\geq 0$, we say a sequence of disjoint vertex sets
$C_{1},F_{1},\ldots,C_{\ell},F_{\ell}$ is a _$z$ -antler-sequence_ for a graph
$G$ if for all $1\leq i\leq\ell$ the pair $(C_{i},F_{i})$ is a $z$-antler in
$G-(C_{<i}\cup F_{<i})$. The _width_ of a $z$-antler-sequence is defined as
$\max_{1\leq i\leq\ell}|C_{1}|$.

######  Proposition 6.7.

If $C_{1},F_{1},\ldots,C_{\ell},F_{\ell}$ is a _$z$ -antler-sequence_ for some
graph $G$, then the pair $(C_{\leq i},F_{\leq i})$ is a $z$-antler in $G$ for
any $1\leq i\leq\ell$.

######  Proof 6.8.

We use induction on $i$. Clearly the statement holds for $i=1$, so suppose
$i>1$. By induction $(C_{<i},F_{<i})$ is a $z$-antler in $G$, and since
$(C_{i},F_{i})$ is a $z$-antler in $G-(C_{<i}\cup F_{<i})$ we have by Lemma
3.11 that $(C_{<i}\cup C_{i},F_{<i}\cup F_{i})=(C_{\leq i},F_{\leq i})$ is a
$z$-antler in $G$.

The following theorem describes that repeatedly applying Lemma 6.5 reduces the
solution size at least as much as repeatedly removing $z$-antlers of width at
most $k$. By taking $t=1$ we obtain Theorem 1.2.

######  Theorem 6.9.

Given as input a graph $G$ and integers $k\geq z\geq 0$ we can find in
$2^{\mathcal{O}(k^{5}z^{2})}\cdot n^{\mathcal{O}(z)}$ time a vertex set
$S\subseteq V(G)$ such that

  1. 1.

there is a minimum FVS in $G$ containing all vertices of $S$, and

  2. 2.

if $C_{1},F_{1},\ldots,C_{t},F_{t}$ is a $z$-antler sequence of width at most
$k$ then $|S|\geq|C_{\leq t}|$.

######  Proof 6.10.

We first describe the algorithm.

### Algorithm

We use Lemma 6.5 to apply an operation in $G$ and obtain the resulting graph
$G^{\prime}$ and vertex set $S$. If no applicable operation was found return
an empty vertex set $S:=\emptyset$. Otherwise we recursively call our
algorithm on $G^{\prime}$ with integers $z$ and $k$ to obtain a vertex set
$S^{\prime}$ and return the vertex set $S\cup S^{\prime}$.

### Running time

Note that since every operation reduces the number of vertices or increases
the number of double-edges, after at most $\mathcal{O}(n^{2})$ operations we
obtain a graph where no operation can be applied. Therefore after at most
$\mathcal{O}(n^{2})$ recursive calls the algorithm terminates. We obtain a
running time of $2^{\mathcal{O}(k^{5}z^{2})}\cdot n^{\mathcal{O}(z)}$.

### Correctness

We prove correctness by induction on the recursion depth, which is shown the
be finite by the run time analysis.

First consider the case that no operation was found. Clearly condition 1 holds
for $G^{\prime}:=G$ and $S:=\emptyset$. To show condition 2 suppose
$C_{1},F_{1},\ldots,C_{t},F_{t}$ is a $z$-antler-sequence of width at most $k$
for $G$. The first non-empty antler in this sequence is a $z$-antler of width
at most $k$ in $G$. Since no operation was found using Lemma 6.5 it follows
that $G$ does not contain a non-empty $z$-antler of width at most $k$. Hence
all antlers in the sequence must be empty and $|C_{\leq t}|=0$, so condition 2
holds for $G^{\prime}:=G$ and $S:=\emptyset$.

For the other case, suppose $G^{\prime}$ and $S$ are obtained by applying an
operation, then since this operation is FVS-safe we know for any minimum FVS
$S^{\prime\prime}$ of $G^{\prime}$ that $S\cup S^{\prime\prime}$ is a minimum
FVS in $G$. Since $S^{\prime}$ is obtained from a recursive call there is a
minimum FVS in $G^{\prime}$ containing all vertices of $S^{\prime}$. Let
$S^{\prime\prime}$ be such a FVS in $G^{\prime}$, so $S^{\prime}\subseteq
S^{\prime\prime}$ then we know $S\cup S^{\prime\prime}$ is a minimum FVS in
$G$. It follows that there is a minimum FVS in $G$ containing all vertices of
$S\cup S^{\prime}$, proving condition 1.

To prove condition 2 suppose $C_{1},F_{1},\ldots,C_{t},F_{t}$ is a $z$-antler-
sequence of width at most $k$ for $G$. We first prove the following:

######  Claim 6.

There exists a $z$-antler-sequence
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t}^{\prime},F_{t}^{\prime}$ of width
at most $k$ for $G^{\prime}$ such that

  1. 1.

$C_{\leq t}^{\prime}\cup F_{\leq t}^{\prime}=V(G^{\prime})\cap(C_{\leq t}\cup
F_{\leq t})$ and

  2. 2.

$|C_{\leq t}^{\prime}|=\sum_{1\leq i\leq t}|C_{i}|-|(C_{i}\cup F_{i})\cap S|$.

We use induction on $t$. Since $G^{\prime}$ and $S$ are obtained through an
antler-safe operation and $(C_{1},F_{1})$ is a $z$-antler in $G$, we know that
$G^{\prime}$ contains a $z$-antler $(C_{1}^{\prime},F_{1}^{\prime})$ such that
$C_{1}^{\prime}\cup F_{1}^{\prime}=(C_{1}\cup F_{1})\cap V(G^{\prime})$ and
$|C_{1}^{\prime}|=|C_{1}|-|(C_{1}\cup F_{1})\cap S|$. The claim holds for
$t=1$.

For the induction step, consider $t>1$. By applying induction to the
length-$(t-1)$ prefix of the sequence, there is a $z$-antler sequence
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t-1}^{\prime},F_{t-1}^{\prime}$ of
width at most $k$ for $G^{\prime}$ such that both conditions hold. We have by
Proposition 6.7 that $(C_{\leq t},F_{\leq t})$ is a $z$-antler in $G$. Since
$G^{\prime}$ and $S$ are obtained through an antler-safe operation from $G$
there is a $z$-antler $(C^{\prime},F^{\prime})$ in $G^{\prime}$ such that
$C^{\prime}\cup F^{\prime}=V(G^{\prime})\cap(C_{\leq t}\cup F_{\leq t})$ and
$|C^{\prime}|=|C_{\leq t}|-|S\cap(C_{\leq t}\cup F_{\leq t})|$. Take
$C_{t}^{\prime}:=C^{\prime}\setminus(C_{<t}^{\prime}\cup F_{<t}^{\prime})$ and
$F_{t}^{\prime}:=F^{\prime}\setminus(C_{<t}^{\prime}\cup F_{<t}^{\prime})$. By
Lemma 3.7 we have that $(C_{t}^{\prime},F_{t}^{\prime})$ is a $z$-antler in
$G^{\prime}-(C_{<t}^{\prime}\cup F_{<t}^{\prime})$, it follows that
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t}^{\prime},F_{t}^{\prime}$ is a
$z$-antler-sequence for $G^{\prime}$. We first show condition 1.

$\displaystyle C_{\leq t}^{\prime}\cup F_{\leq t}^{\prime}$
$\displaystyle=C_{t}^{\prime}\cup F_{t}^{\prime}\cup C_{<t}^{\prime}\cup
F_{<t}^{\prime}$ $\displaystyle=C^{\prime}\cup F^{\prime}$ by choice of
$C_{t}^{\prime}$ and $F_{t}^{\prime}$ $\displaystyle=V(G^{\prime})\cap(C_{\leq
t}\cup F_{\leq t})$ by choice of $C^{\prime}$ and $F^{\prime}$.

To prove condition 2 and the $z$-antler-sequence
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t}^{\prime},F_{t}^{\prime}$ has width
at most $k$ we first show $|C_{t}^{\prime}|=|C_{t}|-|(C_{t}\cup F_{t})\cap
S|$. For this observe that $(C_{\leq t}^{\prime},F_{\leq t}^{\prime})$ is an
antler in $G^{\prime}$ by Proposition 6.7.

$\displaystyle|C_{t}^{\prime}|$ $\displaystyle=|C_{\leq
t}^{\prime}|-|C_{<t}^{\prime}|$ since $C_{i}^{\prime}\cap
C_{j}^{\prime}=\emptyset$ for all $i\neq j$
$\displaystyle=\operatorname{\textsc{fvs}}(G^{\prime}[C_{\leq t}^{\prime}\cup
F_{\leq t}^{\prime}])-|C_{<t}^{\prime}|$ by the above
$\displaystyle=\operatorname{\textsc{fvs}}(G^{\prime}[V(G^{\prime})\cap(C_{\leq
t}\cup F_{\leq t})])-|C_{<t}^{\prime}|$ by condition 1
$\displaystyle=\operatorname{\textsc{fvs}}(G^{\prime}[C^{\prime}\cup
F^{\prime}])-|C_{<t}^{\prime}|$ by choice of $C^{\prime}$ and $F^{\prime}$
$\displaystyle=|C^{\prime}|-|C_{<t}^{\prime}|$ since $(C^{\prime},F^{\prime})$
is an antler in $G^{\prime}$ $\displaystyle=|C^{\prime}|-\sum_{1\leq
i<t}(|C_{i}|-|(C_{i}\cup F_{i})\cap S|)$ by induction $\displaystyle=|C_{\leq
t}|-|S\cap(C_{\leq t}\cup F_{\leq t})|-\sum_{1\leq i<t}(|C_{i}|-|(C_{i}\cup
F_{i})\cap S|)$ $\displaystyle=\sum_{1\leq i\leq t}(|C_{i}|-|S\cap(C_{i}\cup
F_{i})|)-\sum_{1\leq i<t}(|C_{i}|-|(C_{i}\cup F_{i})\cap S|)$ since
$C_{1},F_{1},\ldots,C_{t},F_{t}$ are pairwise disjoint
$\displaystyle=|C_{t}|-|(C_{t}\cup F_{t})\cap S|$

We know the $z$-antler-sequence
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t-1},F_{t-1}$ has width at most $k$,
so to show that this $z$-antler-sequence has width at most $k$ it suffices to
prove that $|C_{t}^{\prime}|\leq k$. Indeed
$|C_{t}^{\prime}|=|C_{t}|-|(C_{t}\cup F_{t})\cap S|\leq|C_{t}|\leq k$.

To complete the proof of 6 we now derive condition 2:

$\displaystyle|C_{\leq t}^{\prime}|$
$\displaystyle=|C_{t}^{\prime}|+|C_{<t}^{\prime}|$ since $C_{t}^{\prime}\cap
C_{<t}^{\prime}=\emptyset$ $\displaystyle=|C_{t}|-|(C_{t}\cup F_{t})\cap
S|+|C_{<t}^{\prime}|$ $\displaystyle=|C_{t}|-|(C_{t}\cup F_{t})\cap
S|+\sum_{1\leq i\leq t-1}(|C_{i}|-|(C_{i}\cup F_{i})\cap S|)$ by induction
$\displaystyle=\sum_{1\leq i\leq t}(|C_{i}|-|(C_{i}\cup F_{i})\cap S|).$

To complete the proof of condition 2 from Theorem 6.9 we show $|S\cup
S^{\prime}|\geq|C_{\leq t}|$. By 6 we know a $z$-antler-sequence
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t}^{\prime},F_{t}^{\prime}$ of width
at most $k$ for $G^{\prime}$ exists. Since $S^{\prime}$ is obtained from a
recursive call we have $|S^{\prime}|\geq|C_{\leq t}^{\prime}|$, so then

$\displaystyle|S\cup S^{\prime}|$ $\displaystyle=|S|+|S^{\prime}|$
$\displaystyle\geq|S|+|C_{\leq t}^{\prime}|$ $\displaystyle=|S|+\sum_{1\leq
i\leq t}(|C_{i}|-|(C_{i}\cup F_{i})\cap S|)$ by 6
$\displaystyle=|S|+\sum_{1\leq i\leq t}|C_{i}|-\sum_{1\leq i\leq t}|(C_{i}\cup
F_{i})\cap S|$ $\displaystyle=|S|+|C_{\leq t}|-|S\cap(C_{\leq t}\cup F_{\leq
t})|$ since
$C_{1}^{\prime},F_{1}^{\prime},\ldots,C_{t}^{\prime},F_{t}^{\prime}$ are
disjoint $\displaystyle=|S|+|C_{\leq t}|-|S|$ $\displaystyle\geq|C_{\leq t}|.$

As a corollary to this theorem, we obtain a new type of parameterized-
tractability result for Feedback Vertex Set. For an integer $z$, let the
$z$-antler complexity of fvs on $G$ be the minimum number $k$ for which there
exists a (potentially long) sequence $C_{1},F_{1},\ldots,C_{t},F_{t}$ of
disjoint vertex sets such that for all $1\leq i\leq t$, the pair
$(C_{i},F_{i})$ is a $z$-antler of width at most $k$ in $G-(C_{<i}\cup
F_{<i})$, and such that $G-(C_{\leq t}\cup F_{\leq t})$ is acyclic (implying
that $C_{\leq t}$ is a feedback vertex set in $G$). If no such sequence
exists, the $z$-antler complexity of $G$ is $+\infty$.

Intuitively, Corollary 6.11 states that optimal solutions can be found
efficiently when they are composed out of small pieces, each of which has a
low-complexity certificate for belonging to some optimal solution.

######  Corollary 6.11.

There is an algorithm that, given a graph $G$, returns an optimal feedback
vertex set in time $f(k^{*})\cdot n^{\mathcal{O}(z^{*})}$, where
$(k^{*},z^{*})$ is any pair of integers such that the $z^{*}$-antler
complexity of $G$ is at most $k^{*}$.

######  Proof 6.12.

Let $(k^{*},z^{*})$ be such that the $z^{*}$-antler complexity of $G$ is at
most $k^{*}$. Let $p_{1}\in\mathcal{O}(k^{5}z^{2}),p_{2}\in\mathcal{O}(z)$ be
concrete functions such that the running time of Theorem 6.9 is bounded by
$2^{p_{1}(k,z)}\cdot n^{p_{2}(z)}$. Consider the pairs
$\\{(k^{\prime},z^{\prime})\in\mathbb{N}^{2}\mid 1\leq z^{\prime}\leq
k^{\prime}\leq n\\}$ in order of increasing value of the running-time
guarantee $2^{p_{1}(k,z)}\cdot n^{p_{2}(z)}$. For each such pair
$(k^{\prime},z^{\prime})$, start from the graph $G$ and invoke Theorem 6.9 to
obtain a vertex set $S$ which is guaranteed to be contained in an optimal
solution. If $G-S$ is acyclic, then $S$ itself is an optimal solution and we
return $S$. Otherwise we proceed to the next pair $(k^{\prime},z^{\prime})$.

### Correctness

The correctness of Theorem 6.9 and the definition of $z$-antler complexity
ensure that for $(k^{\prime},z^{\prime})=(k^{*},z^{*})$, the set $S$ is an
optimal solution. In particular, if $C_{1},F_{1},\ldots,C_{t},F_{t}$ is a
sequence of vertex sets witnessing that the $z^{*}$-antler complexity of $G$
is at most $k^{*}$, then (2) of Theorem 6.9 is guaranteed to output a set $S$
of size at least $\sum_{1\leq i\leq t}|C_{i}|$, which is equal to the size of
an optimal solution on $G$ by definition.

### Running time

For a fixed choice of $(k^{\prime},z^{\prime})$ the algorithm from Theorem 6.9
runs in time $2^{\mathcal{O}((k^{\prime})^{5}(z^{\prime})^{2})}\cdot
n^{\mathcal{O}(z^{\prime})}\leq 2^{\mathcal{O}((k^{*})^{5}(z^{*})^{2})}\cdot
n^{\mathcal{O}(z^{*})}$ because we try pairs $(k^{\prime},z^{\prime})$ in
order of increasing running time. As we try at most $n^{2}$ pairs before
finding the solution, the corollary follows.

To conclude, we reflect on the running time of Corollary 6.11 compared to
running times of the form
$2^{\mathcal{O}(\operatorname{\textsc{fvs}}(G))}\cdot n^{\mathcal{O}(1)}$
obtained by FPT algorithms for the parameterization by solution size. If we
exhaustively apply Lemma 5.9 with the FVC $(C,V(G)\setminus C)$, where $C$ is
obtained from a 2-approximation algorithm [9], then this gives an _antler-
safe_ kernelization: it reduces the graph as long as the graph is larger than
$f_{r}(|C|)$. This opening step reduces the instance size to
$\mathcal{O}(\operatorname{\textsc{fvs}}(G)^{3})$ without increasing the
antler complexity. As observed before, after applying $\mathcal{O}(n^{2})$
operations we obtain a graph in which no operations can be applied. This leads
to a running time of $\mathcal{O}(n^{4})$ of the kernelization. Running
Theorem 6.9 to solve the reduced instance yields a total running time of
$2^{\mathcal{O}(k^{5}z^{2})}\operatorname{\textsc{fvs}}(G)^{\mathcal{O}(z)}+\mathcal{O}(n^{4})$.
This is asymptotically faster than
$2^{\mathcal{O}(\operatorname{\textsc{fvs}}(G))}$ when $z\leq
k=o(\sqrt[7]{\operatorname{\textsc{fvs}}(G)})$ and
$\operatorname{\textsc{fvs}}(G)=\omega(\log n)$, which captures the intuitive
idea sketched above that our algorithmic approach has an advantage when there
is an optimal solution that is large but composed of small pieces for which
there are low-complexity certificates.

##  7 Conclusion

We have taken the first steps of a research program to investigate how and
when a preprocessing phase can guarantee to identify parts of an optimal
solution to an NP-hard problem, thereby reducing the search space of the
follow-up algorithm. Aside from the technical results concerning antler
structures for Feedback Vertex Set and their algorithmic properties, we
consider the conceptual message of this research program an important
contribution of our theoretical work on understanding the power of
preprocessing and the structure of solutions to NP-hard problems.

This line of investigation opens up a host of opportunities for future
research. For combinatorial problems such as Vertex Planarization, Odd Cycle
Transversal, and Directed Feedback Vertex Set, which kinds of substructures in
inputs allow parts of an optimal solution to be identified by an efficient
preprocessing phase? Is it possible to give preprocessing guarantees not in
terms of the size of an optimal solution, but in terms of measures of the
stability [7, 8, 17] of optimal solutions under small perturbations? Some
questions also remain open concerning the concrete technical results in the
paper. Can the running time of Theorem 1.2 be improved to $f(k)\cdot
n^{\mathcal{O}(1)}$? We conjecture that it cannot, but have not been able to
prove this. A related question applies to Vertex Cover: Is there an algorithm
running in time $f(k)\cdot n^{\mathcal{O}(1)}$ that, given a graph $G$ which
has disjoint vertex sets $(C,H)$ such that $N_{G}(C)\subseteq H$ and $H$ of
size $k$ is an optimal vertex cover in $G[C\cup H]$, outputs a set of size at
least $k$ that is part of an optimal vertex cover in $G$? (Note that this is
an easier target than computing such a decomposition of width $k$ if one
exists, which can be shown to be W[1]-hard.)

To apply the theoretical ideas on antlers in the practical settings that
motivated their investigation, it would be interesting to determine which
types of antler can be found in _linear_ time. One can show that a slight
extension of the standard reduction rules [16, FVS.1–FVS.5] for Feedback
Vertex Set can be used to detect 1-antlers of width $1$ in linear time. Can
the running time of Theorem 1.1 be improved to $f(k)\cdot(n+m)$? It would also
be interesting to investigate which types of antlers are present in practical
inputs.

## References

  * [1] Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, and Christopher T. Symons.  Kernelization algorithms for the vertex cover problem: Theory and experiments.  In Proc. 6th ALENEX/ANALC, pages 62–69, 2004.
  * [2] Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, and W. Henry Suters.  Crown structures for vertex cover kernelization.  Theory Comput. Syst., 41(3):411–430, 2007.  doi:10.1007/s00224-007-1328-0.
  * [3] Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, and Dieter Weninger.  Presolve reductions in mixed integer programming.  Technical Report 16-44, ZIB, Takustr.7, 14195 Berlin, 2016.  URL: http://nbn-resolving.de/urn:nbn:de:0297-zib-60370.
  * [4] Tobias Achterberg and Roland Wunderling.  Mixed Integer Programming: Analyzing 12 Years of Progress, pages 449–481.  Springer Berlin Heidelberg, 2013.  doi:10.1007/978-3-642-38189-8_18.
  * [5] Takuya Akiba and Yoichi Iwata.  Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover.  Theor. Comput. Sci., 609:211–225, 2016.  doi:10.1016/j.tcs.2015.09.023.
  * [6] Noga Alon, Raphael Yuster, and Uri Zwick.  Color-coding.  J. ACM, 42(4):844–856, 1995.
  * [7] Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, and Chen Dan.  Bilu-Linial stability, certified algorithms and the independent set problem.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, Proc. 27th ESA, volume 144 of LIPIcs, pages 7:1–7:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ESA.2019.7.
  * [8] Pranjal Awasthi, Avrim Blum, and Or Sheffet.  Center-based clustering under perturbation stability.  Inf. Process. Lett., 112(1-2):49–54, 2012.  doi:10.1016/j.ipl.2011.10.006.
  * [9] Vineet Bafna, Piotr Berman, and Toshihiro Fujito.  A 2-approximation algorithm for the undirected feedback vertex set problem.  SIAM Journal on Discrete Mathematics, 12(3):289–297, 1999.  doi:10.1137/S0895480196305124.
  * [10] Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos.  (meta) kernelization.  J. ACM, 63(5):44:1–44:69, 2016.  doi:10.1145/2973749.
  * [11] Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch.  Kernelization lower bounds by cross-composition.  SIAM J. Discrete Math., 28(1):277–305, 2014.  doi:10.1137/120880240.
  * [12] Hans L. Bodlaender and Thomas C. van Dijk.  A cubic kernel for feedback vertex set and loop cutset.  Theory Comput. Syst., 46(3):566–597, 2010.  doi:10.1007/s00224-009-9234-2.
  * [13] Kevin Burrage, Vladimir Estivill-Castro, Michael R. Fellows, Michael A. Langston, Shev Mac, and Frances A. Rosamond.  The undirected feedback vertex set problem has a poly($k$) kernel.  In Hans L. Bodlaender and Michael A. Langston, editors, Proc. 2nd IWPEC, volume 4169 of Lecture Notes in Computer Science, pages 192–202. Springer, 2006.  doi:10.1007/11847250_18.
  * [14] Jianer Chen, Iyad A. Kanj, and Ge Xia.  Improved upper bounds for vertex cover.  Theor. Comput. Sci., 411(40-42):3736 – 3756, 2010.  doi:10.1016/j.tcs.2010.06.026.
  * [15] Benny Chor, Mike Fellows, and David W. Juedes.  Linear kernels in linear time, or how to save $k$ colors in $O$$(n^{2})$ steps.  In Proc. 30th WG, pages 257–269, 2004.  doi:10.1007/978-3-540-30559-0_22.
  * [16] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [17] Amit Daniely, Nati Linial, and Michael E. Saks.  Clustering is difficult only when it does not matter.  CoRR, abs/1205.4891, 2012.  URL: http://arxiv.org/abs/1205.4891.
  * [18] Holger Dell and Dieter van Melkebeek.  Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.  J. ACM, 61(4):23:1–23:27, 2014.  doi:10.1145/2629620.
  * [19] Huib Donkers and Bart M. P. Jansen.  A Turing kernelization dichotomy for structural parameterizations of $\mathcal{F}$-minor-free deletion.  In Ignasi Sau and Dimitrios M. Thilikos, editors, Proc. 45th WG, volume 11789 of Lecture Notes in Computer Science, pages 106–119. Springer, 2019.  doi:10.1007/978-3-030-30786-8_9.
  * [20] Rod Downey and Michael R. Fellows.  Parameterized Complexity.  Monographs in Computer Science. Springer, New York, 1999.
  * [21] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.  doi:10.1007/978-1-4471-5559-1.
  * [22] Andrew Drucker.  New limits to classical and quantum instance compression.  SIAM J. Comput., 44(5):1443–1479, 2015.  doi:10.1137/130927115.
  * [23] M. Ayaz Dzulfikar, Johannes Klaus Fichte, and Markus Hecher.  The PACE 2019 parameterized algorithms and computational experiments challenge: The fourth iteration (invited paper).  In Bart M. P. Jansen and Jan Arne Telle, editors, Proc. 14th IPEC, volume 148 of LIPIcs, pages 25:1–25:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.IPEC.2019.25.
  * [24] Michael R. Fellows.  Blow-ups, win/win’s, and crown rules: Some new directions in FPT.  In Hans L. Bodlaender, editor, Proc. 29th WG, volume 2880 of Lecture Notes in Computer Science, pages 1–12. Springer, 2003.  doi:10.1007/978-3-540-39890-5_1.
  * [25] Michael R. Fellows.  The lost continent of polynomial time: Preprocessing and kernelization.  In Hans L. Bodlaender and Michael A. Langston, editors, Proc. 2nd IWPEC, volume 4169 of Lecture Notes in Computer Science, pages 276–277. Springer, 2006.  doi:10.1007/11847250_25.
  * [26] J. Flum and M. Grohe.  Parameterized Complexity Theory.  Springer-Verlag, 2006.  doi:10.1007/3-540-29953-X.
  * [27] Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh.  Planar $\mathcal{F}$-Deletion: Approximation, kernelization and optimal FPT algorithms.  In Proc. 53rd FOCS, pages 470–479, 2012.  doi:10.1109/FOCS.2012.62.
  * [28] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.  doi:10.1017/9781107415157.
  * [29] Lance Fortnow and Rahul Santhanam.  Infeasibility of instance compression and succinct PCPs for NP.  J. Comput. Syst. Sci., 77(1):91–106, 2011.  doi:10.1016/j.jcss.2010.06.007.
  * [30] Jiong Guo and Rolf Niedermeier.  Invitation to data reduction and problem kernelization.  SIGACT News, 38(1):31–45, 2007.  doi:10.1145/1233481.1233493.
  * [31] Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu.  A completeness theory for polynomial (Turing) kernelization.  Algorithmica, 71(3):702–730, 2015.  doi:10.1007/s00453-014-9910-8.
  * [32] Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash.  Wegotyoucovered: The winning solver from the PACE 2019 implementation challenge, vertex cover track.  CoRR, abs/1908.06795, 2019.  arXiv:1908.06795.
  * [33] Demian Hespe, Christian Schulz, and Darren Strash.  Scalable kernelization for maximum independent sets.  ACM Journal of Experimental Algorithmics, 24(1):1.16:1–1.16:22, 2019.  doi:10.1145/3355502.
  * [34] Yoichi Iwata.  Linear-time kernelization for feedback vertex set.  In Proc. 44th ICALP, volume 80 of LIPIcs, pages 68:1–68:14, 2017.  doi:10.4230/LIPIcs.ICALP.2017.68.
  * [35] Yoichi Iwata and Yusuke Kobayashi.  Improved analysis of highest-degree branching for feedback vertex set.  In Bart M. P. Jansen and Jan Arne Telle, editors, Proc. 14th IPEC, volume 148 of LIPIcs, pages 22:1–22:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.IPEC.2019.22.
  * [36] Bart M. P. Jansen, Venkatesh Raman, and Martin Vatshelle.  Parameter ecology for feedback vertex set.  Tsinghua Science and Technology, 19(4):387–409, 2014.  doi:10.1109/TST.2014.6867520.
  * [37] R. M. Karp.  Reducibility Among Combinatorial Problems.  In Complexity of Computer Computations, pages 85–103. Plenum Press, 1972.
  * [38] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  In Proc. 53rd FOCS, pages 450–459, 2012.  doi:10.1109/FOCS.2012.46.
  * [39] Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh.  Faster parameterized algorithms using linear programming.  ACM Trans. Algorithms, 11(2):15:1–15:31, 2014.  doi:10.1145/2566616.
  * [40] Moni Naor, Leonard J. Schulman, and Aravind Srinivasan.  Splitters and near-optimal derandomization.  In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182–191. IEEE Computer Society, 1995.  doi:10.1109/SFCS.1995.492475.
  * [41] G.L. Nemhauser and L.E.jun. Trotter.  Vertex packings: structural properties and algorithms.  Math. Program., 8:232–248, 1975.  doi:10.1007/BF01580444.
  * [42] Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen.  Network sparsification for steiner problems on planar and bounded-genus graphs.  ACM Trans. Algorithms, 14(4):53:1–53:73, 2018.  doi:10.1145/3239560.
  * [43] W. V. Quine.  The problem of simplifying truth functions.  The American Mathematical Monthly, 59(8):521–531, 1952.  URL: http://www.jstor.org/stable/2308219, doi:10.2307/2308219.
  * [44] Jean-Florent Raymond and Dimitrios M. Thilikos.  Recent techniques and results on the erdős-pósa property.  Discret. Appl. Math., 231:25–43, 2017.  doi:10.1016/j.dam.2016.12.025.
  * [45] Stéphan Thomassé.  A $4k^{2}$ kernel for feedback vertex set.  ACM Trans. Algorithms, 6(2), 2010.  doi:10.1145/1721837.1721848.
  * [46] P. Toth.  Dynamic programming algorithms for the zero-one knapsack problem.  Computing, 25:29–45, 1980.  doi:10.1007/BF02243880.

##  Appendix A NP-hardness of finding 1-antlers

######  Lemma A.1 ([19, Lemma 2 for $H=K_{3}$]).

There is a polynomial-time algorithm that, given a CNF formula $\Phi$, outputs
a graph $G$ and a collection $\mathcal{H}=\\{H_{1},\ldots,H_{\ell}\\}$ of
vertex-disjoint cycles in $G$, such that $\Phi$ is satisfiable if and only if
$G$ has a feedback vertex set of size $\ell$.

######  Definition A.2.

A 1-antler in an undirected multigraph $G$ is a pair of disjoint vertex sets
$(C,F)$ such that:

  1. 1.

$G[F]$ is acyclic,

  2. 2.

each tree $T$ of the forest $G[F]$ is connected to $V(G)\setminus(C\cup F)$ by
at most one edge, and

  3. 3.

the graph $G[C\cup F]$ contains $|C|$ vertex-disjoint cycles.

A 1-antler is called _non-empty_ if $H\cup C\neq\emptyset$.

Will use the following easily verified consequence of this definition.

######  Observation A.3.

If $(C,F)$ is a 1-antler in an undirected multigraph $G$, then for each vertex
$c\in C$ the graph $G[\\{c\\}\cup F]$ contains a cycle.

In the terminology of Section 1, the cut $C$ corresponds to $\mathsf{head}$
and the forest $F$ corresponds to $\mathsf{antler}$. Observe that this self-
contained definition of a 1-antler is equivalent to the general definition of
$z$-antler from Section 3 for $z=1$.

######  Corollary A.4.

Assuming $\mathsf{P}$ $\neq$ $\mathsf{NP}$, there is no polynomial-time
algorithm that, given a graph $G$, outputs a non-empty 1-antler in $G$ or
concludes that no non-empty 1-antler exists.

######  Proof A.5.

We need the following simple claim.

######  Claim 7.

If $G$ contains a packing of $\ell\geq 1$ vertex-disjoint cycles and a
feedback vertex set of size $\ell$, then $G$ admits a non-empty 1-antler.

Let $C$ be a feedback vertex set in $G$ of size $\ell$ and let
$F:=V(G)\setminus C$.

Now suppose there is a polynomial-time algorithm to find a non-empty 1-antler
decomposition, if one exists. We use it to solve CNF-SAT in polynomial time.
Given an input formula $\Phi$ for CNF-SAT, use Lemma A.1 to produce in
polynomial time a graph $G$ and a packing $\mathcal{H}$ of $\ell$ vertex-
disjoint cycles in $G$, such that $\Phi$ is satisfiable if and only if
$\operatorname{\textsc{fvs}}(G)=\ell$. The following recursive polynomial-time
algorithm correctly tests, given a graph $G$ and a packing $\mathcal{H}$ of
some $\ell\geq 0$ vertex-disjoint cycles in $G$, whether
$\operatorname{\textsc{fvs}}(G)=\ell$.

  1. 1.

If $\ell=0$, then output yes if and only if $G$ is acyclic.

  2. 2.

If $\ell>0$, run the hypothetical algorithm to find a non-empty 1-antler
$(C,F)$.

    1. (a)

If a non-empty 1-antler $(C,F)$ is returned, then let $\mathcal{H^{\prime}}$
consist of those cycles in the packing not intersected by $C$, and let
$\ell^{\prime}:=|\mathcal{H^{\prime}}|$. Return the result of recursively
running the algorithm on $G^{\prime}:=G-(C\cup F)$ and $\mathcal{H^{\prime}}$
to test whether $G^{\prime}$ has a feedback vertex set of size
$|\mathcal{H^{\prime}}|$.

    2. (b)

Otherwise, return no.

The claim shows that the algorithm is correct when it returns no. Observation
3.3 shows that if we recurse, we have $\operatorname{\textsc{fvs}}(G)=\ell$ if
and only if $\operatorname{\textsc{fvs}}(G-(C\cup H))=\ell^{\prime}$; hence
the result of the recursion is the correct output. Since the number of
vertices in the graph reduces by at least one in each iteration, the overall
running time is polynomial assuming the hypothetical algorithm to compute a
non-empty 1-antler. Hence using Lemma A.1 we can decide CNF-SAT in polynomial
time.

######  Corollary A.6.

It is NP-complete to determine whether
$\operatorname{\textsc{fvs}}(G)=\operatorname{\textsc{fvs}}LP(G)$. Here
$\operatorname{\textsc{fvs}}(G)$ denotes the minimum size of a feedback vertex
set in $G$, and $\operatorname{\textsc{fvs}}LP(G)$ denotes the minimum cost of
a solution to the linear programming relaxation of Feedback Vertex Set on $G$.

######  Proof A.7.

Membership in NP is trivial; we prove hardness. Suppose such an algorithm
exists. As above, we use it to solve CNF-SAT in polynomial time. Given an
input $\Phi$ for SAT, use Lemma A.1 to produce in polynomial time a graph $G$
and packing $\mathcal{H}$ of $\ell$ vertex-disjoint cycles in $G$, such that
$\Phi$ is satisfiable if and only if $\operatorname{\textsc{fvs}}(G)=\ell$.

Compute the cost $c$ of an optimal solution to the linear programming
relaxation of Feedback Vertex Set on $G$, using the ellipsoid method. By the
properties of a relaxation, if $c>\ell$ then
$\operatorname{\textsc{fvs}}(G)>\ell$, and hence we can safely report that
$\Phi$ is unsatisfiable. If $c\leq\ell$, then the existence of $\ell$ vertex-
disjoint cycles in $G$ implies that $c=\ell$. Run the hypothetical algorithm
to test whether
$\operatorname{\textsc{fvs}}(G)=\operatorname{\textsc{fvs}}LP(G)$. If the
answer is yes, then $G$ has a feedback vertex set of size $\ell$ and hence
$\Phi$ is satisfiable; if not, then $\Phi$ is unsatisfiable.

##  Appendix B W[1]-hardness of finding bounded-width 1-antlers

We consider the following parameterized problem.

Bounded-Width 1-Antler Detection Input: An undirected multigraph $G$ and an
integer $k$. Parameter: $k$. Question: Does $G$ admit a non-empty 1-antler
$(C,F)$ with $|C|\leq k$?

We prove that Bounded-Width 1-Antler Detection is W[1]-hard by a reduction
from Multicolored Clique, which is defined as follows.

Multicolored Clique Input: An undirected simple graph $G$, an integer $k$, and
a partition of $V(G)$ into sets $V_{1},\ldots,V_{k}$. Parameter: $k$.
Question: Is there a clique $S$ in $G$ such that for each $1\leq i\leq k$ we
have $|S\cap V_{i}|=1$?

The sets $V_{i}$ are referred to as _color classes_ , and a solution clique
$S$ is called a _multicolored clique_. It is well-known that Multicolored
Clique is W[1]-hard (cf. [16, Thm. 13.25]). Our reduction is inspired by the
W[1]-hardness of detecting a Hall set [16, Exercise 13.28]. In the proof, we
use the following shorthand notation: for a positive integer $n$, we denote by
$[n]$ the set $\\{1,\ldots,n\\}$.

######  Theorem B.1.

Bounded-Width 1-Antler Detection is W[1]-hard.

######  Proof B.2.

We give a parameterized reduction [16, Def. 13.1] from the Multicolored Clique
problem. By inserting isolated vertices if needed, we may assume without loss
of generality that for the input instance $(G,k,V_{1},\ldots,V_{k})$ we have
$|V_{1}|=|V_{2}|=\ldots=|V_{k}|=n$ for some $n\geq k(k-1)+4$. For each
$i\in[k]$, fix an arbitrary labeling of the vertices in $V_{i}$ as $v_{i,j}$
for $j\in[n]$. Given this instance, we construct an input
$(G^{\prime},k^{\prime})$ for Bounded-Width 1-Antler Detection as follows.

  1. 1.

For each $i\in[k]$, for each $j\in[n]$, create a set
$U_{i,j}=\\{u_{i,j,\ell}\mid\ell\in[k]\setminus\\{i\\}\\}$ of vertices in
$G^{\prime}$ to represent $v_{i,j}$. Intuitively, vertex $u_{i,j,\ell}$
represents the connection that the $j$th vertex from the $i$th color class
should have to the neighbor in the $\ell$th color class chosen in the solution
clique.

  2. 2.

Define $\mathcal{U}:=\bigcup_{i\in[k]}\bigcup_{j\in[n]}U_{i,j}$. Insert
(single) edges to turn $\mathcal{U}$ into a clique in $G^{\prime}$.

  3. 3.

For each edge $e$ in $G$ between vertices of different color classes, let
$e=\\{v_{i,j},v_{i^{\prime},j^{\prime}}\\}$ with $i<i^{\prime}$, and insert
two vertices into $G^{\prime}$ to represent $e$:

     * •

Insert a vertex $w_{e}$, add an edge from $w_{e}$ to each vertex in
$U_{i,j}\cup U_{i^{\prime},j^{\prime}}$, and then add a second edge between
$w_{e}$ and $u_{i,j,i^{\prime}}$.

     * •

Insert a vertex $w_{e^{\prime}}$, add an edge from $w_{e^{\prime}}$ to each
vertex in $U_{i,j}\cup U_{i^{\prime},j^{\prime}}$, and then add a second edge
between $w_{e^{\prime}}$ and $u_{i^{\prime},j^{\prime},i}$.

Let $W$ denote the set of vertices of the form $w_{e},w_{e^{\prime}}$ inserted
to represent an edge of $G$. Observe that $W$ is an independent set in $G$.

  4. 4.

Finally, insert a vertex $u^{*}$ into $G^{\prime}$. Add a single edge from
$u^{*}$ to all other vertices of $G^{\prime}$, to make $u^{*}$ into a
universal vertex.

This concludes the construction of $G^{\prime}$. Note that $G^{\prime}$
contains double-edges, but no self-loops. We set $k^{\prime}:=k(k-1)$, which
is appropriately bounded for a parameterized reduction. It is easy to see that
the reduction can be performed in polynomial time. It remains to show that $G$
has a multicolored $k$-clique if and only if $G^{\prime}$ has a nonempty
1-antler of width at most $k$. To illustrate the intended behavior of the
reduction, we first prove the forward implication.

######  Claim 8.

If $G$ has a multicolored clique of size $k$, then $G^{\prime}$ has a non-
empty 1-antler of width $k^{\prime}$.

Suppose $S$ is a multicolored clique of size $k$ in $G$. Choose indices
$j_{1},\ldots,j_{k}$ such that $S\cap V_{i}=\\{v_{i,j_{i}}\\}$ for all
$i\in[k]$. Define a 1-antler $(C,F)$ in $G^{\prime}$ as follows:

  * •

$C=\bigcup_{i\in[k]}U_{i,j_{i}}$.

  * •

$F=\\{w_{e},w_{e^{\prime}}\mid e\text{\leavevmode\nobreak\ is an edge
in\leavevmode\nobreak\ $G$ between distinct vertices of\leavevmode\nobreak\
$S$}\\}$.

Since each set $U_{i,j_{i}}$ has size $k-1$, it follows that
$|C|=k(k-1)=k^{\prime}$. Since $F\subseteq W$ is an independent set in
$G^{\prime}$, it also follows that $G^{\prime}[F]$ is acyclic. Each tree $T$
in the forest $G^{\prime}[F]$ consists of a single vertex $w_{e}$ or
$w_{e^{\prime}}$. By construction, there is exactly one edge between $T$ and
$V(G^{\prime})\setminus(C\cup F)$; this is the edge to the universal vertex
$u^{*}$. It remains to verify that $G^{\prime}[C\cup F]$ contains $|C|$
vertex-disjoint cycles, each containing exactly one vertex of $C$. Consider an
arbitrary vertex $u_{i,j_{i},\ell}$ in $C$; we show we can assign it a cycle
in $G^{\prime}[C\cup F]$ so that all assigned cycles are vertex-disjoint.
Since $S$ is a clique, there is an edge $e$ in $G$ between $v_{i,j_{i}}$ and
$v_{\ell,j_{\ell}}$, and the corresponding vertices $w_{e},w_{e^{\prime}}$ are
in $F$. If $i<\ell$, then $w_{e}\in F$ and there are two edges between
$u_{i,j_{i},\ell}$ and $w_{e}$, forming a cycle on two vertices. If $i>\ell$,
then there is a cycle on two vertices $u_{i,j_{i},\ell}$ and $w_{e^{\prime}}$.
Since for any vertex of the form $w_{e}$ or $w_{e^{\prime}}$ there is a unique
vertex of $C$ that it has a double-edge to, the resulting cycles are indeed
vertex-disjoint. This proves that $(C,F)$ is a 1-antler of width $k^{\prime}$.

Before proving reverse implication, we establish some structural claims about
the structure of 1-antlers in $G^{\prime}$.

######  Claim 9.

If $(C,F)$ is a non-empty 1-antler in $G^{\prime}$ with $|C|\leq k^{\prime}$,
then the following holds:

  1. 1.

$\mathcal{U}\cap F=\emptyset$.

  2. 2.

$u^{*}\notin C\cup F$.

  3. 3.

$W\cap C=\emptyset$.

  4. 4.

$C\subseteq\mathcal{U}$, $F\subseteq W$, and each tree of the forest
$G^{\prime}[F]$ consists of a single vertex.

  5. 5.

For each vertex $w\in F$ we have $N_{G^{\prime}}(w)\cap\mathcal{U}\subseteq
C$.

  6. 6.

$F\neq\emptyset$.

(1) Assume for a contradiction that there is a vertex
$u_{i,j,\ell}\in\mathcal{U}\cap F$. Since $G^{\prime}[F]$ is a forest by
Property (1) of Definition A.2, while $\mathcal{U}$ is a clique in
$G^{\prime}$, it follows that $|F\cap\mathcal{U}|\leq 2$. By Property (2), for
a vertex in $F$, there is at most one of its neighbors that belongs to neither
$F$ nor $C$. Since $|\mathcal{U}|\geq n\geq k(k-1)+4$, and $u_{i,j,\ell}\in F$
is adjacent to all other vertices of $\mathcal{U}$ since that set forms a
clique, the fact that $|F\cap\mathcal{U}|\leq 2$ implies that
$|C\cap\mathcal{U}|\geq|\mathcal{U}|-2-1\geq k(k-1)+4-3>k^{\prime}$. So
$|C|>k^{\prime}$, which contradicts that $(C,F)$ is a 1-antler with $|C|\leq
k^{\prime}$.

(2) Since $u^{*}$ is a universal vertex in $G^{\prime}$, the set
$\mathcal{U}\cup\\{u^{*}\\}$ is a clique and the preceding argument shows that
$u^{*}\notin F$. To prove the claim we show that additionally, $u^{*}\notin
C$. Assume for a contradiction that $u^{*}\in C$. By Observation A.3, the
graph $G^{\prime}[\\{u^{*}\\}\cup F]$ contains a cycle. Since $W$ is an
independent set in $G^{\prime}$ and $u^{*}$ is not incident on any double-
edges, the graph $G^{\prime}[\\{u^{*}\\}\cup W]$ is acyclic. Hence to get a
cycle in $G^{\prime}[\\{u^{*}\\}\cup F]$, the set $F$ contains at least one
vertex that is not in $W$ and not $u^{*}$; hence this vertex belongs to
$\mathcal{U}$. So $\mathcal{U}\cap F\neq\emptyset$; but this contradicts Claim
9(1).

(3) Assume for a contradiction that $w\in W\cap C$. Again by Observation A.3,
there is a cycle in $G^{\prime}[\\{w\\}\cup F]$, and since $G^{\prime}$ does
not have any self-loops this implies $N_{G^{\prime}}(w)\cap F\neq\emptyset$.
But by construction of $G^{\prime}$ we have
$N_{G^{\prime}}(w)\subseteq\mathcal{U}\cup\\{u^{*}\\}$, so $F$ contains a
vertex of either $\mathcal{U}$ or $u^{*}$. But this contradict either Claim
9(2) or Claim 9(3).

(4) Since the sets $\mathcal{U},W,\\{u^{*}\\}$ form a partition of
$V(G^{\prime})$, the preceding subclaims imply $C\subseteq\mathcal{U}$ and
$F\subseteq W$. Since $W$ is an independent set in $G^{\prime}$, this implies
that each tree $T$ of the forest $G^{\prime}[W]$ consists of a single vertex.

(5) Consider a vertex $w\in F$, which by itself forms a tree in
$G^{\prime}[F]$. Since $u^{*}\notin C\cup F$, the edge between $T$ and $u^{*}$
is the unique edge connecting $T$ to a vertex of $V(G^{\prime})\setminus(C\cup
F)$, and therefore all neighbors of $T$ other than $u^{*}$ belong to $C\cup
F$. Since a vertex $w\in W$ has
$N_{G^{\prime}}(w)\subseteq\mathcal{U}\cup\\{u^{*}\\}$, it follows that
$N_{G^{\prime}}(w)\cap\mathcal{U}\subseteq C$.

(6) By the assumption that $(C,F)$ is non-empty, we have $C\cup
F\neq\emptyset$. This implies that $F\neq\emptyset$: if $C$ would contain a
vertex $c$ while $F=\emptyset$, then by Observation A.3 the graph
$G^{\prime}[\\{c\\}\cup F]=G^{\prime}[\\{c\\}]$ would contain a cycle, which
is not the case since $G^{\prime}$ has no self-loops. Hence $F\neq\emptyset$.

With these structural insights, we can prove the remaining implication.

######  Claim 10.

If $G^{\prime}$ has a non-empty 1-antler $(C,F)$ with $|C|\leq k^{\prime}$,
then $G$ has a multicolored clique of size $k$.

Let $(C,F)$ be a non-empty 1-antler in $G^{\prime}$ with $|C|\leq k^{\prime}$.
By Claim 9 we have $C\subseteq\mathcal{U}$, while $F\subseteq W$ and
$F\neq\emptyset$. Consider a fixed vertex $w\in F$. Since $F\subseteq W$,
vertex $w$ is of the form $w_{e}$ or $w_{e^{\prime}}$ constructed in Step 3 to
represent some edge $e$ of $G$. Choose $i^{*}\in[k],j^{*}\in[n]$ such that
$v_{i^{*},j^{*}}\in V_{i^{*}}$ is an endpoint of edge $e$ in $G$. By
construction we have $U_{i^{*},j^{*}}\subseteq N_{G^{\prime}}(w)$ and
therefore Claim 9(5) implies $U_{i^{*},j^{*}}\subseteq C$.

Consider an arbitrary $\ell\in[k]\setminus\\{i^{*}\\}$. Then
$u_{i^{*},j^{*},\ell}\in U_{i^{*},j^{*}}\subseteq C$, so by Observation A.3
the graph $G^{\prime}[\\{u_{i^{*},j^{*},\ell}\\}\cup F]$ contains a cycle.
Since $G^{\prime}[F]$ is an independent set and $G^{\prime}$ has no self-
loops, this cycle consists of two vertices joined by a double-edge. By
construction of $G^{\prime}$, such a cycle involving $u_{i^{*},j^{*},\ell}$
exists only through vertices $w_{e}$ or $w_{e^{\prime}}$ where $e$ is an edge
of $G$ connecting $v_{i^{*},j^{*}}$ to a neighbor in class $V_{\ell}$.
Consequently, $F$ contains a vertex $w$ that represents such an edge $e$. Let
$v_{\ell,j_{\ell}}$ denote the other endpoint of $e$. Then
$N_{G^{\prime}}(w)\supseteq U_{i^{*},j^{*}}\cup U_{\ell,j_{\ell}}$, and by
Claim 9(5) we therefore have $U_{\ell,j_{\ell}}\subseteq C$.

Applying the previous argument for all $\ell\in[k]\setminus\\{i^{*}\\}$,
together with the fact that $U_{i^{*},j^{*}}\subseteq C$, we find that for
each $i\in[k]$ there exists a value $j_{i}$ such that $U_{i,j_{i}}\subseteq
C$. Since $|C|\leq k(k-1)$ while each such set $U_{i,j_{i}}$ has size $k-1$,
it follows that the choice of $j_{i}$ is uniquely determined for each
$i\in[k]$, and that there are no other vertices in $C$. To complete the proof,
we argue that the set $S=\\{v_{i,j_{i}}\mid i\in[k]\\}$ is a clique in $G$.

Consider an arbitrary pair of distinct vertices
$v_{i,j_{i}},v_{i^{\prime},j_{i^{\prime}}}$ in $S$, and choose the indices
such that $i<i^{\prime}$. We argue that $G$ contains an edge $e$ between these
vertices, as follows. Since $u_{i,j_{i},i^{\prime}}\in U_{i,j_{i}}\subseteq
C$, by Observation A.3 the graph $G^{\prime}[\\{u_{i,j_{i},i^{\prime}}\\}\cup
F]$ contains a cycle. As argued above, the construction of $G^{\prime}$ and
the fact that $F\subseteq W$ ensure that this cycle consists of
$u_{i,j_{i},i^{\prime}}$ joined to a vertex in $F$ by a double-edge. By Step 3
and the fact that $i<i^{\prime}$, this vertex is of the form $w_{e}$ for an
edge $e$ in $G$ connecting $v_{i,j_{i}}$ to a vertex
$v_{i^{\prime},j^{\prime}}$ in $V_{i^{\prime}}$. By construction of
$G^{\prime}$ we have $U_{i^{\prime},j^{\prime}}\subseteq
N_{G^{\prime}}(w_{e})$, and then $w_{e}\in F$ implies by Claim 9(5) that
$U_{i^{\prime},j^{\prime}}\subseteq C$. Since we argued above that for index
$i^{\prime}$ there is a unique choice $j_{i^{\prime}}$ with
$U_{i^{\prime},j_{i^{\prime}}}\subseteq C$, we must have
$j^{\prime}=j_{i^{\prime}}$. Hence the vertex $w_{e}$ contained in $F$
represents the edge of $G$ between $v_{i,j_{i}}$ and
$v_{i^{\prime},j_{i^{\prime}}}$ in $G$, which proves in particular that the
edge exists. As the choice of vertices was arbitrary, this shows that $S$ is a
clique in $G$. As it contains exactly one vertex from each color class, graph
$G$ has a multicolored clique of size $k$.