Eindhoven University of Technology, The
Netherlandsb.m.p.jansen@tue.nlhttps://orcid.org/0000-0001-8204-1268[3cm]erc.pdfFunded
by the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No 803421, ReduceSearch).
Eindhoven University of Technology, The
<EMAIL_ADDRESS>by Project No. ICT22-029
of the Vienna Science Foundation (WWTF). Bart M. P. Jansen and Bart van der
Steenhoven [500]Theory of computation Parameterized complexity and exact
algorithms [500]Theory of computation Graph algorithms analysis
[500]Mathematics of computing Graph algorithms John 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

# Kernelization for Counting Problems on Graphs: Preserving the Number of
Minimum Solutions

Bart M. P. Jansen  Bart van der Steenhoven

###### Abstract

A kernelization for a parameterized decision problem $\mathcal{Q}$ is a
polynomial-time preprocessing algorithm that reduces any parameterized
instance $(x,k)$ into an instance $(x^{\prime},k^{\prime})$ whose size is
bounded by a function of $k$ alone and which has the same yes/no answer for
$\mathcal{Q}$. Such preprocessing algorithms cannot exist in the context of
counting problems, when the answer to be preserved is the number of solutions,
since this number can be arbitrarily large compared to $k$. However, we show
that for counting minimum feedback vertex sets of size at most $k$, and for
counting minimum dominating sets of size at most $k$ in a planar graph, there
is a polynomial-time algorithm that either outputs the answer or reduces to an
instance $(G^{\prime},k^{\prime})$ of size polynomial in $k$ with the same
number of minimum solutions. This shows that a meaningful theory of
kernelization for counting problems is possible and opens the door for future
developments. Our algorithms exploit that if the number of solutions exceeds
$2^{\mathrm{poly}(k)}$, the size of the input is exponential in terms of $k$
so that the running time of a parameterized counting algorithm can be bounded
by $\mathrm{poly}(n)$. Otherwise, we can use gadgets that slightly increase
$k$ to represent choices among $2^{\mathcal{O}(k)}$ options by only
$\mathrm{poly}(k)$ vertices.

###### keywords:

kernelization, counting problems, feedback vertex set, dominating set,
protrusion decomposition

###### category:

##  1 Introduction

#### Background and motivation.

Counting problems, whose answer is an integer giving the number of objects of
a certain kind rather than merely yes or no, have important applications in
fields of research such as artificial intelligence [27, 28], statistical
physics [20, 23, 35] and network science [25]. They have been studied
extensively in classical complexity, underpinning fundamental results such as
Toda’s theorem [33] and the #P-completeness of the permanent [34]. A
substantial research effort has targeted the parameterized complexity of
counting problems, leading to parametric complexity-notions like
#W[1]-hardness [9, 13, 24] and FPT algorithms to solve several counting
problems. For example, FPT algorithms were developed to count the number of
size-$k$ vertex covers [12], or the number of occurrences of a size-$k$
pattern graph $H$ in a host graph $G$ [10].

This paper is concerned with an aspect of parameterized algorithms which has
been largely neglected for counting problems: that of efficient preprocessing
with performance guarantees, i.e., kernelization. A kernelization for a
parameterized decision problem $\mathcal{Q}$ is a polynomial-time
preprocessing algorithm that reduces any parameterized instance $(x,k)$ into
an instance $(x^{\prime},k^{\prime})$ whose size is bounded by a function of
$k$ alone and which has the same yes/no answer for $\mathcal{Q}$. Over the
last decade, kernelization has developed into an important subfield of
parameterized algorithms, as documented in a textbook dedicated to the topic
[14]. Given the success of kernelization for decision problems, one may
wonder: can a theory of provably-efficient preprocessing for counting problems
be developed?

Consider a prototypical problem such as Feedback Vertex Set in undirected
graphs, in which the goal is to find a small vertex set whose removal breaks
all cycles. What could be an appropriate notion of counting kernelization for
such a problem? The concept of efficient preprocessing towards a provably
small instance with the same answer could be instantiated as follows: given a
pair $(G,k)$, the preprocessing algorithm should output a pair
$(G^{\prime},k^{\prime})$ whose size is bounded by a function of $k$ such that
the number of size-$k$ feedback vertex sets in $G$ is equal to the number of
size-$k^{\prime}$ feedback vertex sets in $G^{\prime}$. However, this task is
clearly impossible. Given a graph consisting of a length-$n$ cycle with
parameter $k=1$, the number of solutions is $n$ which can be arbitrarily large
compared to $k$, while for any reduced instance $(G^{\prime},k^{\prime})$ of
size bounded in $k$, the number of solutions can be at most
$2^{|V(G^{\prime})|}\leq f(k)$. Without allowing the size of the reduced
instance to depend on $n$, it seems that preprocessing while preserving the
answer to the counting problem is impossible.

Over the years, there have been two approaches to deal with this obstacle111A
third [22] approach was announced shortly before this paper went to print; it
allows a polynomial-time lifting step to compute the number of solutions to
the original instance from the number of solutions to the reduced instance..
Thurley [32], inspired by concepts in earlier work [26], proposed a notion of
counting kernelization which effectively reduces a counting problem to an
enumeration problem. He considered problems such as Vertex Cover and
$d$-Hitting Set. In his framework, the preprocessing algorithm has to output
an instance of size bounded by a function of $k$, in such a way that for any
solution to the reduced instance, we can efficiently determine to how many
solutions of the original instance it corresponds. Hence by enumerating _all_
solutions on the reduced instance, we can obtain the number of solutions to
the original instance. A significant drawback of this approach therefore lies
in the fact that to solve the counting problem on the original instance, we
have to enumerate all solutions on the reduced instance. Since counting can
potentially be done much faster than enumeration, it is not clear that this
preprocessing step is always beneficial.

A second notion for counting kernelization was proposed by Kim, Selma, and
Thilikos [21, 30]. Their framework (which also applies to Feedback Vertex Set)
considers two types of algorithms: a _condenser_ that maps an input instance
$(G,k)$ to an instance $(G^{\prime},k^{\prime})$ of an auxiliary _annotated_
problem involving weights on the vertices of $G^{\prime}$, and an _extractor_
that recovers (typically not in polynomial time) the number of solutions to
$(G,k)$ from the weighted instance $(G^{\prime},k^{\prime})$. The number of
vertices of $G^{\prime}$ is required to be bounded in $k$, but the weights are
allowed to be arbitrarily large, thereby sidestepping the issue described
above. This means that in terms of the total encoding size, the weighted graph
$(G^{\prime},k^{\prime})$ is not guaranteed to be smaller than $(G,k)$ and in
general the total number of bits needed to encode the weighted graph cannot be
bounded by a function of $k$ alone. The condenser-extractor framework has the
same drawback as the framework by Thurley: a standard counting problem is
reduced to a more complicated type of problem, in this case one involving
weights and annotations.

The goal of this paper is to show that there is an alternative way to overcome
the obstacle for counting kernelization, which leads to a notion of
preprocessing in which the problem to be solved on the reduced instance is of
exactly the same nature as the original. Our solution is inspired by the
typical behavior of kernelization algorithms for decision problems: we
formalize the option of already finding the answer during the preprocessing
phase. Note that many algorithms, such as the famous Buss [7] kernelization
for Vertex Cover, work by applying reduction rules to arrive at the reduced
instance, or discover the yes/no answer to the decision problem during
preprocessing. Our kernelization algorithms for counting problems will have
the same behavior: they will either reduce to a $\mathrm{poly}(k)$-sized
instance of the same problem that has exactly the same answer to the counting
problem, or they outright answer the counting problem during their polynomial-
time computation. To our initial surprise, such preprocessing algorithms exist
for several classic problems.

#### Our results.

To begin the exploration of this new type of counting kernelization, we
revisit two prominent graph problems: Feedback Vertex Set in general
undirected graphs and Dominating Set in planar graphs. The decision versions
of these problems (does graph $G$ have a solution of size at most $k$?) have
kernels with $\mathcal{O}(k^{2})$ [19, 31] and $\mathcal{O}(k)$ vertices [1,
6, 16], respectively. We consider the problem of counting the number of
_minimum-size_ solutions, parameterized by the size $k$ of a minimum solution.
(We discuss counting inclusion-minimal solutions in the conclusion.) For a
graph $G$ and integer $k$, we denote by $\mathrm{\\#minFVS}(G,k)$ the number
of minimum feedback vertex sets in $G$ of size at most $k$ in $G$. Hence
$\mathrm{\\#minFVS}(G,k)$ is equal to $0$ if the feedback vertex number of $G$
exceeds $k$, and otherwise is equal to the number of minimum solutions. The
analogous concept for minimum dominating sets is denoted
$\mathrm{\\#minDS}(G,k)$. Our result for Feedback Vertex Set reads as follows.

######  Theorem 1.1.

There is a polynomial-time algorithm that, given a graph $G$ and integer $k$,
either

  * •

outputs $\mathrm{\\#minFVS}(G,k)$, or

  * •

outputs a graph $G^{\prime}$ and integer $k^{\prime}$ such that
$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k^{\prime})$ and
$|V(G^{\prime})|=\mathcal{O}(k^{5})$ and $k^{\prime}=\mathcal{O}(k^{5})$.

For Dominating Set on planar graphs, we give an analogous algorithm that
either outputs $\mathrm{\\#minDS}(G,k)$ or reduces to a _planar_ instance
$(G^{\prime},k^{\prime})$ with $|V(G^{\prime})|,k^{\prime}=\mathcal{O}(k^{3})$
such that $\mathrm{\\#minDS}(G,k)=\mathrm{\\#minDS}(G^{\prime},k^{\prime})$.
Hence if the parameter is small, the task of counting the number of minimum
solutions can efficiently be reduced to the _same_ counting task on a provably
small instance.

The high-level approach is the same for both problems. We use insights from
existing kernels for the decision version of the problem to reduce an input
instance $(G,k)$ into one $(G^{\prime},k^{\prime})$ with the same number of
minimum solutions, such that $G^{\prime}$ can be decomposed into a “small”
core together with $\mathrm{poly}(k)$ “simply structured but potentially
large” parts. For Dominating Set, this takes the form of a protrusion
decomposition; for Feedback Vertex Set the decomposition is more elementary.
Then we consider two cases. If $|V(G)|>2^{k}$, we employ an FPT algorithm
running in time $2^{\mathcal{O}(k)}\cdot\mathrm{poly}(n)$ to count the number
of minimum solutions and output it. Since $n>2^{k}$, this step runs in
polynomial time. If $|V(G)|\leq 2^{k}$, then we show that each of the
$\mathrm{poly}(k)$ simply structured parts can be replaced with a gadget of
size $\mathrm{poly}(k)$ without affecting the number of minimum solutions. In
this step, we typically increase the size of minimum solutions slightly to
allow a small vertex set to encode exponentially many potential solutions. For
example, an instance of Feedback Vertex Set consisting of a cycle of length
$2^{10}$ (which has $2^{10}$ different optimal solutions), can be reduced to
the graph consisting of $10$ pairs $(a_{i},b_{i})$, each pair connected by two
parallel edges. The latter graph also has $2^{10}$ minimum solutions, each of
size $10$. To carry out this approach, the most technical part is to show how
to decompose the input instance into parts in which it is easy to analyze how
many different choices an optimal solution can make.

#### Organization.

The remainder of the paper is structured as follows. After presenting
preliminaries in Section 2, we illustrate our approach for Feedback Vertex Set
in Section 3. The more technical application to Dominating Set on planar
graphs is given in Section 4. We conclude in Section 5 with a reflection on
the potential of this approach to counting kernelization.

##  2 Preliminaries

###  2.1 Graphs

All graphs we consider are undirected; they may have parallel edges but no
self-loops. A graph $G$ therefore consists of a set $V(G)$ of vertices and a
multiset $E(G)$ of edges of the form $\\{u,v\\}$ for distinct $u,v\in V(G)$.
For a vertex $v\in V(G)$, we refer to the _open neighborhood_ of $v$ in $G$ as
$N_{G}(v)$ and to the _closed neighborhood_ of $v$ as $N_{G}[v]$. For a set of
vertices $X\subseteq V(G)$, the open and closed neighborhoods are defined as
$N_{G}(X)=(\bigcup_{v\in X}N_{G}(v))\setminus X$ and $N_{G}[X]=\bigcup_{v\in
X}N_{G}[v]$. The degree of vertex $v$ in graph $G$, denoted by $\deg_{G}(v)$,
is equal to the number of edges incident to $v$ in $G$. We refer to the
subgraph of $G$ induced by a vertex set $X\subseteq V(G)$ as $G[X]$. We use
$G-X$ as a way to write $G[V(G)\setminus X]$ and $G-v$ as a shorthand for
$G-\\{v\\}$. A graph $H$ is a _minor_ of $G$ if $H$ can be formed by
contracting edges of a subgraph of $G$.

A graph is _planar_ if it can be embedded in the plane in such a way that its
edges intersect only at their endpoints. Such an embedding is called a _planar
embedding_ of $G$. We make use of the following two properties of planar
graphs.

######  Theorem 2.1 (Wagner’s theorem).

A graph $G$ is planar if and only if $G$ contains neither $K_{5}$ nor
$K_{3,3}$ as a minor.

######  Lemma 2.2 ([17, Lemma 13.3]).

Let $G$ be a planar graph, $C\subseteq V(G)$, and let $N_{3}$ be a set of
vertices from $V(G)\setminus C$ such that every vertex from $N_{3}$ has at
least three neighbors in $C$. Then, $|N_{3}|\leq\max\\{0,2|C|-4\\}$.

A _feedback vertex set_ of a graph $G$ is a set $S\subseteq V(G)$ such that
$G-S$ is a forest, i.e., acyclic. The _feedback vertex number_ of a graph is
the size of a smallest feedback vertex set of that graph. A _dominating set_
of a graph $G$ is a set $D\subseteq V(G)$ such that $N_{G}[D]=V(G)$. The
_domination number_ of a graph is the size of a smallest dominating set of
that graph. We say that a set $X\subseteq V(G)$ dominates $U\subseteq V(G)$ if
$U\subseteq N_{G}[X]$.

We define $V_{\neq 2}(G)$ to be the set of vertices of graph $G$ that do not
have degree two. We refer to a _chain_ $C$ of $G$ as a connected component of
$G-V_{\neq 2}(G)$. We say that a chain $C$ is a _proper chain_ if
$N_{G}(C)\neq\emptyset$ and we then refer to $N_{G}(C)$ as the _endpoints_ of
$C$.

###  2.2 Tree decompositions

For completeness we give the definition of a tree decomposition, which is
needed to formally define the notion of protrusion below.

######  Definition 2.3 (Tree decomposition).

A tree decomposition of a graph $G$ is a pair $(T,\chi)$, where $T$ is a
rooted tree and $\chi$ assigns a bag $\chi(w)\subseteq V(G)$ to every $w\in
V(T)$ such that the following conditions are satisfied.

  * •

$\bigcup_{w\in V(T)}\chi(w)=V(G)$.

  * •

For all $\\{u,v\\}\in E(G)$, there exists a node $w\in V(T)$ such that
$\\{u,v\\}\subseteq\chi(w)$.

  * •

For every $v\in V(G)$, the set $\\{w\in V(T)\mid v\in\chi(w)\\}$ induces a
non-empty connected subtree of $T$.

The _width_ of a tree decomposition is $\max_{w\in V(T)}|\chi(w)|-1$. The
_treewidth_ of a graph $G$, denoted by $\mathrm{tw}(G)$, is the minimum
possible width of a tree decomposition of $G$. For a node $w$ of $T$, we
define $T_{w}$ to be the subtree of $T$ rooted at $w$. For a subtree
$T^{\prime}$ of $T$, we define $\chi(T^{\prime}):=\bigcup_{z\in
V(T^{\prime})}\chi(z)$.

###  2.3 Protrusion decompositions

The definitions concerning protrusion decompositions are based on those from
[17, §15].

######  Definition 2.4 (Boundary).

For a graph $G$ and a vertex subset $X\subseteq V(G)$, we refer to the
boundary of $X$ as $\partial(X)=\\{v\in X\mid N_{G}(v)\setminus
X\neq\emptyset\\}$.

######  Definition 2.5 (Protrusion).

For an integer $t>0$, a $t$-protrusion in a graph $G$ is a vertex set
$X\subseteq V(G)$ such that $\mathrm{tw}(G[X])\leq t$ and $|\partial(X)|\leq
t$.

######  Definition 2.6 (Protrusion decomposition).

For integers $\alpha$, $\beta$ and $t$, an $(\alpha,\beta,t)$-protrusion
decomposition of a graph $G$ is a tree decomposition $(T,\chi)$ of $G$ such
that the following conditions are satisfied.

  * •

The tree $T$ is a rooted tree with root $r$ and $|\chi(r)|\leq\alpha$.

  * •

For every $v\in V(T)$ except $r$, we have $|\chi(v)|\leq t$.

  * •

The root $r$ has degree at most $\beta$ in $T$.

Following this definition, observe that for each child $w$ of $r$ in $T$, we
have that $\chi(T_{w})$ is a $t$-protrusion in $G$. For such a protrusion, we
observe that $\partial(\chi(T_{w}))\subseteq\chi(w)$ and we additionally
define $\partial^{*}(\chi(T_{w}))=\chi(w)$ to be the _extended boundary_ of
protrusion $\chi(T_{w})$.

######  Definition 2.7 (Treewidth modulator).

A set $S\subseteq V(G)$ is a treewidth-$\eta$-modulator in a graph $G$ if
$\mathrm{tw}(G-S)\leq\eta$.

######  Lemma 2.8.

There is a polynomial-time algorithm that, given a planar graph $G$ and a
treewidth-$\eta$-modulator $S$ in $G$, computes an
$(\alpha,\beta,t)$-protrusion decomposition $(T,\chi)$ such that the following
conditions are satisfied.

  * •

For the root $r$ of $T$ we have $S\subseteq\chi(r)$.

  * •

For each child $w$ of $r$ in $T$, the set $\chi(T_{w})$ is a $t$-protrusion in
$G$ such that $\chi(T_{w})\cap S\subseteq\partial^{*}(\chi(T_{w}))$ and
${|\partial^{*}(\chi(T_{w}))\cap S|\leq 2}$.

  * •

$\alpha=\mathcal{O}(\eta|S|)$, $\beta=\mathcal{O}(\eta|S|)$ and $t=3\eta+2$.

The lemma above corresponds with Lemma 15.14 of [17] with the addition of the
second property. This property follows from the proofs of Lemma 15.13 and
Lemma 15.14 in [17].

##  3 Counting feedback vertex sets

In this section, we explain the technique that allows us to either count the
number of minimum feedback vertex sets of a graph $G$ in polynomial time, or
reduce $G$ to a provably small instance with the same number of minimum
solutions. We start by showing that, by using a few reduction rules, we can
already reduce $G$ to an equivalent instance with a specific structure. This
reduction is based on the $\mathcal{O}(k^{3})$-vertex kernel for the decision
Feedback Vertex Set problem presented by Jansen [4]. We choose to use this
kernel over the better-known and smaller-size kernels by Thomassé [31] and
Iwata [19] because those rely on multiple reduction rules that are not safe
for counting minimum solutions.

As is common for Feedback Vertex Set, we consider the graph we are working
with to be undirected and we allow parallel edges. In this section, we make
use of two reduction rules which are common for kernels of the decision
variant of Feedback Vertex Set.

(R1)

If there is an edge of multiplicity larger than two, reduce its multiplicity
to two.

(R2)

If there is a vertex $v$ with degree at most one, remove $v$.

It can easily be verified that if an instance $(G,k)$ is reduced to
$(G^{\prime},k^{\prime})$ by one of the rules above, we have
$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k^{\prime})$. Hence,
these rules are safe in the context of counting minimum feedback vertex sets.
Observe that if (R2) has exhaustively been applied on a graph $G$, then all
vertices in $V_{\neq 2}(G)$ have degree at least three. For our purposes, we
will need one more method to reduce the graph. We first present a lemma that
motivates this third reduction rule.

######  Lemma 3.1.

Let $X$ be a (not necessarily minimum) feedback vertex set of a graph $G$ that
is reduced with respect to (R2) and let $\mathcal{C}$ be the set of connected
components of $G-V_{\neq 2}(G)$. Then:

$|V_{\neq 2}(G)|\leq|X|+\sum_{v\in X}\deg_{G}(v)$, and

$|\mathcal{C}|\leq|X|+2\sum_{v\in X}\deg_{G}(v)$.

######  Proof 3.2.

Consider the forest $F:=G-X$. Partition the vertices of $V_{\neq 2}(G)\cap
V(F)=V_{\neq 2}(G)\setminus X$ into sets $V^{\prime}_{\leq 1}$,
$V^{\prime}_{2}$ and $V^{\prime}_{\geq 3}$ for vertices that have respectively
degree at most one, degree two or degree at least three in $F$. Furthermore,
let $V_{\ell}$ denote the leaf nodes of $F$ that have degree two in $G$. Since
$G$ has no vertices of degree at most one by (R2), the leaves of $F$ are
exactly the vertices $V_{\ell}\cup V^{\prime}_{\leq 1}$. In any tree, the
number of vertices of degree at least three is less than the number of leaves,
thus $|V^{\prime}_{\geq 3}|\leq|V^{\prime}_{\leq 1}|+|V_{\ell}|$. Each vertex
in $V^{\prime}_{2}$ has at least one edge to $X$ since they have degree at
least three in $G$ and degree exactly two in $F$. For a similar reason, each
vertex in $V^{\prime}_{\leq 1}$ has at least two edges to $X$. Each vertex in
$V_{\ell}$ has one edge to $X$. Putting this together gives the following
inequality, from which (3.1) directly follows.

$\displaystyle\sum_{v\in X}\deg_{G}(v)\geq|V^{\prime}_{2}|+2|V^{\prime}_{\leq
1}|+|V_{\ell}|\geq|V^{\prime}_{2}|+|V^{\prime}_{\leq 1}|+|V^{\prime}_{\geq
3}|=|V_{\neq 2}(G)\setminus X|$ (1)

To bound the size of the set $\mathcal{C}$ of connected components of
$G-V_{\neq 2}(G)$, we instead bound the size of the set $\mathcal{C^{\prime}}$
of connected components of $G-V_{\neq 2}(G)-X$. Observe that
$|\mathcal{C}|\leq|\mathcal{C^{\prime}}|+|X|$ since removing a vertex from a
graph reduces the number of connected components by at most one. (Such a
removal can _increase_ the number of components by an arbitrary number, which
is irrelevant for our argument.) Since $X$ is an FVS, the connected components
in $\mathcal{C^{\prime}}$ can be seen as proper chains. Chains in
$\mathcal{C^{\prime}}$ that have both endpoints in $F$ act as edges between
those endpoints when it comes to the connectivity of $F$. This means that,
since $F$ is a forest, there can be at most $|V_{\neq 2}(G)\cap
V(F)|\leq\sum_{v\in X}\deg_{G}(v)$ of such chains by Equation 1. All other
chains will have at least one endpoint in $X$, which means there can be at
most $\sum_{v\in X}\deg_{G}(v)$ of them, implying (3.1).

Based on 3.1, the goal of the third reduction rule is to decrease the degree
of the vertices of a feedback vertex set. This idea is captured in 3.3. After
presenting this lemma, we combine these results in 3.5 to create an algorithm
to reduce a graph $G$ to an, in context of counting minimum feedback vertex
sets, equivalent graph with a bounded number of vertices of degree other than
two and a bounded number of chains.

######  Lemma 3.3.

There exists a polynomial-time algorithm that, given a graph $G$ reduced with
respect to (R1), an integer $k$, a vertex $v\in V(G)$ and a feedback vertex
set $Y_{v}\subseteq V(G)\setminus\\{v\\}$ of $G$, outputs a graph $G^{\prime}$
obtained by removing edges from $G$ such that
$\deg_{G^{\prime}}(v)\leq|Y_{v}|\cdot(k+4)$ and
$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k)$.

######  Proof 3.4.

Consider forest $F:=G-(Y_{v}\cup\\{v\\})$. For each $u\in Y_{v}$, mark trees
of $F$ that have an edge to both $v$ and $u$ until either all such trees are
marked or at least $k+2$ of them are marked. Then, we construct a graph
$G^{\prime}$ from $G$ by removing all edges between $v$ and trees of $F$ that
were not marked.

We shall first prove the bound on the degree of $v$ in $G^{\prime}$. The
vertex $v$ can have edges to vertices in $Y_{v}$ or in $F$. Since (R1) has
been exhaustively applied, there can be at most $2|Y_{v}|$ edges between $v$
and $Y_{v}$. Each tree in $F$ has at most one edge to $v$, since otherwise
$Y_{v}$ would not be an FVS of $G$. In $G^{\prime}$, only trees that were
marked still have an edge to $v$, and since we mark at most $k+2$ trees per
vertex in $Y_{v}$, we have at most $|Y_{v}|\cdot(k+2)$ of such trees.
Combining this gives $\deg_{G^{\prime}}(v)\leq|Y_{v}|\cdot(k+4)$.

To show that $\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k)$, we
prove that a vertex set $X\subseteq V(G)$ with $|X|\leq k$ is an FVS of $G$ if
and only if it is an FVS of $G^{\prime}$. Clearly any FVS of $G$ is an FVS of
$G^{\prime}$ since $G^{\prime}$ is constructed from $G$ by deleting edges. For
the opposite direction, assume that $X$ is an FVS of $G^{\prime}$ and assume
for a contradiction that $X$ is not an FVS of $G$. Then $G-X$ has a cycle $W$.
This cycle must contain an edge $\\{v,w\\}$ of $E(G)\setminus E(G^{\prime})$
since $G^{\prime}-X$ is acyclic. By construction of $G^{\prime}$, we know that
$w$ is a vertex that belongs to an unmarked tree $T$. Since cycle $W$
intersects $T$ and since $T$ is a connected component of
$G-(Y_{v}\cup\\{v\\})$, there must be a vertex $u\in Y_{v}$ that has an edge
to $T$. Since the edge between $v$ and $T$ is removed in $G^{\prime}$, there
exist $k+2$ other trees that are marked and have an edge to both $v$ and $u$.
Since $|X|\leq k$, at least two of these trees are not hit by $X$.
Furthermore, since $v$ and $u$ are part of $W$, they are also not contained in
$X$. Therefore, there is a cycle in $G^{\prime}-X$ through $v$, $u$ and two of
the aforementioned trees, contradicting that $X$ is an FVS of $G^{\prime}$.

######  Lemma 3.5.

There is a polynomial-time algorithm that, given a graph $G$ and integer $k$,
outputs a graph $G^{\prime}$ and integer $k^{\prime}$ such that the following
properties are satisfied.

  * •

$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k^{\prime})$.

  * •

$k^{\prime}\leq k$.

  * •

$|V_{\neq 2}(G^{\prime})|=\mathcal{O}(k^{3})$.

  * •

$G^{\prime}-V_{\neq 2}(G^{\prime})$ has $\mathcal{O}(k^{3})$ connected
components.

######  Proof 3.6.

In our approach, we make use of the linear-time 4-approximation algorithm by
Bar-Yehuda et al. [3] that can also approximate the more general problem of:
for a given graph, find the smallest FVS that does not contain a given vertex.
Our first step is to exhaustively apply (R1) on $G$ and compute a
4-approximate FVS $X$ of the graph. If $|X|>4k$ then the feedback vertex
number of $G$ is larger than $k$, so we can return a trivial, constant size
instance $G^{\prime}$ and $k^{\prime}$ such that
$\mathrm{\\#minFVS}(G^{\prime},k^{\prime})=0$. Otherwise, let $G^{\prime}$ and
$k^{\prime}$ be a copy of $G$ and $k$. For each vertex $v\in X$, compute a
4-approximate FVS $Y_{v}$ of $G^{\prime}$ that does not contain $v$. If
$|Y_{v}|>4k$, then there does not exist a solution of size at most $k$ that
does not contain $v$, so remove $v$ from $G^{\prime}$ and reduce $k^{\prime}$
by one. Otherwise, use 3.3 to reduce the degree of $v$ in $G^{\prime}$.
Finally, we exhaustively apply reduction rule (R2) on $G^{\prime}$.

Computing the 4-approximations and applying the reduction rules can be done in
polynomial time. Each rule can only be applied a polynomial number of times,
thus the algorithm runs in polynomial time. The fact that
$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k^{\prime})$ follows
from safety of the reduction rules used in the algorithm and $k^{\prime}\leq
k$ follows from the fact that $k^{\prime}$ is never increased. We know that
$|V_{\neq 2}(G^{\prime})|=\mathcal{O}(k^{3})$ and that $G^{\prime}-V_{\neq
2}(G^{\prime})$ has $\mathcal{O}(k^{3})$ connected components due to 3.1 and
the following bound:

$\sum_{v\in X}\deg_{G^{\prime}}(v)\leq\sum_{v\in
X}|Y_{v}|\cdot(k+4)\leq\sum_{v\in X}4k\cdot(k+4)=|X|\cdot
4k\cdot(k+4)=\mathcal{O}(k^{3}).$

The result of 3.5 is in and of itself not a proper kernel yet, since the
chains of the graph it produces can be of arbitrary length. Our strategy to
address this is as follows. If these chains are large in terms of $k$, then we
can run an FPT algorithm in $\mathrm{poly}(n)$ time to count the number of
minimum solutions. Otherwise, the chains can be replaced by structures of size
$\mathrm{poly}(k)$ that do not change the number of minimum feedback vertex
sets the instance has. This approach is captured in the following two lemmas
and combined in the proof of Theorem 1.1.

######  Lemma 3.7.

There exists a polynomial-time algorithm that, given a graph $G$ with a chain
$C$ and an integer $k$, outputs a graph $G^{\prime}$ obtained from $G$ by
replacing $C$ with a vertex set $C^{\prime}$, and an integer $k^{\prime}$,
such that:

  * •

$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k^{\prime})$,

  * •

$G-C=G^{\prime}-C^{\prime}$,

  * •

$N_{G}(C)=N_{G^{\prime}}(C^{\prime})$,

  * •

$|C^{\prime}|=\mathcal{O}(\log(|C|)^{2})$, and

  * •

$k^{\prime}=k+\mathcal{O}(\log(|C|)^{2})$.

######  Proof 3.8.

In case $C$ is a proper chain, the endpoints are defined as $N_{G}(C)$. If $C$
is not a proper chain, which happens if $C$ is a cycle in $G$, we choose an
arbitrary vertex of $C$ to act as its endpoint. For simplicity, we consider
$C$ to have two endpoints, where in some cases these two endpoints might be
the same vertex.

First, we assume that the number of vertices of the chain, not including its
endpoints, is a power of two, i.e. $|C|=2^{p}$ for some integer $p$. Let
$v,u\in V(G)$ be the endpoints of $C$ (possibly $v=u$) and let
$C=\\{c_{0},c_{1},\cdots,c_{2^{p}-1}\\}$. Then we construct our graph
$G^{\prime}$ by replacing $C$ by a gadget $C^{\prime}$, of which an example
can be seen in Figure 1. It consists of the following elements.

  * •

A vertex $w$ with edges to both $v$ and $u$.

  * •

Pairs of vertices $a_{i},b_{i}$ for $0\leq i<p$ such that there is an edge of
multiplicity two between $w$ and $a_{i}$ and between $a_{i}$ and $b_{i}$.

Additionally, we set $k^{\prime}=k+p$.

(a)

(b)

Figure 1: (1(a)) A chain structure of size eight with two endpoints. (1(b))
The replacement of the structure. An example of the mapping $f$ is also
illustrated through the vertices with a thicker border.

We shall now prove that
$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{\prime},k^{\prime})$. To this
end, we define a mapping $f$ from the set of minimum feedback vertex sets of
$G$ to those of $G^{\prime}$ and show that this is a bijection, which
immediately implies that the two sets have the same cardinality. For a natural
number $m$, define $\mathrm{bin}(m)$ to be the binary representation of $m$ on
$p$ bits and define $\mathrm{bin}(m)_{i}$ to be the $i$’th least significant
bit of $\mathrm{bin}(m)$.

$f(X)=\begin{cases}X\cup\\{a_{i}\mid 0\leq i<p\\}&\mbox{if }X\cap
C=\emptyset\\\ \\\ (X\setminus C)\cup\\{w\\}\cup\\{a_{i}\mid 0\leq
i<p\wedge\mathrm{bin}(m)_{i}=0\\}\\\ \cup\\{b_{i}\mid 0\leq
i<p\wedge\mathrm{bin}(m)_{i}=1\\}&\mbox{if }X\cap C=\\{c_{m}\\}\\\
\end{cases}$

As a first observation, note that for any minimum feedback vertex set $X$ of
$G$, we have $|X\cap C|\leq 1$ as picking any one vertex from $C$ will already
break all cycles that go through the chain.

######  Claim 1.

If a set $X$ is a minimum FVS of $G$, then $f(X)$ is a minimum FVS of
$G^{\prime}$.

We prove this in two parts. First we prove that $f(X)$ is an FVS of
$G^{\prime}$ and then we prove that $f(X)$ is indeed an FVS of $G^{\prime}$ of
minimum size.

To prove that $f(X)$ is an FVS of $G^{\prime}$, we use a proof by
contradiction. Assume $f(X)$ is not an FVS of $G^{\prime}$, in which case a
(simple) cycle $W$ exists in $G^{\prime}-f(X)$. This cycle must intersect
$C^{\prime}$ as $X\setminus C=f(X)\setminus C^{\prime}$ and
$G-C=G^{\prime}-C^{\prime}$ thus $G-C-X=G^{\prime}-C^{\prime}-f(X)$, which
means $W$ would otherwise also exist in $G-X$, contradicting that $X$ is an
FVS of $G$. The cycle $W$ cannot contain a $b_{j}$ vertex since by definition
of $f$, for $0\leq i<p$, either $a_{i}$ or $b_{i}$ is in $f(X)$, which would
either mean $b_{j}$ is isolated in $G^{\prime}-f(X)$ or is removed. Also, $W$
can not contain any $a_{j}$ vertex as, by definition of $f$, if $a_{j}$ is not
in $f(X)$, then both its neighbors $w$ and $b_{j}$ are in $f(X)$. This leaves
only the option that $W$ intersects $C^{\prime}$ through only vertex $w$. This
means that $W-\\{w\\}$ contains a path from $v$ to $u$ in
$G^{\prime}-f(X)-\\{w\\}$. However, since as mentioned before
$G-C-X=G^{\prime}-C^{\prime}-f(X)$, this same path also exists in $G-X$.
Furthermore, since $w\notin f(X)$, that must mean that $X\cap C=\emptyset$ so
$(W\setminus\\{w\\})\cup C$ would form a cycle in $G-X$ contradicting that $X$
is an FVS of $G$.

Next we prove that $f(X)$ is a minimum FVS of $G^{\prime}$. Assume for sake of
a contradiction that $f(X)$ is not a minimum FVS of $G^{\prime}$ due to the
existence of a $Y\subseteq V(G^{\prime})$ with $|Y|<|f(X)|$ such that $Y$ is
an FVS of $G^{\prime}$. We first observe that any FVS of $G^{\prime}$ contains
at least $p$ vertices from $C^{\prime}$ since all $p$ of the pairs
$(a_{i},b_{i})$ form vertex disjoint cycles. Similarly so, if an FVS of
$G^{\prime}$ contains $w$, then it contains at least $p+1$ vertices from
$C^{\prime}$. We distinguish two cases.

Case $w\notin Y$:

Then $Y\setminus C^{\prime}$ is an FVS of $G$. If $G-(Y\setminus C^{\prime})$
would contain a cycle, then there would also exist a cycle in $G^{\prime}-Y$
since $G-C=G^{\prime}-C^{\prime}$ and both graphs $G-(Y\setminus C^{\prime})$
and $G^{\prime}-Y$ have a $vu$ path, the former through $C$ and the latter
through $w$. Furthermore, $|Y\setminus
C^{\prime}|\leq|Y|-p<|f(X)|-p=|X|+p-p=|X|$, contradicting that $X$ is a
minimum FVS of $G$.

Case $w\in Y$:

Then $X^{\prime}:=(Y\setminus C^{\prime})\cup\\{c_{j}\\}$ is an FVS of $G$ for
any $0\leq j<2^{p}$. If this were not the case, then, since $X^{\prime}$
contains a chain vertex, a cycle would need to exist completely in
$G-C-X^{\prime}$ which is the same graph as $G^{\prime}-C^{\prime}-Y$. This
would contradict $Y$ being an FVS of $G^{\prime}$. Furthermore,
$|X^{\prime}|\leq|Y|-(p+1)+1<|f(X)|-p=|X|+p-p=|X|$, contradicting that $X$ is
a minimum FVS of $G$.

As both cases lead to a contradiction, we conclude that $f(X)$ is a minimum
FVS of $G^{\prime}$.

######  Claim 2.

The function $f$ is bijective.

We first argue that $f$ is injective. Let $X$ and $X^{\prime}$ be two minimum
feedback vertex sets of $G$ such that $X\neq X^{\prime}$. That means
$X\setminus C\neq X^{\prime}\setminus C$ or $X\cap C\neq X^{\prime}\cap C$.
The former immediately allows us to conclude that $f(X)\neq f(X^{\prime})$
since $X\setminus C=f(X)\setminus C^{\prime}$ and $X^{\prime}\setminus
C=f(X^{\prime})\setminus C^{\prime}$. In the second case, we have two options.
The first is that $X\cap C=\\{c_{j}\\}$ and $X^{\prime}\cap C=\\{c_{m}\\}$ for
some $j\neq m$, and since binary representations are unique, they lead to
different sets $f(X)$ and $f(X^{\prime})$. The second option is that either
$X$ or $X^{\prime}$ contains no vertex from $C$ while the other one does. Then
only one of $f(X)$ or $f(X^{\prime})$ contains $w$ and the other one does not,
so $f(X)\neq f(X^{\prime})$.

It remains to show that $f$ is surjective. To this end, we take an arbitrary
minimum FVS $Y$ of $G^{\prime}$ and show that there exists a minimum FVS $X$
of $G$ such that $Y=f(X)$. We distinguish two cases:

Case $w\notin Y$:

For this case, first observe that $\\{a_{i}\mid 0\leq i<p\\}\subseteq Y$ since
otherwise $w$ would form a cycle with one of these $a_{i}$ vertices in $G-Y$.
Furthermore, $b_{i}\notin Y$ for $0\leq i<p$ since $Y$ already contains
$a_{i}$, leaving $b_{i}$ isolated in $G-Y$ and thus a redundant choice for a
minimum FVS. From this we can conclude that $Y\cap C^{\prime}=\\{a_{i}\mid
0\leq i<p\\}$. Therefore, taking $X:=Y\setminus C^{\prime}$ would give
$f(X)=Y$. We have already argued in case $w\notin Y$, that $Y\setminus
C^{\prime}$ is an FVS of $G$. To show that it is a minimum FVS of $G$, note
that if there was an $X^{\prime}\subseteq V(G)$, $|X^{\prime}|<|X|$ such that
$X^{\prime}$ is an FVS of $G$, then $f(X^{\prime})$ is an FVS of $G^{\prime}$
and $|f(X^{\prime})|=|X^{\prime}|+p<|X|+p=|Y\setminus
C^{\prime}|+p=|Y|-p+p=|Y|$ which would contradict $Y$ being a minimum FVS of
$G^{\prime}$.

Case $w\in Y$:

For this case, we instead observe that for each pair $\\{a_{i},b_{i}\\}$,
exactly one of $\\{a_{i},b_{i}\\}$ is in $Y$, as otherwise $Y$ would not be an
FVS of minimum size. Since there are $p$ of such pairs, there is a unique
value $0\leq j<2^{p}$ such that the binary representation of $j$ corresponds
to the choice of $a$ and $b$ vertices in $Y$. We can then choose
$X:=(Y\setminus C^{\prime})\cup\\{c_{j}\\}$. We clearly have that $f(X)=Y$.
Also, we have already shown before that $X$ is an FVS of $G$ and the argument
that $X$ is a minimum FVS of $G$ is analogous to that in case $w\notin Y$.

From this reasoning we can conclude that $f$ is a bijective function from the
set of minimum feedback vertex sets of $G$ to the set of minimum feedback
vertex sets of $G$.

In the argument above, we assumed that the length of the chain is a power of
two. We can address this by noting that any natural number can be written as a
sum of unique powers of two. Similarly, we can decompose the chain $C$ into a
number of subpaths each having a number of vertices that is a unique power of
two. We can then apply the replacement described above on each subpath
individually to get multiple replacement structures in a chain between the
endpoints of $C$. As seen before, the size of the replacement is linear in the
exponent of the length of the chain. In the worst case, when expressing $|C|$
in binary as a sum of distinct powers of two, the exponents of these powers
sum up to $\mathcal{O}(\log(|C|)^{2})$, which is also the bound on the number
of vertices used in our replacement and on the increase in the parameter
value.

We remark for 3.7 that a similar chain replacement gadget without parallel
edges can be constructed, at the expense of a linear increase in the size of
the gadget.

By adapting the iterative compression algorithm by Cao et al. [8] for the
decision Feedback Vertex Set problem, we can derive the following lemma. Its
proof is given in Appendix A.

######  Lemma 3.9.

There is an algorithm that, given a graph $G$ and integer $k$, computes
$\mathrm{\\#minFVS}(G,k)$ in $2^{\mathcal{O}(k)}\cdot\mathrm{poly}(n)$ time.

See 1.1

######  Proof 3.10.

First we use the algorithm from 3.5 to find a graph $G^{*}$ and integer
$k^{*}\leq k$ such that
$\mathrm{\\#minFVS}(G,k)=\mathrm{\\#minFVS}(G^{*},k^{*})$, $|V_{\neq
2}(G^{*})|=\mathcal{O}(k^{3})$ and $G^{*}-V_{\neq 2}(G^{*})$ has
$\mathcal{O}(k^{3})$ connected components (chains). Then, if there is a chain
of size larger than $2^{k}$, we can run the algorithm from 3.9 to compute
$\mathrm{\\#minFVS}(G^{*},k^{*})$ in $\mathrm{poly}(n)$ time since $n>2^{k}$.
Otherwise, all chains of $G^{*}$ have size at most $2^{k}$ and we can use 3.7
on $G^{*}$ to find a graph $G^{\prime}$ and integer $k^{\prime}$ such that:

  * •

$\mathrm{\\#minFVS}(G^{\prime},k^{\prime})=\mathrm{\\#minFVS}(G^{*},k^{*})=\mathrm{\\#minFVS}(G,k)$,

  * •

$|V(G^{\prime})|=\mathcal{O}(k^{3})+\mathcal{O}(k^{3}\cdot\log(2^{k})^{2})=\mathcal{O}(k^{5})$,
and

  * •

$k^{\prime}=\mathcal{O}(k+k^{3}\cdot\log(2^{k})^{2})=\mathcal{O}(k^{5})$.

##  4 Counting dominating sets in planar graphs

In this section, we show how our approach can also be used with a different
technique. In section 3 we adapted a decision kernel and replaced remaining,
potentially large structures by smaller, similarly behaving structures. In
this section we will instead focus on protrusion decompositions and the
reduction of protrusions.

We consider the problem of counting minimum dominating sets of a planar graph.
In the context of dominating sets, we assume all graphs to be undirected and
simple, so they do not have parallel edges. We start by showing that if a
planar graph $G$ has a dominating set of size at most $k$, we can use this to
find a protrusion decomposition.

######  Lemma 4.1.

Let $G$ be a planar graph and $k$ an integer. If $G$ has a dominating set of
size at most $k$, then $G$ has an
$(\mathcal{O}(k),\mathcal{O}(k),8)$-protrusion decomposition $(T,\chi)$ with
root $r$ of $T$ such that, for each child $w$ of $r$, the set of vertices
$\chi(T_{w})\setminus\partial(\chi(T_{w}))$ can be dominated by at most two
vertices in $\partial^{*}(\chi(T_{w}))=\chi(w)$. Moreover, there is a
polynomial-time algorithm that, given $G$ and $k$, either finds such a
protrusion decomposition or determines that the domination number of $G$ is
greater than $k$.

######  Proof 4.2.

The decision version of Dominating Set on planar graphs admits a polynomial-
time approximation scheme [2]. As a first step, we can use this to find a
2-approximate dominating set $S$ of $G$ in polynomial time. If $|S|>2k$ then
the domination number of $G$ is greater than $k$, so we are done. Otherwise,
in case $G$ is connected, we can turn $S$ into a connected dominating set
$S^{\prime}$ of $G$ such that $|S^{\prime}|\leq 3|S|\leq 6k$ [17, Claim
15.10]. If $G$ is not connected, we can do the same for each connected
component of the graph. Since $G$ is a planar graph, $G-S^{\prime}$ is an
outerplanar graph and thus has treewidth at most two [5, Lemma 78]. This means
that $S^{\prime}$ is a treewidth-2-modulator for $G$. Therefore, we can use
2.8 to find in polynomial time an
$(\mathcal{O}(k),\mathcal{O}(k),8)$-protrusion decomposition that satisfies
the described requirements.

We call a vertex set $C\subseteq V(G)$ a _wide diamond_ if there are distinct
vertices $v,u\in V(G)\setminus C$ such that for all $c\in C$, we have that
$N_{G}(c)=\\{v,u\\}$. We consider $v$ and $u$ to be the endpoints of the wide
diamond $C$. We make the following observation concerning minimum dominating
sets on wide diamonds. If $C$ is a wide diamond with distinct endpoints $v,u$
in a graph $G$ and $|C|\geq 3$, then any minimum dominating set $X$ of $G$
satisfies the following properties.

  1. 1.

$X\cap\\{v,u\\}\neq\emptyset$, since if $X$ contains neither $v$ nor $u$, we
must have that $C\subseteq X$, while $(X\setminus C)\cup\\{v,u\\}$ would then
be a dominating set of smaller size.

  2. 2.

If $\\{v,u\\}\subseteq X$, then $X\cap C=\emptyset$, since $N_{G}[c]\subseteq
N_{G}[\\{v,u\\}]$ for all $c\in C$.

  3. 3.

$|X\cap C|\leq 1$, since by Property 1, we can assume w.l.o.g. that $v\in X$,
and $N_{G}[c]\setminus N_{G}[v]=\\{u\\}$ for all $c\in C$.

In 4.3 we show how we can efficiently replace a wide diamond by a smaller,
similarly behaving structure. We show how to use this replacement to reduce
the protrusions of a protrusion decomposition in 4.5.

######  Lemma 4.3.

There exists a polynomial-time algorithm that, given a planar graph $G$ with a
wide diamond $C$ and an integer $k$, outputs a planar graph $G^{\prime}$
obtained from $G$ by replacing $C$ with a vertex set $C^{\prime}$, and an
integer $k^{\prime}$, such that:

  * •

$\mathrm{\\#minDS}(G,k)=\mathrm{\\#minDS}(G^{\prime},k^{\prime})$,

  * •

$G-C=G^{\prime}-C^{\prime}$,

  * •

$N_{G}(C)=N_{G^{\prime}}(C^{\prime})$,

  * •

$|C^{\prime}|=\mathcal{O}(\log(|C|)^{2})$, and

  * •

$k^{\prime}=k+\mathcal{O}(\log(|C|)^{2})$.

######  Proof 4.4.

Let vertices $v$ and $u$ be the endpoints of the wide diamond $C$. Assume
without loss of generality that $C$ consists of at least five vertices, since
the statement is trivial otherwise. For simplicity, we first assume that
$|C|=2^{p}+3$ for some integer $p$, so let
$C=\\{c_{0},c_{1},\cdots,c_{2^{p}+2}\\}$. We then construct $G^{\prime}$ from
$G$ by replacing $C$ by $C^{\prime}$, which has the following structure. In
$C^{\prime}$, we leave three vertices $c_{0},c_{1},c_{2}$ from $C$ untouched
and replace all others.

  * •

Add vertex $x_{v}$ with an edge to $v$ and vertex $x_{u}$ with an edge to $u$.

  * •

For each $0\leq i<p$, add two adjacent vertices $a_{i}$ and $b_{i}$ and make
these vertices adjacent to both $x_{v}$ and $x_{u}$.

  * •

Add a degree-one vertex $e_{i}$ adjacent to $b_{i}$.

It is easy to see that $G^{\prime}$ is planar since the constructed gadget has
a planar embedding with its only boundary vertices $x_{v},x_{u}$ on a single
face (see Figure 2). The gadget can be drawn into any face of an embedding of
$G$ that contains both $u$ and $v$, whose existence is guaranteed because
$N_{G}(c_{0})=\\{v,u\\}$. For the parameter, we set $k^{\prime}=k+p$.

(a) (b)

Figure 2: (2(a)) A wide diamond structure with endpoints. (2(b)) The
replacement of the structure.

We define a function $f$ from the set of minimum dominating sets of $G$ to the
set of minimum dominating sets of $G^{\prime}$ and we prove that
$\mathrm{\\#minDS}(G,k)=\mathrm{\\#minDS}(G^{\prime},k^{\prime})$ by showing
that $f$ is a well-defined, bijective function.

$f(X)=\begin{cases}X\cup\\{b_{i}\mid 0\leq i<p\\}&\mbox{if }X\cap
C\subseteq\\{c_{0},c_{1},c_{2}\\}\\\ \\\ (X\setminus
C)\cup\\{x_{u}\\}\cup\\{b_{i}\mid 0\leq i<p\wedge\mathrm{bin}(m-3)_{i}=0\\}\\\
\cup\\{e_{i}\mid 0\leq i<p\wedge\mathrm{bin}(m-3)_{i}=1\\}&\mbox{if }X\cap
C=\\{c_{m}\\}\wedge m\geq 3\wedge v\in X\\\ \\\ (X\setminus
C)\cup\\{x_{v}\\}\cup\\{b_{i}\mid 0\leq i<p\wedge\mathrm{bin}(m-3)_{i}=0\\}\\\
\cup\\{e_{i}\mid 0\leq i<p\wedge\mathrm{bin}(m-3)_{i}=1\\}&\mbox{if }X\cap
C=\\{c_{m}\\}\wedge m\geq 3\wedge u\in X\end{cases}$

Note that since we assumed $|C|\geq 5$, by 4.2 the function $f$ covers all
cases for a minimum DS $X$ of $G$. Also note that $\\{c_{0},c_{1},c_{2}\\}$
still forms a wide diamond of size at least three between $v$ and $u$, so the
properties of the observation still apply in $G^{\prime}$.

######  Claim 3.

If a set $X$ is a minimum DS of $G$, then $f(X)$ is a minimum DS of
$G^{\prime}$.

We prove this claim in two parts. We first prove that $f(X)$ is a DS of
$G^{\prime}$, and then we prove that it is a DS of minimum size.

To prove that $f(X)$ is a DS of $G^{\prime}$, we use a proof by contradiction,
so assume $f(X)$ is not a DS of $G^{\prime}$. This means there is a vertex
$w\in V(G^{\prime})$ that is not dominated by $f(X)$. If $w$ is a vertex of
$G^{\prime}-C^{\prime}-\\{v,u\\}$, then since $G^{\prime}-C^{\prime}=G-C$, we
have that $w$ is also a vertex of $G-C-\\{v,u\\}$. Furthermore, since
$X\setminus C=f(X)\setminus C^{\prime}$ and $N_{G}(C)=\\{v,u\\}$, if $w$ is
not dominated by $f(X)$ it is also not dominated by $X$, which contradicts $X$
being a dominating set of $G$. Thus $w\in C^{\prime}$ or $w\in\\{v,u\\}$. The
former can never be true, as in all cases the function $f$ takes the union
over a dominating set of $C^{\prime}\setminus\\{c_{0},c_{1},c_{2}\\}$ and by
Property 1 of 4.2, either $v$ or $u$ is in $X$, and thus also in $f(X)$,
ensuring that $c_{0},c_{1}$ and $c_{2}$ are dominated. So, assume without loss
of generality that $w=u$. Then, by Property 1 of 4.2, that means $v\in X$ and
since $u$ is dominated by $X$ in $G$ that $X\cap C=\\{c_{m}\\}$ for some
$c_{m}$. However, by definition of $f$, that would mean that either $c_{m}\in
f(X)$ or $x_{u}\in f(X)$ and both $c_{m}$ and $x_{u}$ have an edge to $u$
which contradicts that $u$ is not dominated by $f(X)$. Thus $f(X)$ is a
dominating set of $G^{\prime}$.

We also use a proof by contradiction to show that $f(X)$ is a minimum DS of
$G^{\prime}$. Assume that $f(X)$ is not a minimum DS of $G^{\prime}$ due to
the existence of a set $Y\subseteq V(G^{\prime})$ with $|Y|<|f(X)|$ such that
$Y$ is a dominating set of $G^{\prime}$. Assume that $Y$ is a minimum such
dominating set. We distinguish three cases:

Case $x_{v},x_{u}\notin Y$:

We can then show that $\\{b_{i}\mid 0\leq i<p\\}\subseteq Y$. If there would
be a $b_{j}\notin Y$, then since also $x_{v},x_{u}\notin Y$, we would need to
have that $a_{j},e_{j}\in Y$ since these are the only remaining options to
dominate these vertices. However, since
$N_{G^{\prime}}[\\{a_{j},e_{j}\\}]=N_{G^{\prime}}[b_{j}]$, taking
$(Y\setminus\\{a_{j},e_{j}\\})\cup\\{b_{j}\\}$ would result a dominating set
of smaller cardinality, contradicting that $Y$ is a minimum dominating set of
$G^{\prime}$. Thus $\\{b_{i}\mid 0\leq i<p\\}\subseteq Y$. From this it
follows that $Y^{\prime}:=Y\setminus\\{b_{i}\mid 0\leq i<p\\}$ is a dominating
set of $G$. We already have $v\in Y$ or $u\in Y$ by Property 1 of 4.2,
ensuring that all vertices in $C$ are dominated. Also, since
$x_{v},x_{u}\notin Y$, the set $Y$ dominates $u$ and $v$ from
$V(G)\setminus(C\setminus\\{c_{0},c_{1},c_{2}\\})$. Furthermore,
$|Y^{\prime}|=|Y|-p<|f(X)|-p=|X|+p-p=|X|$, contradicting that $X$ is a minimum
DS of $G$.

Case $x_{v}\in Y$:

As a first step, we can realize that $v\notin Y$. If $v$ would be in $Y$, then
we could construct a DS of $G^{\prime}$ of smaller size than $Y$ by taking
$(Y\setminus C^{\prime})\cup\\{b_{i}\mid 0\leq i<p\\}$ (potentially also
including $x_{u}$ if $x_{u}\in Y$). Thus, $v\notin Y$ which by Property 1 of
4.2 implies that $u\in Y$. Knowing this, we consider $Y^{\prime}:=(Y\setminus
C^{\prime})\cup\\{c_{j}\\}$ for some $0\leq j<2^{p}+3$. This set $Y^{\prime}$
is a dominating set of $G$ since all vertices $G-C-\\{v,u\\}$ are unaffected
by the change, $u\in Y^{\prime}$ which ensures all vertices $c_{i}$ are
dominated, and $c_{j}\in Y^{\prime}$ ensuring that $v$ is dominated. Notice
that $|Y\cap C^{\prime}|\geq p+1$ since $x_{v}\in Y$ and $Y$ must contain
either $e_{i}$ or $b_{i}$ for each $0\leq i<2^{p}$ in order to dominate
$e_{i}$. Thus, $|Y^{\prime}|\leq|Y|-(p+1)+1=|Y|-p<|f(X)|-p=|X|+p-p=|X|$,
contradicting that $X$ is a minimum DS of $G$.

Case $x_{u}\in Y$:

The argument for this case is symmetric to that of the previous case.

In all cases we reach a contradiction from which we can conclude that $f(X)$
is a minimum DS of $G^{\prime}$. From this we can conclude that $f$ is a well-
defined mapping from the set of minimum dominating sets of $G$ to those of
$G^{\prime}$.

######  Claim 4.

The function $f$ is bijective.

The function $f$ is clearly injective as when $X\neq X^{\prime}$, either
$X\setminus C\neq X^{\prime}\setminus C$ or $X\cap C\neq X^{\prime}\cap C$
which both imply that $f(X)\neq f(X^{\prime})$ by definition of $f$. Following
the same type of argumentation as in 3, it is easy to verify the following.
For any minimum dominating set $Y^{\prime}$ in $G^{\prime}$, if we define $Y$
as follows:

$Y=\begin{cases}Y^{\prime}\setminus\\{b_{i}\mid 0\leq i<p\\}&\mbox{if
}Y^{\prime}\cap\\{x_{v},x_{u}\\}=\emptyset\\\ (Y^{\prime}\setminus
C^{\prime})\cup\\{c_{j}\\}&\mbox{if
}Y^{\prime}\cap\\{x_{v},x_{u}\\}\neq\emptyset\end{cases}$

then $Y$ is a minimum DS of $G$ and $f(Y)=Y^{\prime}$ for the correct choice
of $j$, which is determined by which $b$ and $e$ vertices are in $Y^{\prime}$.
Thus the function is surjective, and therefore also a bijection.

Similar as for counting feedback vertex sets, we can address the issue that we
assumed $|C|=2^{p}+3$ for some $p$ by decomposing the wide diamond $C$ into
multiple smaller wide diamonds such that one consists of three vertices and
all others consist of a number of vertices that is a unique power of two. In
order for the complete structure to get the behavior we desire, it suffices to
not replace the one wide diamond consisting of three vertices to let this act
as $c_{0},c_{1},c_{2}$ in the replacement procedure for all other
replacements. We then replace all other wide diamonds entirely in the way
described above. This allows us to replace any wide diamond $C$ by a structure
with $\mathcal{O}(\log(|C|)^{2})$ vertices, and
$k^{\prime}=k+\mathcal{O}(\log(|C|)^{2})$.

######  Lemma 4.5.

There is a polynomial-time algorithm that, given a planar graph $G$, an
integer $k$ and a protrusion $P\subseteq V(G)$ such that $P=\chi(T_{w})$ for
some $(\alpha,\beta,8)$-protrusion decomposition $(T,\chi)$ with root $r$ and
child of root $w$ and such that $P\setminus\partial(P)$ can be dominated by a
set of at most two vertices in $\partial^{*}(P)$, outputs a planar graph
$G^{\prime}$ obtained from $G$ by replacing $P$ with a vertex set
$P^{\prime}$, and integer $k^{\prime}$, such that:

  * •

$\mathrm{\\#minDS}(G,k)=\mathrm{\\#minDS}(G^{\prime},k^{\prime})$,

  * •

$G-(P\setminus\partial^{*}(P))=G^{\prime}-(P^{\prime}\setminus\partial^{*}(P))$,

  * •

$N_{G}(P)=N_{G^{\prime}}(P^{\prime})$,

  * •

$|P^{\prime}|=\mathcal{O}(\log(|P|)^{2})$, and

  * •

$k^{\prime}=k+\mathcal{O}(\log(|P|)^{2})$.

######  Proof 4.6.

The proof is structured as follows. We will first remove certain edges and
vertices in the protrusion that are not relevant in the context of dominating
sets. We then prove that the remaining protrusion can only have
$\mathcal{O}(1)$ vertices that are not part of a wide diamond. Finally, we use
4.3 to replace the wide diamond structures that appear in this remaining
protrusion.

Consider a minimum dominating set $S$ of $G$. The first thing we note is that
$S$ contains at most $8$ vertices from $P$. This is because $\partial^{*}(P)$
is a dominating set of $P$ with $|\partial^{*}(P)|\leq 8$ and for all
$D\subseteq P$, we have that $N_{G}[D]\subseteq N_{G}[\partial^{*}(P)]$. Thus,
if $S$ would contain more than $8$ vertices of $P$, then $(S\setminus
P)\cup\partial^{*}(P)$ would be a dominating set of $G$ of smaller size,
contradicting that $S$ is a minimum dominating set. Additionally, we note that
the vertex set $S\cap P$ dominates $P\setminus\partial(P)$, which follows
directly from the definition of a boundary. We shall refer to a set
$D\subseteq P$ as a _partial dominating set_ (PDS) of $P$ if $D$ dominates
$P\setminus\partial(P)$. Based on these observations, the goal of our
reduction is to preserve these partial dominating sets of size at most 8.

The first step will be to remove redundant edges between vertices of
$P\setminus\partial^{*}(P)$. More formally, an edge $\\{v,u\\}$ with $v,u\in
P\setminus\partial^{*}(P)$ is called _redundant_ if for each partial
dominating set $D$ of $P$ of size at most 8, the set $D$ is still a partial
dominating set of $P$ in graph $G$ when we remove edge $\\{v,u\\}$. We can
check if an edge is redundant by enumerating the set of partial dominating
sets of $P$ of size at most 8 in $\mathrm{poly}(n)$ time and checking if
removing the edge changes this set. Next, we remove certain vertices from
$P\setminus\partial^{*}(P)$ using the following observation. If there is a
vertex $v\in V(G)$ with more than two neighbors of degree one, then all
minimum dominating sets of $G$ will contain $v$ and none of those degree-one
neighbors. Therefore, removing all but two of the degree-one neighbors does
not affect the set of minimum dominating sets of $G$. After we have removed
redundant edges from $P$, we use this observation to remove unnecessary
degree-one vertices from $P\setminus\partial^{*}(P)$.

Assume now that we used the techniques described above to remove edges and
vertices from $P$. We can analyze the structure that the remaining graph
$G[P]$ has by counting the types of vertices that appear in it. We first
consider one specific case.

If $\partial^{*}(P)=\\{s\\}$ for some vertex $s$, then we can always find a
replacement $P^{\prime}$ for $P$ that has only a constant number of vertices.
For this, we first realize that in this specific case, any minimum dominating
set $S$ of $G$ contains at most one vertex from $P$. Therefore, $S$ can only
contain a vertex from $P$ that dominates all vertices in
$P\setminus\partial(P)$. If $P\setminus\partial(P)=\emptyset$ then $P$ already
has constant size, so assume that this is not the case. Let $U$ be the set of
vertices of $P\setminus\partial^{*}(P)$ that individually form a partial
dominating set of $P$. If $U=\emptyset$, then, since
$P\setminus\partial(P)\neq\emptyset$, any minimum dominating set of $G$ must
contain $s$. Thus we can let $P^{\prime}$ consist of only $s$ and two new
vertices, both having only an edge to $s$. If $U\neq\emptyset$, then we
construct $P^{\prime}$ from $P$ by removing all vertices other than $s$ and
those in $U$. There can be at most three vertices in $U$, since otherwise
$G[U\cup\\{s\\}]$ would form $K_{5}$, which would contradict $G$ being planar
by Theorem 2.1. To see why this reduction is safe, note that for any minimum
dominating set $S$ of $G$, we must have that $S\cap P=\\{v\\}$ for some vertex
$v\in U\cup\\{s\\}$. If $|S\cap P|>1$, then $S$ is not of minimum size, and if
$v\notin U\cup\\{s\\}$, then there is a vertex in $P\setminus\partial(P)$ not
dominated by $S$.

From this point on, assume $|\partial^{*}(P)|>1$ and let $s_{1},s_{2}$ be two
distinct vertices in $\partial^{*}(P)$ that together dominate
$P\setminus\partial(P)$. We partition the vertices of
$P\setminus\partial^{*}(P)$ into sets $P_{\leq 1}$, $P_{2}$ and $P_{\geq 3}$
based on whether their degree in $G[P]$ is at most one, is two, or is at least
three, respectively. We first look at $P_{\leq 1}$. Note that there cannot
exist vertices of degree zero since $\\{s_{1},s_{2}\\}$ is a partial
dominating set of $P$, thus all vertices of $P\setminus\partial^{*}(P)$ must
have an edge to at least one of these. Similarly, for vertices of degree one,
the one edge incident to them must have as other endpoint either $s_{1}$ or
$s_{2}$. There cannot be more than two degree-one neighbors per vertex, since
then we would have removed them previously. From this we can conclude that
$|P_{\leq 1}|\leq 4$.

Before we look at $P_{\geq 3}$, we will first prove the following claim to be
correct. This claim will in turn be useful for bounding the number of vertices
contained in $P_{\geq 3}$.

######  Claim 5.

If $P$ has no redundant edges, then for each distinct pair of vertices
$z_{1},z_{2}\in P$, there can be at most $96$ vertices in
$(N_{G[P]}(z_{1})\cap N_{G[P]}(z_{2}))\setminus\partial(P)$ that are adjacent
to at least one vertex in $P\setminus(\partial(P)\cup\\{z_{1},z_{2}\\})$.

Let $R\subseteq(N_{G[P]}(z_{1})\cap N_{G[P]}(z_{2}))\setminus\partial(P)$ be
the set of vertices that are adjacent to both $z_{1}$ and $z_{2}$ and at least
one vertex in $P\setminus(\partial(P)\cup\\{z_{1},z_{2}\\})$. Assume for a
contradiction that $|R|>96$. We first prove that all partial dominating sets
of size at most 8 of $P$ must contain at least one of $\\{z_{1},z_{2}\\}$. If
this were not the case, then there exists a partial dominating set $S$ with
$|S|\leq 8$ such that $z_{1},z_{2}\notin S$. All vertices in $R$ must be
dominated by $S$, so there is a vertex $v\in S$ that dominates more than
$96/8=12$ vertices of $R$. This means that $v$ has an edge to more than $11$
vertices in $R$. However, then $v$, $z_{1}$, $z_{2}$ and three of those
vertices of $R$ adjacent to $v$ would together form $K_{3,3}$, which
contradicts $G$ being planar by Theorem 2.1. Thus, each PDS of size at most
$8$ must contain $z_{1}$ or $z_{2}$.

We associate a vertex from $P\setminus(\partial(P)\cup\\{z_{1},z_{2}\\})$ to
each vertex of $R$ through a function $f\colon R\to
P\setminus(\partial(P)\cup\\{z_{1},z_{2}\\})$, where for each vertex $v\in R$,
we let $f(v)$ be an arbitrary vertex in
$N_{G[P]}(v)\setminus(\partial(P)\cup\\{z_{1},z_{2}\\})$. Next, let
$f(R):=\\{f(v)\mid v\in R\\}$ be the set of vertices of
$P\setminus(\partial(P)\cup\\{z_{1},z_{2}\\})$ that are associated to some
vertex of $R$. See 3(a) for an example of the vertices involved in the
structure under consideration. No vertex in $f(R)$ has an edge to both $z_{1}$
and $z_{2}$, since then all edges from $R$ to that vertex would have been
redundant due to $z_{1}$ or $z_{2}$ being in every partial dominating set of
size at most 8. We then claim that no vertex $v\in
V(G)\setminus\\{z_{1},z_{2}\\}$ is adjacent to three vertices of $f(R)$. For a
proof by contradiction, assume that $v$ is adjacent to three distinct vertices
$f(a),f(b),f(c)\in f(R)$. Then this would contradict $G$ being planar due to
it containing $K_{3,3}$ as a minor. One side of the minor consists of
$\\{z_{1},z_{2},v\\}$, and the other side consists of the vertices obtained by
contracting the edges $\\{a,f(a)\\}$, $\\{b,f(b)\\}$ and $\\{c,f(c)\\}$.

Furthermore, each vertex in $f(R)$ can be the image of at most two vertices of
$R$. If there were distinct $a,b,c\in R$ such that $f(a)=f(b)=f(c)$, then
$\\{z_{1},z_{2},f(a)\\}$ and $\\{a,b,c\\}$ would together form $K_{3,3}$.
Thus, since $|R|>96$, we must have $|f(R)|>48$. Each vertex in $f(R)$ is non-
adjacent to at least one of $\\{z_{1},z_{2}\\}$, so at least half of them are
non-adjacent to the same one. Assume without loss of generality that at least
half of them, so more than $24$, are non-adjacent to $z_{1}$. Let $U$ refer to
this set of vertices. Then $z_{2}$ must be in all partial dominating sets of
$P$ of size at most 8. If this were not the case, then there would need to be
a vertex $v\in V(G)\setminus\\{z_{1},z_{2}\\}$ that dominates more than
$24/8=3$ of these vertices in $U\subseteq f(R)$, which we already argued to be
impossible. Thus $z_{2}$ is contained in all partial dominating sets of $P$ of
size at most 8. This leaves two options. Either $z_{2}$ has no edge to any
vertex of $U$, in which case no partial dominating set of size at most $8$
exists, which is a contradiction as is witnessed by the partial dominating set
$\partial^{*}(P)$. As a second option, $z_{2}$ has an edge to at least one
vertex $f(u)\in U$, which would imply that the edge between $u$ and $f(u)$ is
redundant, which is also a contradiction. As all cases lead to a
contradiction, we must have that $|R|\leq 96$.

Having proven this claim, we shall now consider $P_{\geq 3}$, which we
partition further into sets $Q_{1}$, $Q_{2}$ and $Q_{\geq 3}$ based on whether
they have one, two, or at least three edges to $\partial^{*}(P)$,
respectively. We will prove that $P_{\geq 3}$ has constant size by proving
that all three of these sets have constant size. We can immediately conclude
that $|Q_{\geq 3}|=\mathcal{O}(1)$ using 2.2 since $G[P]$ is planar, each
vertex in $Q_{\geq 3}$ has at least three neighbors in $\partial^{*}(P)$ by
definition, and $|\partial^{*}(P)|\leq 8$.

(a) (b)

Figure 3: (3(a)) An example of the types of vertices involved in the proof of
5. (3(b)) An example of the types of vertices involved in the proof of 7.

######  Claim 6.

The set $Q_{2}$ consists of at most $28\cdot 96$ vertices.

The set $Q_{2}$ consists of the vertices of $P\setminus\partial^{*}(P)$ that
have degree at least three in $G[P]$ and have exactly two edges to
$\partial^{*}(P)$. Thus, all vertices of $Q_{2}$ exist between a pair of
$\partial^{*}(P)$ vertices. Consider an arbitrary pair of distinct vertices
$z_{1},z_{2}\in\partial^{*}(P)$. Then, since by definition each vertex in
$Q_{2}$ has an edge to at least one vertex not in $\partial^{*}(P)$, we can
use 5 to conclude that $|Q_{2}\cap N_{G[P]}(z_{1})\cap N_{G[P]}(z_{2})|\leq
96$. Since there are at most $\binom{8}{2}=28$ pairs of $\partial^{*}(P)$
vertices, we arrive at the bound stated in the claim.

######  Claim 7.

The set $Q_{1}$ consists of at most $2\cdot 8\cdot 96$ vertices.

The set $Q_{1}$ consists of the vertices of $P\setminus\partial^{*}(P)$ that
have degree at least three in $G[P]$ and have exactly one edge to
$\partial^{*}(P)$. Note that since $\\{s_{1},s_{2}\\}$ dominates the vertices
in $P\setminus\partial(P)$ (and thus also $P\setminus\partial^{*}(P)$), all
vertices in $Q_{1}$ have an edge to either $s_{1}$ or $s_{2}$ and no other
vertices in $\partial^{*}(P)$. To bound the number of vertices in $Q_{1}$, we
will bound the number of such vertices that can be adjacent to $s_{1}$, and
realize that that same bound applies for $s_{2}$. First observe that if all
partial dominating sets of size at most 8 contain both $s_{1}$ and $s_{2}$,
then all edges between vertices of $P\setminus\partial^{*}(P)$ would have been
redundant and we would immediately have that $|Q_{1}|=0$, so assume that this
is not the case. We shall prove that $|Q_{1}\cap N_{G[P]}(s_{1})|\leq 8\cdot
96$ using a proof by contradiction, so assume $|Q_{1}\cap
N_{G[P]}(s_{1})|>8\cdot 96$. We distinguish two cases.

Case:

There exists a partial dominating set of size at most 8 that does not contain
$s_{1}$. That means that all vertices in $N_{G[P]}(s_{1})\setminus\partial(P)$
can be dominated with at most 8 vertices other than $s_{1}$. Since $|Q_{1}\cap
N_{G[P]}(s_{1})|>8\cdot 96$ there must be a vertex $v\in
P\setminus\partial^{*}(P)$ that has an edge to more than $96$ vertices in
$Q_{1}\cap N_{G[P]}(s_{1})$. Since the vertices in $Q_{1}$ have degree at
least three, they must all have an edge to at least one vertex in
$P\setminus(\partial^{*}(P)\cup\\{v\\})$. This means we can use 5 to conclude
that $|Q_{1}\cap N_{G[P]}(s_{1})\cap N_{G[P]}(v)|\leq 96$, which contradicts
our assumption.

Case:

All partial dominating sets of $P$ of size at most 8 contain $s_{1}$. Note
that this means that there is a partial dominating set $S$ with $|S|\leq 8$
that does not contain $s_{2}$, since we assumed that not all partial
dominating sets of size at most 8 contain both $s_{1}$ and $s_{2}$. In this
case, the vertices in $Q_{1}\cap N_{G[P]}(s_{1})$ all have exclusively edges
to vertices that do not have an edge to $s_{1}$ but do have an edge to
$s_{2}$, since otherwise the edge would be redundant or $\\{s_{1},s_{2}\\}$
would not dominate the vertex. See 3(b) for an example of the vertices
involved in such a structure. We can find that
$|N_{G[P]}(s_{2})|\geq|Q_{1}\cap N_{G[P]}(s_{1})|>8\cdot 96$. This follows
from the fact that each vertex in $Q_{1}\cap N_{G[P]}(s_{1})$ has at least two
edges to vertices in $N_{G[P]}(s_{2})$ and that each vertex $v\in
N_{G[P]}(s_{2})$ can have an edge to at most two vertices in $Q_{1}\cap
N_{G[P]}(s_{1})$. If $v$ has edges to three vertices in $Q_{1}\cap
N_{G[P]}(s_{1})$, then $v,s_{1},s_{2}$ and those three vertices would form
$K_{3,3}$ when we contract the edges between $s_{2}$ and
$N_{G[P]}(s_{2})\setminus\\{v\\}$. In a similar vein, any vertex in $S$ can
have an edge to at most two of these vertices in $N_{G[P]}(Q_{1}\cap
N_{G[P]}(s_{1}))\cap N_{G[P]}(s_{2})$ due to planarity and thus can dominate
at most three of them. However, there are more than $8\cdot 3=24$ of such
vertices which contradicts $S$ being a partial dominating set of $P$.

In both cases we reach a contradiction, thus we must have that $|Q_{1}\cap
N_{G[P]}(s_{1})|\leq 8\cdot 96$. The same bound holds for the vertices of
$Q_{1}$ that are adjacent to $s_{2}$ through analogous reasoning, and since
$Q_{1}\subseteq N_{G[P]}(s_{1})\cup N_{G[P]}(s_{2})$, we must have that
${|Q_{1}|\leq 2\cdot 8\cdot 96=\mathcal{O}(1)}$.

Summarizing so far, we have shown that $|P_{1}|=\mathcal{O}(1)$ and $|P_{\geq
3}|=|Q_{1}|+|Q_{2}|+|Q_{\geq 3}|=\mathcal{O}(1)$. This only leaves $P_{2}$,
the vertices of degree two. All such vertices must have at least one edge to
$\partial^{*}(P)$ since it is a dominating set for $P$. There are a few
options for the other edge. It could have an edge to another vertex in $P_{2}$
which in turn has an edge to some vertex in $\partial^{*}(P)$. Let $P_{2}^{*}$
be the set of $P_{2}$ vertices involved in such a structure. If there were
three or more of such structures between a pair of vertices in
$\partial^{*}(P)$, then the edge between the degree two vertices would have
been redundant. Thus, since $|\partial^{*}(P)|=\mathcal{O}(1)$, also
$|P_{2}^{*}|=\mathcal{O}(1)$. Finally, consider the vertices of
$P_{2}\setminus P_{2}^{*}$. These are vertices of $P$ of degree two with both
neighbors in the set $\partial^{*}(P)\cup P_{\geq 3}$. The vertices of
$P_{2}\setminus P_{2}^{*}$ can be partitioned into $\mathcal{O}(1)$ wide
diamonds, namely the wide diamonds of the form $N_{G[P]}(x)\cap
N_{G[P]}(y)\cap P_{2}$ for $x,y\in\partial^{*}(P)\cup P_{\geq 3}$. Since
$|\partial^{*}(P)\cup P_{\geq 3}|=\mathcal{O}(1)$, we also end up with
$\mathcal{O}(1)$ wide diamonds. We can use 4.3 for each wide diamond to get a
replacement $P^{\prime}$ and $k^{\prime}$ that satisfy the requirements stated
in the lemma.

Having proven that we can reduce the size of these protrusions, we proceed
similarly to as for counting feedback vertex sets. We argue that there is an
algorithm that solves $\mathrm{\\#minDS}$ in 4.7 and combine all our results
in Theorem 4.9.

######  Lemma 4.7.

There is an algorithm that, given a planar graph $G$ and integer $k$, computes
$\mathrm{\\#minDS}(G,k)$ in $2^{\mathcal{O}(\sqrt{k})}\cdot\mathrm{poly}(n)$
time.

######  Proof 4.8 (Proof sketch).

There exists an algorithm that solves the decision version of Dominating Set
in $4^{\mathrm{tw}(G)}\cdot\mathrm{tw}(G)^{\mathcal{O}(1)}\cdot n$ time [11].
This algorithm can straightforwardly be adapted to also count the number of
minimum dominating sets without increasing the running time. Furthermore, note
that if $G$ has a dominating set of size at most $k$, then
$\mathrm{tw}(G)=\mathcal{O}(\sqrt{k})$ [17]. As a final ingredient, we use
that there exists a polynomial-time exact algorithm for branchwidth on planar
graphs [29], and that any branch decomposition of width $k$ can be turned into
a tree decomposition of width $\mathcal{O}(k)$ in polynomial time [18].
Putting this together results in an algorithm that can compute
$\mathrm{\\#minDS}(G,k)$ in the mentioned time.

######  Theorem 4.9.

There is a polynomial-time algorithm that, given a planar graph $G$ and
integer $k$, either

  * •

outputs $\mathrm{\\#minDS}(G,k)$, or

  * •

outputs a planar graph $G^{\prime}$ and integer $k^{\prime}$ such that
$\mathrm{\\#minDS}(G,k)=\mathrm{\\#minDS}(G^{\prime},k^{\prime})$ and
$|V(G^{\prime})|=\mathcal{O}(k^{3})$ and $k^{\prime}=\mathcal{O}(k^{3})$.

######  Proof 4.10.

First, we can use the algorithm from 4.1 on $G$ and $k$. If it reports that
the domination number of $G$ is greater than k, then
$\mathrm{\\#minDS}(G,k)=0$. Else, we find an
$(\mathcal{O}(k),\mathcal{O}(k),8)$-protrusion decomposition of $G$. If there
is a protrusion that consists of more than $2^{k}$ vertices, we know that
$n>2^{k}$ so we can run the algorithm from 4.7 to compute
$\mathrm{\\#minDS}(G,k)$ in $\mathrm{poly}(n)$ time. Otherwise, we know that
each protrusion consists of at most $2^{k}$ vertices. Applying 4.5 to all
protrusions gives us a graph $G^{\prime}$ with
$\mathcal{O}(k)+\mathcal{O}(k)\cdot\mathcal{O}(k^{2})=\mathcal{O}(k^{3})$
vertices and an integer
$k^{\prime}=k+\mathcal{O}(k)\cdot\mathcal{O}(k^{2})=\mathcal{O}(k^{3})$ such
that $\mathrm{\\#minDS}(G,k)=\mathrm{\\#minDS}(G^{\prime},k^{\prime})$.

##  5 Conclusion

We introduced a new model of kernelization for counting problems: a
polynomial-time preprocessing algorithm that either outputs the desired count,
or reduces to a provably small instance with the same answer. We showed that
for counting the number of minimum solutions of size at most $k$, a reduction
to a graph of size $\mathrm{poly}(k)$ exists for two classic problems.

We believe that the new viewpoint on counting kernelization facilitates a
general theory that can be explored for many problems beyond the ones
considered here. By following the textbook proof [11, Lemma 2.2] that a
decidable parameterized decision problem is fixed-parameter tractable if and
only if it admits a kernel (of potentially exponential size), it is easy to
show the following equivalence between fixed-parameter tractability of
counting problems and our notion of counting kernelization.

######  Lemma 5.1.

Let $\mathcal{P}\colon\Sigma^{*}\times\mathbb{N}\to\mathbb{N}$ be a computable
function for some finite alphabet $\Sigma$. Then the following two statements
are equivalent:

  1. 1.

There is a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and an
algorithm that, given an input $(x,k)\in\Sigma^{*}\times\mathbb{N}$, outputs
$\mathcal{P}(x,k)$ in time $f(k)\cdot|x|^{\mathcal{O}(1)}$.

  2. 2.

There is a computable function $f\colon\mathbb{N}\to\mathbb{N}$ and a
polynomial-time algorithm that, given $(x,k)\in\Sigma^{*}\times\mathbb{N}$,
either:

    1. (a)

outputs $\mathcal{P}(x,k)$, or

    2. (b)

outputs $(x^{\prime},k^{\prime})\in\Sigma^{*}\times\mathbb{N}$ satisfying
$|x^{\prime}|,k^{\prime}\leq f(k)$ and
$\mathcal{P}(x,k)=\mathcal{P}(x^{\prime},k^{\prime})$.

Hence our view of counting kernelization is generic enough to capture all
fixed-parameter tractable counting problems. Determining which counting
problems have a _polynomial-size_ kernel remains an interesting challenge.

In this work, we focused on counting _minimum-size_ solutions (of size at most
$k$). Apart from being of practical interest in several applications, this
facilitates several steps in the design and analysis of our preprocessing
algorithms. At present, we do not know whether the two considered problems
have polynomial-size kernels when counting the number of inclusion-minimal
solutions of size exactly $k$, or the number of (not necessarily minimal or
minimum) solutions of size exactly $k$; we leave this investigation to future
work. To see the importance of the distinction, observe that the number of
_minimum_ vertex covers of size at most $k$ in a graph is bounded by $2^{k}$
(since the standard 2-way branching discovers all of them) and the Buss kernel
preserves their count. But the total number of vertex covers of size at most
$k$ cannot be bounded in terms of $k$ in general.

For both problems we investigated, our preprocessing step effectively consists
of reducing to an equivalent instance composed of a small core along with
$\mathrm{poly}(k)$ simply structured parts, followed by replacing each such
part by a small problem-specific gadget. In the world of decision problems,
the theory of protrusion replacement [6, 15] gives a generic way of replacing
such simply-structured parts by gadgets. Similarly, the condenser-extractor
framework [21, 30] can be applied to generic problems as long as they can be
captured in a certain type of logic. This leads to the question of whether, in
our model of counting kernelization, the design of the gadgets can be
automated. Can a notion of meta-kernelization be developed for counting
problems?

## References

  * [1] Jochen Alber, Michael R. Fellows, and Rolf Niedermeier.  Polynomial-time data reduction for dominating set.  J. ACM, 51(3):363–384, 2004.  doi:10.1145/990308.990309.
  * [2] Brenda S. Baker.  Approximation algorithms for np-complete problems on planar graphs.  J. ACM, 41(1):153–180, 1994.
  * [3] Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, and Ron M. Roth.  Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference.  SIAM J. Comput., 27(4):942–959, 1998.
  * [4] Bart M. P. Jansen.  The power of preprocessing: Gems in kernelization.  https://www.win.tue.nl/~bjansen/talks/BonnGemsInKernelization.pptx, 2016\.
  * [5] Hans L. Bodlaender.  A partial _k_ -arboretum of graphs with bounded treewidth.  Theor. Comput. Sci., 209(1-2):1–45, 1998.
  * [6] 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.
  * [7] Jonathan F. Buss and Judy Goldsmith.  Nondeterminism within P.  SIAM J. Comput., 22(3):560–572, 1993.  doi:10.1137/0222038.
  * [8] Yixin Cao, Jianer Chen, and Yang Liu.  On feedback vertex set: New measure and new structures.  Algorithmica, 73(1):63–86, 2015.
  * [9] Radu Curticapean.  The simple, little and slow things count: on parameterized counting complexity.  Bull. EATCS, 120, 2016.  URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/445.
  * [10] Radu Curticapean, Holger Dell, and Dániel Marx.  Homomorphisms are a good basis for counting small subgraphs.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210–223. ACM, 2017.  doi:10.1145/3055399.3055502.
  * [11] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [12] Henning Fernau.  Parameterized algorithmics: A graph-theoretic approach.  PhD thesis, Habilitationsschrift, Universität Tübingen, Germany, 2005.
  * [13] Jörg Flum and Martin Grohe.  The parameterized complexity of counting problems.  SIAM J. Comput., 33(4):892–922, 2004.  doi:10.1137/S0097539703427203.
  * [14] Fedor Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization: theory of parameterized preprocessing.  Cambridge University Press, 2019.  doi:10.1017/9781107415157.
  * [15] Fedor V. Fomin.  Protrusions in graphs and their applications.  In Venkatesh Raman and Saket Saurabh, editors, Parameterized and Exact Computation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 of Lecture Notes in Computer Science, page 3. Springer, 2010.  doi:10.1007/978-3-642-17493-3\\_2.
  * [16] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos.  Bidimensionality and kernels.  SIAM J. Comput., 49(6):1397–1422, 2020.  doi:10.1137/16M1080264.
  * [17] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.  doi:10.1017/9781107415157.
  * [18] Illya V Hicks, Arie MCA Koster, and Elif Kolotoğlu.  Branch and tree decomposition techniques for discrete optimization.  In Emerging Theory, Methods, and Applications, pages 1–29. INFORMS, 2005.
  * [19] Yoichi Iwata.  Linear-time kernelization for feedback vertex set.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 68:1–68:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICALP.2017.68.
  * [20] Mark Jerrum and Alistair Sinclair.  Polynomial-time approximation algorithms for the Ising model.  SIAM J. Comput., 22(5):1087–1116, 1993.
  * [21] Eun Jung Kim, Maria J. Serna, and Dimitrios M. Thilikos.  Data-compression for parametrized counting problems on sparse graphs.  In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pages 20:1–20:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.ISAAC.2018.20.
  * [22] Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi.  Kernelization of counting problems.  CoRR, abs/2308.02188, 2023.  arXiv:2308.02188, doi:10.48550/arXiv.2308.02188.
  * [23] Michael Luby and Eric Vigoda.  Fast convergence of the Glauber dynamics for sampling independent sets.  Random Struct. Algorithms, 15(3-4):229–241, 1999.
  * [24] Catherine McCartin.  Parameterized counting problems.  Annals of Pure and Applied Logic, 138(1):147–182, 2006.  doi:10.1016/j.apal.2005.06.010.
  * [25] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon.  Network motifs: Simple building blocks of complex networks.  Science (New York, N.Y.), 298:824–7, 11 2002.  doi:10.1126/science.298.5594.824.
  * [26] Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos.  Parameterized counting algorithms for general graph covering problems.  In Frank K. H. A. Dehne, Alejandro López-Ortiz, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, volume 3608 of Lecture Notes in Computer Science, pages 99–109. Springer, 2005.  doi:10.1007/11534273\\_10.
  * [27] Pekka Orponen.  Dempster’s rule of combination is #p-complete.  Artif. Intell., 44(1-2):245–253, 1990.
  * [28] Dan Roth.  On the hardness of approximate reasoning.  Artif. Intell., 82(1-2):273–302, 1996.
  * [29] Paul D. Seymour and Robin Thomas.  Call routing and the ratcatcher.  Comb., 14(2):217–241, 1994.
  * [30] Dimitrios M. Thilikos.  Compactors for parameterized counting problems.  Comput. Sci. Rev., 39:100344, 2021.  doi:10.1016/j.cosrev.2020.100344.
  * [31] Stéphan Thomassé.  A $4k^{2}$ kernel for feedback vertex set.  ACM Trans. Algorithms, 6(2):32:1–32:8, 2010.  doi:10.1145/1721837.1721848.
  * [32] Marc Thurley.  Kernelizations for parameterized counting problems.  In Jin-yi Cai, S. Barry Cooper, and Hong Zhu, editors, Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings, volume 4484 of Lecture Notes in Computer Science, pages 703–714. Springer, 2007.  doi:10.1007/978-3-540-72504-6\\_64.
  * [33] Seinosuke Toda.  PP is as hard as the polynomial-time hierarchy.  SIAM J. Comput., 20(5):865–877, 1991.  doi:10.1137/0220053.
  * [34] Leslie G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.  doi:10.1016/0304-3975(79)90044-6.
  * [35] D. J. A. Welsh.  Graph theory and theoretical physics.  The Mathematical Gazette, 54(390):432–433, 1970.  doi:10.2307/3613919.

##  Appendix A An FPT algorithm for #minFVS

See 3.9

######  Proof A.1.

The pseudocode of an algorithm to solve the disjoint minimum feedback vertex
set counting problem is given in 2 and is based on the algorithm by Cao et al
[8]. In fact, our algorithm solves a slightly more general version of the
problem, where the vertices of the graph $G$ are weighted by a function
$w\colon V(G)\to\mathbb{N}$. In case $G$ has no FVS of size at most $k$ that
is disjoint from $W$, then #DJ-FVS($G$, $w$, $W$, $k$) will output a pair
$(a,b)$ with $a=\infty$ and $b=0$. Otherwise, $a$ will be the size of a
minimum FVS disjoint of $W$ and

$b=\sum_{\begin{subarray}{c}|S|=a,\\\ S\in\mathrm{FVS}(G),\\\ S\cap
W=\emptyset\end{subarray}}\prod_{v\in S}w(v).$

We refer to this value as the _weighted disjoint minimum FVS sum_ of $G$. The
weight of a vertex $v$ essentially models the number of distinct alternatives
there are for a vertex $v$ that, in the context of choosing them for a minimum
FVS of $G$, achieve the same result. When we assign a weight of one to each
vertex of a graph $G$, then the weighted minimum FVS sum of $G$ is equal to
the number of minimum feedback vertex sets of $G$.

In the pseudocode we make use of binary operator $\oplus$, which is defined to
work on pairs as follows:

$(a_{1},b_{1})\oplus(a_{2},b_{2})=\begin{cases}(a_{1},b_{1})&\mbox{if
}a_{1}<a_{2}\\\ (a_{2},b_{2})&\mbox{if }a_{1}>a_{2}\\\
(a_{1},b_{1}+b_{2})&\mbox{if }a_{1}=a_{2}\\\ \end{cases}$

For the operators $+$ and $\cdot$ we assume element-wise functionality when
applied to pairs, i.e.
$(a_{1},b_{1})+(a_{2},b_{2})=(a_{1}+a_{2},b_{1}+b_{2})$. Furthermore, for a
weight function $w$ of $G$ and $X\subseteq V(G)$, we use $w|_{X}$ to denote
the restriction of $w$ to $X$.

We shall now explain how the #DJ-FVS algorithm works by going over the
pseudocode in Algorithm 2. It makes use of a branching strategy with measure
function $\ell+k$, where $\ell$ is the number of connected components of
$G[W]$.

Lines 1-3 are the base cases of the algorithm. In lines 4-5 we remove vertices
of degree at most one, which corresponds to (R2). In lines 6-7 we contract the
chains of $G$ existing in $G-W$ one edge at a time. Note for line 8 that $H$
is a forest since $W$ is an FVS of $G$. For lines 9-10, if a vertex $v$ would
form a cycle with $W$ it should be contained in all solutions so we recurse on
this choice. In lines 11-14, vertex $v$ has at least two neighbors in $W$, but
since $G[W\cup\\{v\\}]$ does not form a cycle these neighbors must be in
different connected components of $G[W]$. Thus we branch on $v$ not being in a
solution, which corresponds with adding $v$ to $W$, and on $v$ being in a
solution by removing it from the graph. In the former branch $\ell$ decreases,
while in the latter $k$ decreases.

In line 15, we choose a vertex $v\in V(H)$ that is not a leaf of tree $H$ such
that at most one of its neighbors in $H$ is not a leaf of $H$. Note that such
a vertex always exists for a tree that does not consist of only leaves.
Furthermore, at this point of the algorithm no tree of $H$ can consist of only
leaves. If a tree of $H$ consists of a single leaf, then either it has degree
one in $G$, but then lines 4-5 would have gotten rid of it, or it has degree
at least two, in which case the if condition on line 9 or the if condition on
line 11 would have been satisfied. If a tree of $H$ consists of two leaves,
then either both have degree two in which case the edge between them would
have been contracted by lines 6-7, or one of the if statements of line 9 or
line 11 would have been applicable to one of the two leaves.

First consider the case where $v$ has one neighbor in $W$ (lines 16-22). In
that case we pick $c$ in line 16 to be a child of $v$. For these two vertices,
we branch over all possible combinations of whether or not they should be in a
solution, while realizing that a minimum FVS that contains $v$ can never
contain $c$. Note that if $G[W\cup\\{v,c\\}]$ does not form a cycle, both $v$
and $c$ must have a neighbor in a different connected component of $W$ so the
branch in line 19 decreases $\ell$. The branches on line 20 and 21 decrease
$k$ while not increasing $\ell$.

Finally, we have the case that $v$ has no neighbors in $W$ (lines 23-31). That
must mean that $v$ has at least two children, which are all leaves by how we
chose $v$. If $v$ would have had only one child, then the edge between $v$ and
the child would have been contracted in lines 6-7. Thus we let $c_{1}$ and
$c_{2}$ be two distinct children of $v$. Again, we branch over all viable
combinations of how these three vertices can be part of solutions. The logic
here is similar to that of the previous case. Here as well, in all branches,
the measure $k+\ell$ decreases.

Since the algorithm branches in at most five directions and the time per
iteration is polynomial in $n$, the runtime of the disjoint algorithm becomes
$5^{k+\ell}\cdot n^{O(1)}$. We can use 2 to compute $\mathrm{\\#minFVS}(G,k)$
by taking an FVS $Z$ of $G$ and running the disjoint algorithm for all subsets
of $Z$, simulating the ways an FVS can intersects $Z$. The pseudocode for this
compression algorithm can be seen in 1. To get an FVS of $G$ of size at most
$k$, we can simply run one of the existing algorithms designed for this, for
example the one by Cao et al. [8] which runs in time
$\mathcal{O}(3.83^{k})\cdot\mathrm{poly}(n)$. If this reports that no such FVS
exists, we output $\mathrm{\\#minFVS}(G,k)=0$. Otherwise, we use the found FVS
for the compression algorithm. Using the fact that the FVS used by the
compression algorithm is of size at most $k$, we can bound the runtime of the
complete algorithm to compute $\mathrm{\\#minFVS}(G,k)$ at $26^{k}\cdot
n^{O(1)}$.

Algorithm 1 #FVS-compression($G$, $k$, $Z$)

Input: Graph $G$, integer $k$, FVS $Z$ of $G$ of size at most $k$
Output: A pair $(a,b)$ with $a$ being the feedback vertex number of $G$ and
$b=\mathrm{\\#minFVS}(G,k)$

1:$s=(\infty,0)$ $X_{Z}\subseteq Z$

2:$s^{\prime}=(|X_{Z}|,0)+$#DJ-FVS$G-X_{Z}$, $w$, $Z\setminus X_{Z}$,
$k-|X_{Z}|$ with $\forall v\in V(G-X_{Z}):w(v)=1$

3:$s=s\oplus s^{\prime}$

4:s

Algorithm 2 #DJ-FVS($G$, $w$, $W$, $k$)

Input: Graph $G$, weight function $w\colon V(G)\to\mathbb{N}$, FVS $W$ of $G$,
integer $k$
Parameter: $k+\ell$, with $\ell=\\#$ components of $G[W]$
Output: A pair $(a,b)$ where $a$ is the size of a minimum FVS $S$ of $G$ such
that
$S\cap W=\emptyset$ and $b$ is the weighted disjoint minimum FVS sum of $G$.
If no such FVS
of size at most $k$ exists, then $(a,b)=(\infty,0)$.

$k<0$$(\infty,0)$$G[W]$has a cycle $(\infty,0)$$G-W$is empty $(0,1)$$\exists
v\in V(G-W)$: $\mathit{deg}_{G}(v)\leq 1$

1:#DJ-FVS$G-v$, $w|_{V(G)\setminus\\{v\\}}$ ,$W$,$k$ $\exists\\{v,u\\}\in
E(G):$ $\deg_{G}(v)=\deg_{G}(u)=2$ and $v,u\notin W$

2:#DJ-FVS$G^{\prime}$, $w^{\prime}$ $W$, $k$, where $G^{\prime}$ is $G$ with
edge $\\{v,u\\}$ contracted to a single vertex $s$ and $w^{\prime}$ is the
weight function $w|_{V(G^{\prime})}$ with $w^{\prime}(s)=w(v)+w(u)$.

3:Let $H$ be forest $G-W$. $\exists v\in V(H)$: $G[W\cup\\{v\\}]$ has a cycle

4:$(1,0)+(1,w(v))\cdot$ #DJ-FVS$G-v$, $w|_{V(G)\setminus\\{v\\}}$, $W$, $k-1$
$\exists v\in V(H)$: $|N_{G}(v)\cap W|\geq 2$

5:$X_{0}=$#DJ-FVS$G$, $w$, $W\cup\\{v\\}$, $k$

6:$X_{1}=(1,0)+(1,w(v))\cdot$ #DJ-FVS$G-v$, $w|_{V(G)\setminus\\{v\\}}$, $W$,
$k-1$

7:$X_{0}\oplus X_{1}$

8:Let $v\in V(H)$ be a vertex that is not a leaf of $H$ such that at most one
vertex in $N_{H}(v)$ is not a leaf of $H$. $|N_{G}(v)\cap W|=1$

9:Pick $c\in V(H)$ such that $N_{G}(c)=\\{v,x\\}$ for some $x\in W$
$G[W\cup\\{v,c\\}]$ forms a cycle $X_{00}=(\infty,0)$ $X_{00}=$ #DJ-FVS$G$,
$w$, $W\cup\\{v,c\\}$, $k$

10:$X_{10}=(1,0)+(1,w(v))\cdot$ #DJ-FVS$G-v$, $w|_{V(G)\setminus\\{v\\}}$,
$W$, $k-1$

11:$X_{01}=(1,0)+(1,w(c))\cdot$ #DJ-FVS$G-c$, $w|_{V(G)\setminus\\{c\\}}$,
$W\cup\\{v\\}$, $k-1$

12:$X_{00}\oplus X_{10}\oplus X_{01}$ $|N_{G}(v)\cap W|=0$

13:Pick $c_{1},c_{2}\in V(H),c_{1}\neq c_{2}$ such that
$N_{G}(c_{1})=\\{v,x\\}$ and $N_{G}(c_{2})=\\{v,y\\}$ for some $x,y\in W$
$G[W\cup\\{v,c_{1},c_{2}\\}]$ forms a cycle $X_{000}=(\infty,0)$ $X_{000}=$
#DJ-FVS$G$, $w$, $W\cup\\{v,c_{1},c_{2}\\}$, $k$

14:$X_{100}=(1,0)+(1,w(v))\cdot$ #DJ-FVS$G-v$, $w|_{V(G)\setminus\\{v\\}}$,
$W$, $k-1$

15:$X_{010}=(1,0)+(1,w(c_{1}))\cdot$ #DJ-FVS$G-c_{1}$,
$w|_{V(G)\setminus\\{c_{1}\\}}$, $W\cup\\{v,c_{2}\\}$, $k-1$

16:$X_{001}=(1,0)+(1,w(c_{2}))\cdot$ #DJ-FVS$G-c_{2}$,
$w|_{V(G)\setminus\\{c_{2}\\}}$, $W\cup\\{v,c_{1}\\}$, $k-1$

17:$X_{011}=(2,0)+(1,w(c_{1})\cdot w(c_{2}))\cdot$ #DJ-
FVS$G-\\{c_{1},c_{2}\\}$, $w|_{V(G)\setminus\\{c_{1},c_{2}\\}}$,
$W\cup\\{v\\}$, $k-2$

18:$X_{000}\oplus X_{100}\oplus X_{010}\oplus X_{001}\oplus X_{011}$