Nanjing<EMAIL_ADDRESS>Nanjing<EMAIL_ADDRESS>Huairui
Chu and Bingkai Lin [500]Theory of computation Fixed parameter tractability
Satoru Iwata and Naonori Kakimura 2 34th International Symposium on Algorithms
and Computation (ISAAC 2023) ISAAC 2023 ISAAC 2023 December 3-6, 2023 Kyoto,
Japan 283 18

# FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set
Selection and Vector Dominating Set

Huairui Chu  Bingkai Lin

###### Abstract

Treewidth is a useful tool in designing graph algorithms. Although many NP-
hard graph problems can be solved in linear time when the input graphs have
small treewidth, there are problems which remain hard on graphs of bounded
treewidth. In this paper, we consider three vertex selection problems that are
W[1]-hard when parameterized by the treewidth of the input graph, namely the
capacitated vertex cover problem, the target set selection problem and the
vector dominating set problem. We provide two new methods to obtain FPT
approximation algorithms for these problems. For the capacitated vertex cover
problem and the vector dominating set problem, we obtain
$(1+o(1))$-approximation FPT algorithms. For the target set selection problem,
we give an FPT algorithm providing a tradeoff between its running time and the
approximation ratio.

###### keywords:

FPT approximation algorithm, Treewidth, Capacitated vertex cover, Target set
selection, Vector dominating set

###### category:

##  1 Introduction

We consider problems whose goals are to select a minimum sized vertex set in
the input graph that can “cover” all the target objects. In the capacitated
vertex cover problem (CVC), we are given a graph $G$ with a capacity function
$c:V(G)\to\mathbb{N}$, the goal is to find a set $S\subseteq V(G)$ of minimum
size such that every edge of $G$ is covered111An edge $e$ can be covered by a
vertex $v$ if $v$ is an endpoint of $e$. by some vertex in $S$ and each vertex
$v\in S$ covers at most $c(v)$ edges. This problem has application in planning
experiments on redesign of known drugs involving glycoproteins [24]. In the
target set selection problem (TSS), we are given a graph $G$ with a threshold
function $t:V(G)\to\mathbb{N}$. The goal is to select a minimum sized set
$S\subseteq V(G)$ of vertices that can activate all the vertices of $G$. The
activation process is defined as follows. Initially, all vertices in the
selected set $S$ are activated. In each round, a vertex $v$ gets active if
there are $t(v)$ activated vertices in its neighbors. The study of TSS has
application in maximizing influence in social network [26]. Vector dominating
set (VDS) can be regarded as a “one-round-spread” version of TSS, where the
input consists of a graph $G$ and a threshold function $t:V(G)\to\mathbb{N}$,
and the goal is to find a set $S\subseteq V(G)$ such that for all vertices
$v\in V$, there are at least $t(v)$ neighbors of $v$ in $S$.

Since CVC generalizes the vertex cover problem, while TSS and VDS are no
easier than the dominating set problem222For VDS, when $t(v)=1$ for every
vertex $v$ in the graph, VDS is the dominating set problem. For TSS, a
reduction from dominating set to TSS can be found in the work of Charikar et
al. [8]., they are both NP-hard and thus have no polynomial time algorithm
unless $P=NP$. Polynomial time approximation algorithms for capacitated vertex
cover problem have been studied extensively [24, 12, 22, 34, 11, 36, 35]. The
problem has a $2$-approximation polynomial time algorithm [22]. Assuming the
_Unique Game Conjecture_ , there is no polynomial time algorithm for the
vertex cover problem with approximation ratio better than $2$ [27]. As for the
TSS problem, it is known that the minimization version of TSS cannot be
approximated to $2^{\log^{1-\epsilon}n}$ assuming $P\neq NP$, or
$n^{0.5-\epsilon}$ assuming the conjecture on planted dense subgraph [10, 9].
Cicalese et al. proved that VDS cannot be approximated within a factor of
$c\ln n$ for some $c$ unless $P=NP$ [13].

Another way of dealing with hard computational problems is to use
parameterized algorithms. For any input instance $x$ with parameter $k$, an
algorithm with running time upper bounded by $f(k)\cdot|x|^{O(1)}$ for some
computable function $f$ is called FPT. A natural parameter for a computational
problem is the solution size. The first FPT algorithm with running time
$1.2^{k^{2}}+n^{2}$ for capacitated vertex cover problem parameterized by
solution size was provided in [25]. In [17], the authors gave an improved FPT
algorithm that runs in $k^{3k}\cdot|G|^{O(1)}$. However, using the solution
size as parameter might be too strict for CVC. Note that CVC instances with
sublinear capacity functions cannot have small sized solutions. On the other
hand, TSS parameterized by its solution size is W[P]-hard 333The well known
W-hierarchy is $FPT\subseteq W[1]\subseteq W[2]\subseteq...\subseteq W[P]$,
where $FPT$ denotes the set of problems which admits FPT algorithms. The basic
conjecture on parameterized complexity is $FPT\neq W[1]$. We refer the readers
to [18, 20, 15] for more details. according to [1]. VDS is W[2]-hard since it
generalizes the dominating set problem.

In this paper, we consider these problems parameterized by the treewidth [33]
of the input graph. In fact, since the treewidth of a graph having $k$-sized
vertex cover is also upper-bounded by $k$ [17], CVC parameterized by treewidth
can be regarded as a natural generalization of CVC parameterized by solution
size. And it is already proved in [17] that CVC parameterized only by the
treewidth of its input graph has no FPT algorithm assuming $W[1]\neq FPT$. As
for the TSS problem, it can be solved in $n^{O(w)}$ time for graphs with $n$
vertices and treewidth bounded by $w$ and has no $n^{o(\sqrt{w})}$-time
algorithm unless ETH fails [3]. VDS is also $W[1]$-hard when parameterized by
treewidth [4], however, it admits an FPT algorithm with respect to the
combined parameter $(w+k)$[32].

Recently, the approach of combining parameterized algorithms and approximation
algorithms has received increased attention [19]. It is natural to ask whether
there exist FPT algorithms for these problems with approximation ratios better
than that of the polynomial time algorithms. Lampis [29] proposed a general
framework for approximation algorithms on tree decomposition. Using his
framework, one can obtain algorithms for CVC and VDS which outputs a solution
of size at most $opt(I)$ on input instance $I$ but may slightly violate the
capacity or the threshold requirement within a factor of $(1\pm\epsilon)$.
However, the framework of Lampis can not be directly used to find an
approximation solution for these problems satisfying all the capacity or
threshold requirement. The situation becomes worse in the TSS problem, as the
error might propagate during the activation process. We overcome these
difficulties and give positive answer to the aforementioned question. For the
CVC and VDS problems, we obtain $(1+o(1))$-approximation FPT algorithms
respectively.

######  Theorem 1.1.

There exists an algorithm 444The algorithm can be modified to output a
solution with size as promised. See the remark in Appendix B., which takes a
CVC instance $I=(G,c)$ and a tree decomposition $(T,\mathcal{X})$ with width
$w$ for $G$ as input and outputs an integer
$\hat{k}_{\min}\in[opt(I),(1+O(1/(w^{2}\log n)))opt(I)]$ in $(w\log
n)^{O(w)}n^{O(1)}$ time.

######  Theorem 1.2.

There exists an algorithm running in time $2^{O(w^{5}\log w\log\log
n)}n^{O(1)}$ which takes as input an instance $I=(G,t)$ of VDS and a tree
decomposition of $G$ with width $w$, finds a solution of size at most
$(1+1/(w\log\log n)^{\Omega(1)})\cdot opt(I)$.

Notice that the running time stated in above theorems are FPT running time,
because $(\log n)^{f(w)}\leq f(w)^{O(f(w))}+n^{O(1)}$.

For the TSS problem, we give an approximation algorithm with a tradeoff
between the approximation ratio and its running time.

######  Theorem 1.3.

For all $C\in\mathbb{N}$, there is an algorithm which takes as input an
instance $I=(G,t)$ of TSS and a tree decomposition of $G$ with width $w$,
finds a solution of size $(1+(w+1)/(C+1))\cdot opt(I)$ in time $n^{C+O(1)}$.

Open problems and future work. Note that our FPT approximation algorithm for
TSS has ratio equal to the treewidth of the input graph. An immediate question
is whether this problem has parameterized $(1+o(1))$-approximation algorithm.
We remark that the reduction from $k$-Clique to TSS in [3] does not preserve
the gap. Thus it does not rule out constant FPT approximation algorithm for
TSS on bounded treewidth graphs even under hypotheses such as parameterized
inapproximablity hypothesis (PIH) [30] or GAP-ETH [16, 31].

In the regime of exact algorithms, we have the famous Courcelle’s Theorem
which states that all problems defined in _monadic second order logic_ have
linear time algorithm on graphs of bounded treewidth [2, 14]. It is
interesting to ask if one can obtain a similar algorithmic meta-theorem [23]
for approximation algorithms.

###  1.1 Overview of our techiniques

Capacitated Vertex Cover. Our starting point is the exact algorithm for CVC on
graphs with treewidth $w$ in $n^{\Theta(w)}$ time. The exact algorithm has
running time $n^{\Theta(w)}$ because it has to maintain a set of
$(w+1)$-dimension vectors $d:X_{\alpha}\to[n]$ for every node $\alpha$ in the
tree decomposition. One can get more insight by checking out the exact
algorithm for CVC in Section 3. To reduce the size of such a table, Lampis’
approach [29] is to pick a parameter $\epsilon\in(0,1)$ and round every
integer to the closest integer power of $(1+\epsilon)$. In other words, an
integer $n$ is represented by $(1+\epsilon)^{x}$ with $(1+\epsilon)^{x}\leq
n<(1+\epsilon)^{x+1}$. Thus it suffices to keep $(\log n)^{O(w)}$ records for
every bag in the tree decomposition. The price of this approach is that we can
only have approximate values for records in the table. Note that the errors of
approximate values might accumulate after addition (See Lemma 4.7).
Nevertheless, we can choose a tree decomposition with height $O(w^{2}\log n)$
and set $\epsilon=1/poly(w\log n)$ so that if the dynamic programming
procedure only involves adding and passing values of these vectors, then we
can have $(1+o(1))$-approximation values for all the records in the table.

Unfortunately, in the forgetting node for a vertex $v$, we need to compare the
value of $d(v)$ and the capacity value $c(v)$. This task seems impossible if
we do not have the exact value of $d(v)$. Our idea is to modify the “slightly-
violating-capacity” solution, based on two crucial observations. The first is
that, in a solution, for any vertex $v\in V$, the number of edges incident to
$v$ which are not covered by $v$ presents a lower bound for the solution size.
The second observation is that one can test if a “slightly-violating-capacity”
solution can be turned into a good one in polynomial time. These observations
are formally presented in Lemma 4.8 and 4.10.

Target Set Selection and Vector Dominating Set. We observe that both of the
TSS and VDS problems are _monotone_ and _splittable_ , where the monotone
property states that any super set of a solution is still a solution and the
splittable property means that for any separator $X$ of the input graph $G$,
the union of $X$ and solutions for components after removing $X$ is also a
solution for the graph $G$. We give a general approximation for vertex subset
problems that are monotone and splittable. The key of our approximation
algorithm is an observation that any bag in a tree decomposition is a
separator in $G$. As the problem is splittable, we can design a procedure to
find a bag, and remove it, which leads to a separation of $G$ and we then deal
with the component “rooted” by this bag. We can use this procedure repeatedly
until the whole graph is done.

###  1.2 Organization of the Paper

In Section 2 the basic notations are given, and we formally define the problem
we study. In Section 3 we present the exact algorithm for CVC. In Section 4 we
present the approximate algorithm for CVC. In Section 5, we give the
approximation algorithms for TSS and VDS.

##  2 Preliminaries

###  2.1 Basic Notations

We denote an undirected simple graph by $G=(V,E)$, where $V=[n]$ for some
$n\in\mathbb{N}$ and $E\subseteq\binom{V}{2}$. Let $V(G)=V$ and $E(G)=E$ be
its vertex set and edge set. For any vertex subset $S\subseteq V$, let the
induced subgraph of $S$ be $G[S]$. The edges of $G[S]$ are
$E[S]=E(G)\cap\binom{S}{2}$. For any $S_{1},S_{2}\subseteq V$, we use
$E[S_{1},S_{2}]$ to denote the edge set between $S_{1}$ and $S_{2}$, i.e.
$E[S_{1},S_{2}]=\\{e=(u,v)\in E\mid u\in S_{1},v\in S_{2}\\}$. For every $v\in
V(G)$, we use $N(v)$ to denote the neighbors of $v$, and $d(v):=|N(v)|$.

For an orientation $O$ of a graph $G$, which can be regarded as a directed
graph whose underlying undirected graph is $G$, we use $D_{O}^{+}(v)$ to
denote the outdegree of $v$ and $D_{O}^{-}(v)$ its indegree. In a directed
graph or an orientation, an edge $(u,v)$ is said to start at $u$ and sink at
$v$. Reversing an edge is an operation, in which an edge $(u,v)$ is replaced
by $(v,u)$.

In a graph $G=(V,E)$, a separator is a vertex set $X$ such that $G[V\setminus
X]$ is not a connected graph. In this case we say $X$ separates $V$ into
disconnected parts $C_{1},C_{2},...\subseteq V\setminus X$, where $C_{i}$ and
$C_{j}$ are disconnected for all $i\neq j$ in $G[V\setminus X]$.

Let $f:A\rightarrow B$ be a mapping. For a subset $A^{\prime}\subseteq A$, let
$f[A^{\prime}]$ denote the mapping with domain $A^{\prime}$ and
$f[A^{\prime}](a)=f(a)$, for all $a\in A^{\prime}$. Let $f\setminus a$ be
$f[A\setminus\\{a\\}]$. For all $b\in B$, let $f^{-1}(b)$ be the set $\\{a\in
A^{\prime}\mid f(a)=b\\}$.

Let $\gamma\geq 0$ be a small value, we use $\mathbb{N}_{\gamma}$ to denote
$\\{0\\}\cup\\{(1+\gamma)^{x}\mid x\in\mathbb{N}\\}$. For $a,b\in\mathbb{R}$,
we use $a\sim_{\gamma}b$ to denote that $b/(1+\gamma)\leq a\leq(1+\gamma)b$.
It’s easy to see this is a symmetric relation. Further, we use $[a]_{\gamma}$
to denote $\max_{x\in\mathbb{N}_{\gamma},x\leq a}x$. Notice that
$[a]_{\gamma}\sim_{\gamma}a$.

###  2.2 Problems

Capacitated Vertex Cover: An instance of CVC consists of a graph $G=(V,E)$ and
a capacity function $c:V\rightarrow\mathbb{N}$ on the vertices. A solution is
a pair $(S,M)$ where $S\subseteq V$ and $M:E\rightarrow S$ is a mapping. If
for all $v\in S,|M^{-1}(v)|\leq c(v)$ and for all $e\in E,M(e)\in e$, then we
say that $S$ is feasible. The size of a feasible solution is $|S|$. The goal
of CVC is to find a feasible solution of minimum size. An equivalent
description of this problem is the following. Let $O$ be an orientation of all
the edges in $E$. $O$ is a feasible solution if and only if for all $v\in
V,D^{-}_{O}(v)\leq c(v)$. The size of $O$ is defined as $|\\{v\in V\mid
d^{-}(v)>0\\}|$. Here we actually use a directed edge $(u,v)$ to represent
that $\\{u,v\\}$ is covered by $v$. We mainly use this definition as it’s more
convenient for organizing our proof and analysis.

Target Set Selection: Given a graph $G=(V,E)$, a threshold function
$t:V\rightarrow\mathbb{N}$, and a set $S\subseteq V$, the set
$S^{\prime}\subseteq V$ which contains the vertices activated by $S$ is the
smallest set that:

  * •

$S\subseteq S^{\prime}$;

  * •

For a vertex $v$, if $|N(V)\cap S^{\prime}|\geq t(v)$, then $v\in S^{\prime}$.

One can find the vertices activated by $S$ in polynomial time. Just start from
$S^{\prime}:=S$, as long as there exists a vertex $v$ such that $|N(v)\cap
S^{\prime}|\geq t(v)$, add $v$ to $S^{\prime}$, until no such vertex exists. A
vertex set that can activate all vertices in $V$ is called a target set. The
goal of TSS is to find a target set of minimum size.

Vector Dominating Set: Given a graph $G=(V,E)$, a threshold function
$t:V\rightarrow\mathbb{N}$, the goal of Vector Dominating Set problem is to
find a minimum vertex subset $S\subseteq V$ such that every vertex $v\in
V\setminus S$ satisfies $|N(v)\cap S|\geq t(v)$.

###  2.3 Tree Decomposition

In this paper, we consider problems parameterized by the treewidth of the
input graphs. A tree decomposition of a graph $G$ is a pair $(T,\mathcal{X})$
such that

  * •

$T$ is a rooted tree and $\mathcal{X}=\\{X_{\alpha}:\alpha\in
V(T),X_{\alpha}\subseteq V(G)\\}$ is a collection of subsets of $V(G)$;

  * •

$\bigcup_{\alpha\in V(T)}X_{\alpha}=V(G)$;

  * •

For every edge $e$ of $G$, there exists an $\alpha\in V(T)$ such that
$e\subseteq X_{\alpha}$;

  * •

For every vertex $v$ of $G$, the set $\\{\alpha\in V(T)\mid v\in
X_{\alpha}\\}$ forms a subtree of $T$.

The width of a tree decomposition $(T,\mathcal{X})$ is $\max_{\alpha\in
V(T)}{|X_{\alpha}|-1}$. The treewidth of a graph $G$ is the minimum width over
all its tree decompositions.

The sets in $\mathcal{X}$ are called “bags”. For a node $\alpha\in V(T)$, let
$T_{\alpha}$ denote the subtree of $T$ rooted by $\alpha$. Let
$V_{\alpha}\subseteq V$ denote the vertex set
$V_{\alpha}=\cup_{\alpha^{\prime}\in V(T_{\alpha})}X_{\alpha^{\prime}}$. Let
$Y_{\alpha}:=V_{\alpha}\setminus X_{\alpha}$. For a node $\alpha$, we use
$\alpha_{1}(,\alpha_{2})$ to denote its possible children. By the definition
of tree decompositions, for a join node $\alpha$, $Y_{\alpha_{1}}\cap
Y_{\alpha_{2}}=\emptyset$.

It is convenient to work on a _nice tree decomposition_. Every node $\alpha\in
V(T)$ in this nice tree decomposition is expected to be one of the following:

Leaf Node: $\alpha$ is a leaf and $X_{\alpha}=\emptyset$;

Introducing $v$ Node: $\alpha$ has exactly one child $\alpha_{1}$, $v\notin
X_{\alpha_{1}}$ and $X_{\alpha}=X_{\alpha_{1}}\cup\\{v\\}$;

Forgetting $v$ Node: $\alpha$ has exactly one child $\alpha_{1}$, $v\notin
X_{\alpha}$ and $X_{\alpha}\cup\\{v\\}=X_{\alpha_{1}}$;

Join Node: $\alpha$ has exactly two children $\alpha_{1}$, $\alpha_{2}$ and
$X_{\alpha}=X_{\alpha_{1}}=X_{\alpha_{2}}$.

Treewidth is a popular parameter to consider because tree decompositions with
optimal or approximate treewidth can be efficiently computed [28]. We refer
the reader to [15, 6, 5] for more details of treewidth and nice tree
decomposition. Using the tree balancing technique [7] and the method of
introducing new nodes, we can transform any tree decomposition with width $w$
in polynomial time into a nice tree decomposition with width $O(w)$, depth
upper bounded by $O(w^{2}\log n)$, and containing at most $O(nw)$ nodes.
Moreover, we can add $O(w)$ nodes so that the root $\alpha_{0}$ is assigned
with an empty set $X_{\alpha_{0}}=\emptyset$. Notice that in this case,
$Y_{\alpha_{0}}=V_{\alpha_{0}}=V$. We assume all the nice tree decompositions
discussed in this paper satisfy these properties.

##  3 Exact Algorithm for CVC

We present the exact algorithm for two reasons. The first is that one can gain
some basic insights on the structure of the approximate algorithm by
understanding the exact algorithm, which is more comprehensible. The other is
that we need to compare the intermediate results of the exact algorithm and
the approximate algorithm, so the total description of the algorithm can also
be regarded as a recursive definition of the intermediate results (which are
the sets $R_{\alpha}$’s defined in the following).

###  3.1 Definition of the Tables

Given a tree decomposition $(T,\mathcal{X})$, we run a classical bottom-up
dynamic program to solve CVC. That is, on each node $\alpha$ we allocate a
record set $R_{\alpha}$. $R_{\alpha}$ contains records of the form $(d,k)$. A
record $(d,k)$ consists of two elements: a mapping
$d:X_{\alpha}\rightarrow\mathbb{N}$ and an integer $k\in\mathbb{N}$. At first,
we present a definition of $R_{\alpha}$ by its properties. Then we define
$R_{\alpha}$ according to the Recursive Rules. If our goal is only to design
an exact algorithm for CVC, then there could be many different definitions of
the tables which all work. However, here our definitions are elaborated so
that they fit in our analysis of the approximation algorithm. After these
definitions are given, later in Theorem 3.2 we prove that these two
definitions coincide.

Let $G_{\alpha}$ denote the graph with vertex set $V_{\alpha}$ and edge set
$E[V_{\alpha}]\setminus E[X_{\alpha}]$. We expect that the table $R_{\alpha}$
has the following properties.

####  3.1.1 Expected Properties for $R_{\alpha}$

A record $(d,k)\in R_{\alpha}$ if and only if there exists $O$, an orientation
of $G_{\alpha}$, such that

For each $v\in X_{\alpha}$, $d(v)=D_{O}^{+}(v)$ is just its out degree;

$D^{-}_{O}(v)\leq c(v)$ for all $v\in Y_{\alpha}$;

$|\\{v\in Y_{\alpha}\mid D_{O}^{-}(v)>0\\}|\leq k\leq|Y_{\alpha}|$.
Intuitively, $(d,k)\in R_{\alpha}$ if there exists a vertex set $S\subseteq
Y_{\alpha}$ and a mapping $M:E[V_{\alpha}]\setminus E[X_{\alpha}]\rightarrow
S\cup X_{\alpha}$ such that

  * •

all edges are covered correctly, i.e. $M(e)\in e$ for all $e\in
E[V_{\alpha}]\setminus E[X_{\alpha}]$;

  * •

for each $v\in X_{\alpha}$, there are $d(v)$ edges from $v$ to $Y_{\alpha}$
that are covered by $S$, i.e. $|E[\\{v\\},Y_{\alpha}]\cap\cup_{u\in
S}M^{-1}(u)|=d(v)$;

  * •

$M$ satisfies the capacity constraints for vertices in $Y_{\alpha}$, i.e. for
all $v\in Y_{\alpha}$, $|M^{-1}(v)|\leq c(v)$;

  * •

$|S|\leq k\leq|Y_{\alpha}|$.

One can imagine that $S$ is a feasible solution for a spanning subgraph of
$G_{\alpha}$, where the vector $d$ governs the edges between $X_{\alpha}$ and
$Y_{\alpha}$.

Note that the root node $\alpha_{0}$ satisfies $X_{\alpha_{0}}=\emptyset$, and
$G_{\alpha_{0}}=G$. So if $R_{\alpha_{0}}$ is correctly computed, then the $k$
values in those records in $R_{\alpha_{0}}$ have a one-to-one correspondence
to all feasible solution sizes for the original instance. We output
$\min_{(d,k)\in R_{\alpha_{0}}}k$ to solve the instance.

####  3.1.2 Recursive Rules for $R_{\alpha}$

Fix a node $\alpha\in V(T)$, if $\alpha$ is a introducing node or a forgetting
node, let $\alpha_{1}$ be its child. If $\alpha$ is a join node, let
$\alpha_{1},\alpha_{2}$ be its children. In case $\alpha$ is a:

Leaf Node.

$R_{\alpha}=\\{(d,k)\\}$, in which $d$ is a mapping with empty domain and
$k:=0$.

Introducing $v$ Node.

Note that by the properties of tree decompositions, there is no edge between
$v$ and $Y_{\alpha}$ in $G$. A record $(d,k)\in R_{\alpha}$ if and only if
$(d\setminus v,k)\in R_{\alpha_{1}}$ and $d(v)=0$.

Join Node.

$(d,k)\in R_{\alpha}$ if and only if there exist $(d_{1},k_{1})\in
R_{\alpha_{1}}$ and $(d_{2},k_{2})\in R_{\alpha_{2}}$ such that for all $v\in
X_{\alpha}$, $d(v)=d_{1}(v)+d_{2}(v)$ and $k=k_{1}+k_{2}$.

Forgetting $v$ Node.

$(d,k)\in R_{\alpha}$ if and only if there exists $(d_{1},k_{1})\in
R_{\alpha_{1}}$ satisfying one of the following conditions:

$k_{1}=k$, $d_{1}(v)=|N(v)\cap Y_{\alpha}|$ and $d_{1}\setminus v=d$. In this
case, $v$ is not “included in $S$”. All the edges between $v$ and $Y_{\alpha}$
must be covered by other vertices in $Y_{\alpha}$.

$k_{1}=k-1$ and there exist $\Delta(v)\subseteq N(v)\cap X_{\alpha}$ and
$A\in[|N(v)\cap Y_{\alpha}|-c(v)+|\Delta(v)|,|N(v)\cap Y_{\alpha}|]$ such that
$d_{1}(v)=A$, $d_{1}(u)=d(u)-1$ for all $u\in\Delta(v)$, and $d_{1}(u)=d(u)$
for all $u\in X_{\alpha_{1}}\setminus(\Delta(v)\cup\\{v\\})$. In this case,
$v$ is “included in $S$”. We enumerate a set $\Delta(v)\subseteq N(v)\cap
X_{\alpha}$ of edges between $v$ and $X_{\alpha}$ and let $v$ cover these
edges. Note that for a record $(d_{1},k_{1})\in R_{\alpha_{1}}$, there are
$|N(v)\cap Y_{\alpha}|-d_{1}(v)$ edges that are covered by $v$. To construct
$(d,k)$ from $(d_{1},k_{1})$, we need to check that
$c(v)\geq|\Delta(v)|+|N(v)\cap Y_{\alpha}|-d_{1}(v)$, which is implicitly done
by the setting $d_{1}(v)=A\geq|N(v)\cap Y_{\alpha}|-c(v)+|\Delta(v)|$.

######  Remark 3.1.

In fact, one can find many different ways to define the dynamic programming
table for CVC. We use this definition because we want to upper bound the
values of records in $R_{\alpha}$ by the size of solution (Lemma 4.8), so we
need to record “outdegrees” rather than “indegrees” or “capacities”.

Valid certificate. Notice that all the rules are of the form $(d_{1},k_{1})\in
R_{\alpha_{1}}\Rightarrow(d,k)\in R_{\alpha}$ or $(d_{1},k_{1})\in
R_{\alpha_{1}}\wedge(d_{2},k_{2})\in R_{\alpha_{2}}\Rightarrow(d,k)\in
R_{\alpha}$, thus a rule can actually be divided in to two parts: we found a
“valid certificate” $(d_{1},k_{1})\in R_{\alpha_{1}}$ (and $(d_{2},k_{2})\in
R_{\alpha_{2}}$, for join nodes), then we add a “product” $(d,k)\in
R_{\alpha}$ based on the certificate. In fact, every record in
$R_{\alpha_{1}}$ can be a valid certificate in introducing nodes, and every
pair of records $((d_{1},k_{1}),(d_{2},k_{2}))\in R_{\alpha_{1}}\times
R_{\alpha_{2}}$ can be a valid certificate in join nodes. But in forgetting
$v$ nodes, we further require that $d_{1}(v)$ satisfies some condition. To be
specific, in a forgetting node $\alpha_{1}$ we say $(d_{1},k_{1})\in
R_{\alpha_{1}}$ is valid if it satisfies the following condition:

  * ($\star$)

$d_{1}(v)=|N(v)\cap Y_{\alpha}|$ or $\geq|N(v)\cap
Y_{\alpha}|-c(v)+|\Delta(v)|$ for some $\Delta(v)\subseteq N(v)\cap
X_{\alpha}$.

######  Theorem 3.2.

The set $\\{R_{\alpha}:\alpha\in V(T)\\}$ can be computed by the recursive
rules above in time $n^{w+O(1)}$, and the Expected Properties are satisfied.

The proof sketch of the correctness of these rules are presented in Appendix
A. As $|R_{\alpha}|\leq n^{w+2}$ for all $\alpha\in V(T)$ and the enumerating
$\Delta(v)$ procedure in dealing with a forgetting node runs in time
$w^{O(w)}$, it’s not hard to see that this algorithm runs in time $n^{w+O(1)}$
(for $w$ small enough compared to $n$).

##  4 Approximation Algorithm for CVC

Let $\epsilon$ be a small value to be determined later. We try to compute an
approximate record set $\hat{R}_{\alpha}$ for each node $\alpha$, still using
bottom-up dynamic programming like what we do in the exact algorithm. An
approximate record is a pair $(\hat{d},\hat{k})$, where $\hat{k}\in\mathbb{N}$
and $\hat{d}$ is a mapping from $X_{\alpha}$ to
$\mathbb{N}_{\epsilon}=\\{0\\}\cup\\{(1+\epsilon)^{x}\mid x\in\mathbb{N}\\}$.
As we can see, $\hat{d}$ can take non-integer values.

Height of a Node The height $h$ of a node $\alpha$ is defined by the length of
the longest path from $\alpha$ to a leaf which is descendent to $\alpha$. By
this definition, the height of a node is $1$ plus the maximum height among the
heights of its children. Let the height of the root node be $h_{0}$. According
to the property of nice tree decompositions, $h_{0}$ is at most $O(w^{2}\log
n)$.

Let $\epsilon_{h},\delta_{h}$ be two non-negative values (which are functions
of $h,n$ and $w$) to be determined later.

$h$-close records. If an exact record $(d,k)$ and an approximate record
$(\hat{d},\hat{k})$ satisfy $d(v)\sim_{\epsilon_{h}}\hat{d}(v)$ for all $v\in
X_{\alpha}$ and $k\sim_{\delta_{h}}\hat{k}$, then we say these two records are
$h$-close.

We expect that for each node $\alpha$, $\hat{R}_{\alpha}$ satisfies the
following. Let the height of $\alpha$ be $h$.

  1. (A)

If $(d,k)\in R_{\alpha}$, then there exists
$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ which is $h$-close to $(d,k)$.

  2. (B)

If $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$, then there exists $(d,k)\in
R_{\alpha}$ which is $h$-close to $(\hat{d},\hat{k})$.

After $\hat{R}_{\alpha_{0}}$ is correctly computed (i.e. satisfying (A) and
(B)), we output the value
$\hat{k}_{\min}=(1+\delta_{h_{0}})\min_{(\hat{d},\hat{k})\in\hat{R}_{\alpha_{0}}}\hat{k}$.
Let $OPT$ be the size of the minimum solution, which equals to $\min_{(d,k)\in
R_{\alpha_{0}}}k$. We claim that
$\hat{k}_{\min}\in[OPT,(1+\delta_{h_{0}})^{2}OPT]$.

######  Proof 4.1.

By property (B), we have
$OPT\leq(1+\delta_{h_{0}})\min_{(\hat{d},\hat{k})\in\hat{R}_{\alpha_{0}}}\hat{k}$.
By property (A), we have
$\min_{(\hat{d},\hat{k})\in\hat{R}_{\alpha_{0}}}\hat{k}\leq(1+\delta_{h_{0}})OPT$.
The claim follows by combining these two inequalities.

We need the following procedure to test in polynomial time if a sub-problem is
solvable when we are allowed to use all vertices to cover the edges.

######  Lemma 4.2.

Testing whether $(d,|Y_{\alpha}|)\in R_{\alpha}$ for any $d$ can be done in
$n^{O(1)}$ time.

######  Proof 4.3.

Construct a directed graph with vertex set
$\\{s,t\\}\cup(E[V_{\alpha}]\setminus E[X_{\alpha}])\cup V_{\alpha}$. For each
$e\in(E[V_{\alpha}]\setminus E[X_{\alpha}])$ add an edge $(s,e)$ with capacity
$1$. For each $e=(u,v)\in(E[Y_{\alpha}]\setminus E[X_{\alpha}])$ add an edge
$(e,u)$ and an edge $(e,v)$ both with capacity $1$. For each $v\in X_{\alpha}$
add an edge $(v,t)$ with capacity $|N(v)\cap Y_{\alpha}|-d(v)$. For each $v\in
Y_{\alpha}$ add an edge $(v,t)$ with capacity $c(v)$. We claim that
$(d,|Y_{\alpha}|)\in R_{\alpha}$ if and only if there is a flow from $s$ to
$t$ with value $|E[V_{\alpha}]\setminus E[X_{\alpha}]|$. For the ’if’ part,
notice that by the well-known integrality theorem for network flow, there
exists a integral flow with the same value. Every integral flow with this
value can be transform to an $O$ as expected in the Expected Properties: An
edge $e\in E[Y_{\alpha}]\setminus E[X_{\alpha}]$ is oriented so that it sinks
at vertex $v$ if $(e,v)$ has flow value $1$, then for each vertex $v\in
X_{\alpha}$, reverse some edges in $E[\\{v\\},Y_{\alpha}]$ so that
$D_{O}^{+}(v)=d(v)$, if the flow carried in $(v,t)$ is less than $|N(v)\cap
Y_{\alpha}|-d(v)$. One can construct a flow with the value based on an
orientation $O$, too. Thus the ’only if’ part is easy to see, too.

We first define $\\{\hat{R}_{\alpha}:\alpha\in V(T)\\}$ using the following
Recursive Rules. Then we prove that these sets satisfy the properties (A) and
(B). The basic idea of our approximate algorithm is to run the exact algorithm
in an “approximate way”. For a rule formed as
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}\Rightarrow(\hat{d},\hat{k})\in\hat{R}_{\alpha}$
or
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}\wedge(\hat{d}_{2},\hat{k}_{2})\in\hat{R}_{\alpha_{2}}\Rightarrow(\hat{d},\hat{k})\in\hat{R}_{\alpha}$,
we also call $(\hat{d}_{1},\hat{k}_{1})$ (and $(\hat{d}_{2},\hat{k}_{2})$) the
certificate while $(\hat{d},\hat{k})$ is the product.

###  4.1 Recursive Rules for $\hat{R}_{\alpha}$

Fix a node $\alpha\in V(T)$ with height $h$, in case $\alpha$ is a:

Leaf Node.

$\hat{R}_{\alpha}=\\{(\hat{d},\hat{k})\\}$, in which $\hat{d}$ is a mapping
with empty domain and $\hat{k}=0$.

Introducing $v$ Node.

A record $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ if and only if
$(\hat{d}\setminus v,\hat{k})\in\hat{R}_{\alpha_{1}}$ and $\hat{d}(v)=0$.

Join Node.

$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ if and only if there exists
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}},(\hat{d}_{2},\hat{k}_{2})\in\hat{R}_{\alpha_{2}}$
such that for each $v\in X_{\alpha}$,
$\hat{d}(v)=[\hat{d}_{1}(v)+\hat{d}_{2}(v)]_{\epsilon}$ and
$\hat{k}=\hat{k}_{1}+\hat{k}_{2}$.

Forgetting $v$ Node.

This case is the most complicated. Think in this way: we pick
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ and based on it we try to
construct $(\hat{d},\hat{k})$ to add into $\hat{R}_{\alpha}$. Notice that in
the exact algorithm, not every $(d_{1},k_{1})\in R_{\alpha_{1}}$ can be used
to generate a corresponding product $(d,k)\in R_{\alpha}$ — it has to be the
case that $d_{1}(v)=|N(v)\cap Y_{\alpha}|$ or $d_{1}(v)\geq|N(v)\cap
Y_{\alpha}|-c(v)+|\Delta(v)|$, which is what we called to be a valid
certificate. We have to test both the validity of the certificate and its
exact counterpart using an indirect way. So there are three issues we need to
address:

  1. (a)

The requirement for $(\hat{d}_{1},\hat{k}_{1})$ being valid, i.e. satisfying
the “approximate version” of condition $(\star)$;

  2. (b)

There exists a valid exact counterpart $(d_{1},k_{1})\in R_{\alpha_{1}}$ of
$(\hat{d}_{1},\hat{k}_{1})$ satisfying condition $(\star)$;

  3. (c)

How to construct $(\hat{d},\hat{k})$.

(b) seems impossible since we do not compute $R_{\alpha_{1}}$, we obtain this
indirectly using Lemma 4.2. Later we explain why such an approach reaches our
goal. Formally, suppose we have
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$, we consider two cases:

  1. (1)

$v$ is not “included”.

(1a) See if $\hat{d}_{1}(v)\sim_{\epsilon_{h-1}}|N(v)\cap Y_{\alpha}|$;

(1b) See if $(d_{t},|Y_{\alpha_{1}}|)\in R_{\alpha_{1}}$, where
$d_{t}(u)=\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil$ for all $u\in
X_{\alpha_{1}}\setminus\\{v\\}$ and $d_{t}(v)=|N(v)\cap Y_{\alpha}|$ (This is
polynomial-time tractable by Lemma 4.2);

(1c) If (a) and (b) are satisfied, then add $(\hat{d},\hat{k})$ to
$\hat{R}_{\alpha}$, where $\hat{d}=\hat{d}_{1}\setminus
v,\hat{k}=\hat{k}_{1}$.

  2. (2)

$v$ is “included”. We enumerate $\Delta(v)\subseteq N(v)\cap X_{\alpha}$ and
integer $A$ satisfying $A\in[|N(v)\cap Y_{\alpha}|-c(v)+|\Delta(v)|,|N(v)\cap
Y_{\alpha}|]$.

(2a) See if $\hat{d}_{1}(v)\geq A/(1+\epsilon_{h-1})$;

(2b) See if $(d_{t},|Y_{\alpha_{1}}|)\in R_{\alpha_{1}}$, where
$d_{t}(u)=\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil$ for all $u\in
X_{\alpha_{1}}\setminus\\{v\\}$ and $d_{t}(v)=A$ (By Lemma 4.2, this is still
polynomial-time tractable);

(2c) If (a) and (b) are satisfied, then add $(\hat{d},\hat{k})$ to
$\hat{R}_{\alpha}$, where $\hat{d}(u)=\hat{d}_{1}(u)$ for all $u\in
X_{\alpha}\setminus\Delta(v)$, $\hat{d}(u)=[\hat{d}(u)+1]_{\epsilon}$ for all
$u\in\Delta(v)$, $\hat{k}=\hat{k}_{1}+1$.

######  Theorem 4.4.

Set $\epsilon=\frac{1}{(w^{2}\log n)^{3}}$, $\epsilon_{h}=2h\epsilon$ and
$\delta_{h}=4(h+1)h\epsilon$. Suppose $n$ is great enough. When the dynamic
programming is done, for all $\alpha$, $\hat{R}_{\alpha}$ satisfies property
(A) and (B).

######  Proof 4.5.

(of Theorem 1.1) According to Theorem 4.4 and the above discussion, we
immediately get $\hat{k}_{\min}\in[OPT,(1+\delta_{h_{0}})^{2}OPT]$. By the
property of nice tree decomposition, $h_{0}$ is at most $O(w^{2}\log n)$, thus
$\hat{k}_{\min}\in[OPT,(1+O(1/(w^{2}\log n)))^{2}OPT]=[OPT,(1+O(1/(w^{2}\log
n)))OPT]$.

The space we need to memorize each $\hat{R}_{\alpha}$ is
$O((w^{6}\log^{4}n)^{w}n^{O(1)})$. Computing a leaf/introduce/join node we
need $O((w^{6}\log^{4}n)^{2w}n^{O(1)})$ time. In a forgetting node, we may
need to enumerate some set $\Delta(v)\subseteq N(v)\cap X_{\alpha}$, which
requires time $O(2^{|X_{\alpha}|})=O(2^{w+1})$. So computing a Forgetting node
requires $O((w^{6}\log^{4}n)^{w}2^{w}n^{O(1)})$ time. The tree size is
polynomial, so the total running time is FPT.

To prove Theorem 4.4, we need a few lemmas. The proof of Lemma 4.6 and Lemma
4.7 are presented in Appendix B.2. Lemma 4.6 and Lemma 4.7 are some simple
observations. To understand why we need Lemma 4.8 and Lemma 4.10, remember
that we have a complicated recursive rule for forgetting nodes in which we
verifies (a) and (b). However, we cannot directly verify if a valid exact
record described in (b) exists, because we don’t have $R_{\alpha_{1}}$. We
overcome this by verifies a feasible partial solution (e.g.
$(d_{1},|Y_{\alpha_{1}}|)$ in (1b)) rather than an optimal one, which can be
done by Lemma 4.2. When we are computing $\hat{R}_{\alpha}$, we assume that
$\hat{R}_{\alpha_{1}}$ has been correctly computed, i.e. it satisfies (A) and
(B). So there exists $(d_{1},k_{1})\in rcds{1}$ which is $h-1$-close to
$(\hat{d}_{1},\hat{k}_{1})$. However, we don’t know if $(d_{1},k_{1})$ is a
so-called valid certificate. Lemma 4.10 shows how to modify $(d_{1},k_{1})$ so
that it becomes we want in (b), knowing $(d_{t},|Y_{\alpha_{1}}|)\in
R_{\alpha_{1}}$. We introduces some error like $o(1)d_{1}(v)$ on $k_{1}$ in
this procedure. Lemma 4.8 helps us to rewrite it as $o(1)k_{1}$.

######  Lemma 4.6.

If $(d,k)\in R_{\alpha}$ for some node $\alpha$, then for every
$({d}^{\prime},k^{\prime})$ with $d(v)\geq{d}^{\prime}(v)$ for all $v\in
X_{\alpha}$ and $k^{\prime}$ satisfying $k\leq k^{\prime}\leq|Y_{\alpha}|$, we
have $({d}^{\prime},k^{\prime})\in R_{\alpha}$.

######  Lemma 4.7.

Let $a,b,a^{\prime},b^{\prime}\in\mathbb{R},h\in\mathbb{N}^{+}$,
$\epsilon_{h}\in[0,1]$, $a^{\prime}\sim_{\epsilon_{h}}a$ and
$b^{\prime}\sim_{\epsilon_{h}}b$. Then we have
$[a^{\prime}+b^{\prime}]_{\epsilon}\sim_{\epsilon_{h+1}}(a+b)$.

######  Lemma 4.8.

For all $(d,k)\in R_{\alpha}$ and $v\in X_{\alpha},k\geq d(v)$.

######  Proof 4.9.

Let $O$ be the orientation. Let $N^{+}(v)=\\{u\in V(G):(v,u)\in E(G)\\}$ be
out neighbors of $v$. By definition, we have $d(v)=|N^{+}(v)|\leq|\\{u\in
Y_{\alpha}\mid D_{O}^{-}(u)>0\\}|\leq k$.

######  Lemma 4.10.

Fix some $(d,k)\in R_{\alpha},v\in X_{\alpha}$ and some integer $p>0$
satisfying $k+p\leq|Y_{\alpha}|$. Let $d_{m}:X_{\alpha}\rightarrow\mathbb{N}$
be a function such that $d_{m}(v)=d(v)+p$ and $d_{m}\setminus v=d\setminus v$.
We have $(d_{m},|Y_{\alpha}|)\in R_{\alpha}$ if and only if $(d_{m},k+p)\in
R_{\alpha}$.

######  Proof 4.11.

On one hand, the ’if’ part is obvious by Lemma 4.6. On the other hand, we
prove that $(d_{m},|Y_{\alpha}|)\in R_{\alpha}$ implies $({d}^{\prime},k+1)\in
R_{\alpha}$, where ${d}^{\prime}(v)=d(v)+1,{d}^{\prime}\setminus v=d\setminus
v$. Then we can repeatedly increase the value of $k$ by $1$ for $p$ times to
obtain the ’only if’ part. Let the orientation corresponding to $(d,k)$ and
$(d_{m},|Y_{\alpha}|)$ be $O_{1},O_{2}$ respectively. Now let $G^{\prime}$ be
a graph with vertex set $Y_{\alpha}\cup\\{v\\}$. A directed edge $(x,y)$ is in
$G^{\prime}$ if and only if $(x,y)\in O_{2}$ and $(y,x)\in O_{1}$.

By picking $O_{1}$ so that the number of edges in $G^{\prime}$ is minimized,
we can assume that $G^{\prime}$ contains no cycle. Otherwise if $G^{\prime}$
contains a cycle, we can reverse every edge along the cycle in $O_{1}$ so that
it is still a valid orientation for $(d,k)$ but the number of edges in
$G^{\prime}$ decreases.

As $D_{O_{2}}^{+}(v)>D_{O_{1}}^{+}(v)$, there exists an non-empty path in
$G^{\prime}$ starting from $v$ ending at, say, $v^{\prime}\neq v$ such that
$v^{\prime}$ has no out edge in $G^{\prime}$. This implies
$D_{O_{1}}^{-}(v^{\prime})\leq D_{O_{2}}^{-}(v^{\prime})-1$, or $v^{\prime}$
will have an out edge in $G^{\prime}$. We reverse the edges along this path in
$O_{1}$. Let the new orientation be $O_{3}$. $D_{O_{3}}^{-}(v^{\prime})\leq
D_{O_{1}}^{-}(v^{\prime})+1\leq D_{O_{2}}^{-}(v^{\prime})\leq c(v)$. Moreover,
$\\{u\mid D_{O_{3}}^{-}(u)>0\\}\setminus\\{u\mid
D_{O_{1}}^{-}(u)>0\\}\subseteq\\{v^{\prime}\\}$. Thus, $O_{3}$ is a valid
orientation for $({d}^{\prime},k+1)$.

###  4.2 Theorem 4.4 Proof Sketch

Due to space limit, the complete proof is presented in Appendix B.2.

We use induction on nodes, following a bottom-up order on the tree
decomposition. Leaf nodes satisfy property (A) and (B), because
$R_{\alpha}=\hat{R}_{\alpha}$ for every leaf node. Fix a node $\alpha$ of
height $h$, by induction, we assume that every node descendent to $\alpha$
satisfies (A) and (B). We only need to prove that $\alpha$ satisfies both (A)
and (B). We make a case distinction based on the type of $\alpha$. The case
where $\alpha$ is a forgetting node is the most complicated and requires lemma
4.8 and 4.10. The other two types follow Lampis’ framework.

To show $\alpha$ satisfies (A), we need to prove the existence of some
$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ for any given $(d,k)\in R_{\alpha}$
such that $(\hat{d},\hat{k})$ and $(d,k)$ are $h$-close. This is done by first
picking up the certificate of $(d,k)$, that is, the record $(d_{1},k_{1})\in
R_{\alpha_{1}}$ (or a pair of records in the case $\alpha$ is a join node, we
omit join node case in the following sketch) which “produces” $(d,k)$ based on
recursive rules for $R_{\alpha}$. Then by induction hypothesis, there is an
$(h-1)$-close record $(\hat{d}_{1},\hat{k}_{1})$ in $\hat{R}_{\alpha_{1}}$. If
$\alpha$ is not a forgetting node, then according to recursive rules for
$\hat{R}_{\alpha}$, there exists $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$. We
prove that $(\hat{d},\hat{k})$ and $(d,k)$ are $h$-close. If $\alpha$ is a
forgetting node, then we verify (1b) or (2b) by applying Lemma 4.6 on
$(d_{1},k_{1})$.

To show $\alpha$ satisfies (B), if $\alpha$ is not a forgetting node, then we
pick up and compare some records in a different order: We start from
$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$; Then we pick
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ according to recursive
rules for $\hat{R}_{\alpha}$; Next we pick $(d_{1},k_{1})\in R_{\alpha_{1}}$
based on induction hypothesis; Finally we find out $(d,k)\in R_{\alpha}$ using
recursive rules for $R_{\alpha}$. If $\alpha$ is a forgetting node, suppose
the record $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ is produced by
$(\hat{d}_{1},\hat{k}_{1})$. The main idea is to apply Lemma 4.10 on
$(d_{t},|Y_{\alpha_{1}}|)$, the record verified by (1b) or (2b), and
$(d_{1},k_{1})$, the record $(h-1)$-close to $(\hat{d}_{1},\hat{k}_{1})$, so
as to show the existence of some $(d,k)\in R_{\alpha}$. At the same time we
use Lemma 4.8 to bound $k$.

##  5 Approximation algorithms for TSS and VDS

In this section, we introduce the _vertex subset problem_ which is a
generalization of many graph problems. Then we present a sufficient condition
for the existence of parameterized approximation algorithms for such problems
parameterized by the treewidth. Finally, we apply our algorithm to target set
selection problem (TSS) and vector dominating set problem (VDS), which are
both vertex subset problems satisfying this condition. The definitions bellow
are inspired by Fomin, et al. [21].

######  Definition 5.1 (Vertex Subset Problem).

A vertex subset problem $\Phi$ takes a string $I\in\\{0,1\\}^{*}$ as an input,
which encodes a graph $G_{I}=(V_{I},E_{I})$ and some possible additional
information, e.g. threshold values on vertices. $\Phi$ is identified by a
function $\mathcal{F}_{\Phi}$ which maps a string $I\in\\{0,1\\}^{*}$ to a
family of vertex subsets of $V_{I}$, say $\mathcal{F}_{\Phi}(I)\subseteq
2^{V_{I}}$. Any vertex set in $\mathcal{F}_{\Phi}(I)$ is a solution of the
instance $I$. The goal is to find a minimum sized solution.

We will often select a set of vertices and assume that it is included in a
solution, and then consider the remaining sub-problem. So we introduce the
concept of partial instances.

######  Definition 5.2 (Partial Vertex Subset Problem).

Let $\Phi$ be a vertex subset problem. The partial version of $\Phi$ takes a
string $I\in\\{0,1\\}^{*}$ appended with a vertex subset $U\subseteq V_{I}$ as
input. We call such a pair $(I,U)$ a partial instance of $\Phi$. Any vertex
set $W\subseteq V_{I}\setminus U$ is a solution if and only if $W\cup
U\in\mathcal{F}_{\Phi}(I)$. Still, the goal is to find a minimum sized
solution.

We consider the following conditions of a vertex subset problem $\Phi$.

  * •

$\Phi$ is monotone, if for any instance $I$, $S\in\mathcal{F}_{\Phi}(I)$
implies for all $S^{\prime}$ satisfying $S\subseteq S^{\prime}\subseteq
V_{I}$, $S^{\prime}\in\mathcal{F}_{\Phi}(I)$.

  * •

$\Phi$ is splittable, if: for any instance $I$ and any separator $X$ of
$G_{I}$ which separates $V_{I}\setminus X$ into disconnected parts
$V_{1},V_{2},...,V_{p}$, if $S_{1},S_{2},...,S_{p}$ are vertex sets such that
$S_{i}$ is a solution for the partial instance $(I,V_{I}\setminus
V_{i}),\forall 1\leq i\leq p$, then $X\cup\bigcup_{1\leq i\leq p}S_{i}$ is a
solution for $I$.

It is trivial to show the monotonicity for TSS and VDS. To see that they are
splittable, observe that given an instance $I=(G,t)$ of VDS for example, fix
some $X\subseteq V(G)$, a set $S$ containing $X$ is a solution for $I$ if and
only if $S\setminus X$ is a solution for $I^{\prime}=(G^{\prime},t^{\prime})$,
where $G^{\prime}=G[V\setminus X]$ and $t^{\prime}(v)=t(v)-|N(v)\cap X|$ for
all $v\in V\setminus X$. If $X$ is a separator, then the graph $G^{\prime}$ is
not connected, and the union of any solutions of each component in
$G^{\prime}$, with $X$ together forms a solution of $I$. This observation also
works for TSS.

The main theorem in this section is to show the tractability, in the sense of
parameterized approximation, of monotone and splittable vertex subset problems
on graphs with bounded treewidth.

######  Theorem 5.3.

Let $\Phi$ be a vertex selection problem which is monotone and splittable. If
there exists an algorithm such that on input a partial instance of $\Phi$
appended with a corresponding nice tree decomposition with width $w$, it can
run in time $f(\ell,w,n)$ and

  * •

either output the optimal solution, if the size of it is at most $\ell$;

  * •

or confirm that the optimal solution size is at least $\ell+1$

then there exists an approximate algorithm for $\Phi$ with ratio
$1+(w+1)/(l+1)$ and runs in time $f(l,w,n)\cdot n^{O(1)}$, for all
$l\in\mathbb{N}$.

We provide a trivial algorithm for the partial version of TSS. Given a partial
instance $(I=(G,t),U)$, we search for a solution of size at most $\ell$ by
brute-force. This takes time $f(\ell,w,n)=n^{\ell+O(1)}$. Setting $l:=C$ in
Theorem 5.3, we simply get the following.

######  Corollary 5.4.

(Restated version of Theorem 1.3) For all constant $C$, TSS admits a
$1+(w+1)/(C+1)$-approximation algorithm running in time $n^{C+O(1)}$.

As mentioned before, Raman et al.[32] showed that VDS is $W[1]$-hard
parameterized by $w$, but FPT with respect to the combined parameter $(k+w)$
where $k$ is the solution size. The running time of their algorithm is
$k^{O(wk^{2})}n^{O(1)}$. A partial instance $(I,U)$ of VDS can be transformed
to an equivalent VDS instance, in which the input graph is $G[V_{I}\setminus
U_{I}]$, so this algorithm can also be used for the partial version of VDS.
Set $l:=w^{2}(\log\log n/\log\log\log n)^{0.5}$ in Theorem 5.3, we get
Corollary 5.5.

######  Corollary 5.5.

(Restated version of Theorem 1.2) Vector Dominating Set admits a
$1+1/(w\log\log n)^{\Omega(1)}$-approximation algorithm running in time
$2^{O(w^{5}\log w\log\log n)}n^{O(1)}$.

Notice that we can’t obtain a $(1+o(1))$-approximation for TSS using a similar
approach, because solving TSS in $f(w+k)n^{O(1)}$-time is $W[1]$-hard [3].

One may also think of applying Theorem 5.3 to CVC, since CVC is FPT when
parameterized by solution size [17]. However, CVC is not splittable. Think of
a simple $3$-vertex graph with vertex set $\\{a,b,c\\}$ and edge set
$\\{\\{a,b\\},\\{b,c\\}\\}$. The capacities are: $c(a)=0,c(b)=1,c(c)=0$.
$\\{b\\}$ is a separator in this graph and empty sets are two solutions for
the two partial instances. However, $\\{b\\}$ cannot cover both two edges in
the original graph.

###  5.1 The Algorithm Framework

To prove Theorem 5.3, we introduce the concept of $l$-good node.

######  Definition 5.6 ($l$-good Node).

Let $I$ be an instance of a vertex selection problem $\Phi$ and
$(T,\mathcal{X})$ be a nice tree decomposition of any subgraph of $G_{I}$. A
node $\alpha\in V(T)$ is an $l$-good node if the partial instance
$(I,V_{I}\setminus Y_{\alpha})$ admits a solution of size at most $l$.

For a node $\alpha$, let $N^{-}_{\alpha}$ denote the set of all children of
$\alpha$. We present the pseudocode of our algorithm in Algorithm 1. Figure 1
in Appendix C illustrates how the sets defined in Algorithm 1 are related.
Algorithm 1 solves the partial version of $\Phi$. For the original version,
when we get an instance $I$, we just create an equivalent partial instance
$(I,\emptyset)$ appended with a nice tree decomposition $(T,\mathcal{X})$ and
an integer $l$, then we run $Solve((I,\emptyset),(T,\mathcal{X}),l)$. The
analyze of Algorithm 1 is presented in Appendix C.

Main idea of Algorithm 1: Let $Alg$ be an algorithm solving partial instances
in time $f(l,w,n)$. Given a partial instance $(I,D)$ and a nice tree
decomposition $(T,\mathcal{X})$ on $G[I\setminus D]$, we run $Alg$ to test the
goodness of each node. If the root node is $l$-good, then $(I,D)$ has a
solution with size at most $l$, we use $Alg$ to find the optimal solution. If
a leaf node is not $l$-good then by monotonicity $I$ has no solution555By our
definition of vertex subset problem, the set of solutions can be empty.
However any instance of TSS or VDS admits at least one solution which is the
whole vertex set..Otherwise, we can pick a lowest node $\alpha$ which is not
$l$-good. Then all its children are $l$-good. Such a node has nice properties.

  * •

On one hand, since all children of $\alpha$ are $l$-good, the partial
instances $(I,V_{I}\setminus Y_{\alpha_{c}})$ can be optimally solved by $Alg$
for each $\alpha_{c}$ a child of $\alpha$. Adding $X_{\alpha_{c}}$ and the
optimal solution $E_{\alpha_{c}}$ for $(I,V_{I}\setminus Y_{\alpha_{c}})$ into
the solution enables us to “discard” the whole subtree rooted by $\alpha_{c}$
and the corresponding vertices, i.e. $V_{\alpha_{c}}$;

  * •

On the other hand, as $\alpha$ is not $l$-good, by the splittable and monotone
properties, we can deduce that the optimal solution $S^{*}$ has an
intersection of size at least $(l+1)$ with $Y_{\alpha}$ i.e. $|S^{*}\cap
Y_{\alpha}|\geq l+1$.

Based on these properties, the algorithm iteratively finds one such node
$\alpha$ and includes $X_{\alpha_{c}}\cup E_{\alpha_{c}}$ for its every child
$\alpha_{c}$ into the solution, then “removes” $V_{\alpha_{c}}$ from the
graph. Once we repeat this procedure, the optimal solution size decreases by
at least $|S^{*}\cap(\bigcup_{\alpha_{c}}V_{\alpha_{c}})|\geq|S^{*}\cap
Y_{\alpha}|\geq l+1$. For each $\alpha_{c}$, we use $Alg$ to find the optimal
solution $E_{\alpha_{c}}$, so in each $Y_{\alpha_{c}}$ we select at most
$|S^{*}\cap Y_{\alpha_{c}}|$ vertices. The “non-optimal” part is
$\bigcup_{\alpha_{c}}X_{\alpha_{c}}$, which is at most
$O(w)=O(w/l)|S^{*}\cap(\bigcup_{\alpha_{c}}V_{\alpha_{c}})|$. Therefore, the
approximation ratio is upper bounded by
$1+\frac{|\bigcup_{\alpha_{c}}X_{\alpha_{c}}|}{l+1}\leq 1+O(w/l)$.

Input: A partial instance $(I,D)$ of $\Phi$, a nice tree decomposition
$(T,\mathcal{X})$ of $G_{I}[V_{I}\setminus D]$ with width $w$,
$l\in\mathbb{N}$ an integer.

Output: A solution $S$ to $(I,D)$, or ’there exists no solution’.

1 for  _each node $\alpha$_ do

2 Use $Alg$ to test if $\alpha$ is an $l$-good node;

3 if  _$\alpha$ is $l$-good_ then

4 $E_{\alpha}:=$ the minimum solution for $(I,V_{I}\setminus Y_{\alpha})$;

5 end if

6

7 end for

8if  _the root $\alpha_{0}$ is $l$-good_ then

9 Return $E_{\alpha_{0}}$;

10 end if

11

12Find a node $\alpha$ which is not $l$-good with minimum height;

13 if  _$\alpha$ is a leaf node_ then

14 Return ’there exists no solution’;

15 end if

16$E^{\prime}:=\emptyset$;

17 $F:=\emptyset$;

18 for  _each $\alpha_{c}\in N^{-}_{\alpha}$_ do

19 $E^{\prime}:=E^{\prime}\cup E_{\alpha_{c}}\cup X_{\alpha_{c}}$;

20 $F:=F\cup V_{\alpha_{c}}$;

21

22 end for

23Find a nice tree decomposition $(T^{\prime},\mathcal{X}^{\prime})$ for
$G_{I}[V_{I}\setminus(D\cup F)]$;

Return $E^{\prime}\cup Solve((I,D\cup
F),(T^{\prime},\mathcal{X}^{\prime}),l)$;

Algorithm 1 Subprocess $Solve()$

## References

  * [1] Karl R. Abrahamson, Rodney G. Downey, and Michael R. Fellows.  Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues.  Ann. Pure Appl. Log., 73(3):235–276, 1995.  doi:10.1016/0168-0072(94)00034-Z.
  * [2] Stefan Arnborg, Jens Lagergren, and Detlef Seese.  Easy problems for tree-decomposable graphs.  Journal of Algorithms, 12(2):308–340, 1991.
  * [3] Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman.  Treewidth governs the complexity of target set selection.  Discrete Optimization, 8(1):87–96, 2011.
  * [4] Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann.  On bounded-degree vertex deletion parameterized by treewidth.  Discrete Applied Mathematics, 160(1-2):53–60, 2012.
  * [5] Hans L Bodlaender.  A linear time algorithm for finding tree-decompositions of small treewidth.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 226–234, 1993.
  * [6] Hans L Bodlaender.  A tourist guide through treewidth.  Acta cybernetica, 11(1-2):1, 1994.
  * [7] Hans L. Bodlaender and Torben Hagerup.  Parallel algorithms with optimal speedup for bounded treewidth.  SIAM J. Comput., 27(6):1725–1746, 1998.  doi:10.1137/S0097539795289859.
  * [8] Moses Charikar, Yonatan Naamad, and Anthony Wirth.  On approximating target set selection.  In Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, volume 60 of LIPIcs, pages 4:1–4:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.APPROX-RANDOM.2016.4.
  * [9] Moses Charikar, Yonatan Naamad, and Anthony Wirth.  On approximating target set selection.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), 2016.
  * [10] Ning Chen.  On the approximability of influence in social networks.  SIAM Journal on Discrete Mathematics, 23(3):1400–1415, 2009.
  * [11] Wang Chi Cheung, Michel X Goemans, and Sam Chiu-wai Wong.  Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1714–1726. SIAM, 2014.
  * [12] Julia Chuzhoy and Joseph Naor.  Covering problems with hard capacities.  SIAM Journal on Computing, 36(2):498–515, 2006.
  * [13] Ferdinando Cicalese, Martin Milanič, and Ugo Vaccaro.  On the approximability and exact algorithms for vector domination and related problems in graphs.  Discrete Applied Mathematics, 161(6):750–767, 2013.
  * [14] Bruno Courcelle.  Graph rewriting: An algebraic and logic approach.  In Formal Models and Semantics, pages 193–242. Elsevier, 1990.
  * [15] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [16] Irit Dinur.  Mildly exponential reduction from gap 3sat to polynomial-gap label-cover.  Electron. Colloquium Comput. Complex., page 128, 2016.  URL: https://eccc.weizmann.ac.il/report/2016/128.
  * [17] Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger.  Capacitated domination and covering: A parameterized perspective.  In International Workshop on Parameterized and Exact Computation, pages 78–90. Springer, 2008.
  * [18] Rodney G Downey and Michael R Fellows.  Fundamentals of parameterized complexity, volume 4.  Springer, 2013.
  * [19] Andreas Emil Feldmann, Euiwoong Lee, and Pasin Manurangsi.  A survey on approximation in parameterized complexity: Hardness and algorithms.  Algorithms, 13(6):146, 2020.
  * [20] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Springer, 2006.
  * [21] Fedor V Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh.  Exact algorithms via monotone local search.  Journal of the ACM (JACM), 66(2):1–23, 2019.
  * [22] Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, and Aravind Srinivasan.  An improved approximation algorithm for vertex cover with hard capacities.  Journal of Computer and System Sciences, 72(1):16–33, 2006.
  * [23] Martin Grohe.  Logic, graphs, and algorithms.  In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], volume 2 of Texts in Logic and Games, pages 357–422. Amsterdam University Press, 2008.
  * [24] Sudipto Guha, Refael Hassin, Samir Khuller, and Einat Or.  Capacitated vertex covering with applications.  In Symposium on Discrete Algorithms: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, volume 6, pages 858–865. Citeseer, 2002.
  * [25] Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke.  Parameterized complexity of generalized vertex cover problems.  In Workshop on Algorithms and Data Structures, pages 36–48. Springer, 2005.
  * [26] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003.
  * [27] Subhash Khot and Oded Regev.  Vertex cover might be hard to approximate to within 2- $\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [28] Tuukka Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 184–192. IEEE, 2022.
  * [29] Michael Lampis.  Parameterized approximation schemes using graph widths.  In International Colloquium on Automata, Languages, and Programming, pages 775–786. Springer, 2014.
  * [30] Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi.  Parameterized complexity and approximability of directed odd cycle transversal.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2181–2200. SIAM, 2020.
  * [31] Pasin Manurangsi and Prasad Raghavendra.  A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 78:1–78:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2017/7463, doi:10.4230/LIPIcs.ICALP.2017.78.
  * [32] Venkatesh Raman, Saket Saurabh, and Sriganesh Srihari.  Parameterized algorithms for generalized domination.  In International Conference on Combinatorial Optimization and Applications, pages 116–126. Springer, 2008.
  * [33] Neil Robertson and Paul D. Seymour.  Graph minors. ii. algorithmic aspects of tree-width.  Journal of algorithms, 7(3):309–322, 1986.
  * [34] Barna Saha and Samir Khuller.  Set cover revisited: Hypergraph cover with hard capacities.  In International Colloquium on Automata, Languages, and Programming, pages 762–773. Springer, 2012.
  * [35] Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and DT Lee.  Tight approximation for partial vertex cover with hard capacities.  In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [36] Sam Chiu-wai Wong.  Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2626–2637. SIAM, 2017.

##  Appendix A Proof Sketch of Theorem 3.2

It is easy to see that $|R_{\alpha}|\leq n^{O(w)}$ for all $\alpha$. And one
execution of a recursive rule takes time at most polynomial of the size of
some $R_{\alpha}$. Thus the total running time is $n^{O(w)}\cdot O(w^{2}\log
n)=n^{O(w)}$.

To prove the correctness, we need to show the record sets computed by the
recursive rules satisfy the expected properties. We use induction. Leaf nodes
are trivial to verify. Fix a node $\alpha$, assume that for every node
descendent to it, the corresponding record set is correctly computed. The
proof then contains the ’if’ part and the ’only if’ part. For the ’if’ part we
have some $O$, $(d,k)$ satisfying the expected properties and aim to prove
$(d,k)$ is included into $R_{\alpha}$ by the recursive rules. The framework is
to extract $O_{1}$ and $(d_{1},k_{1})$ (and $O_{2}$, $(d_{2},k_{2})$ for join
nodes) satisfying the expected properties for the child node(s) and shows that
$(d,k)$ will be add into $R_{\alpha}$ because of $(d_{1},k_{1})$ (and
$(d_{2},k_{2})$). By induction, the extracted record will be included by the
algorithm because they satisfy the expected properties, so $(d,k)$ will also
be included. For the ’only if’ part we have $(d,k)$ included and aim to prove
the existence of a satisfying $O$. The framework is to take the record(s)
based on which $(d,k)$ is added. By induction, the record(s) we take has
corresponding orientation(s) that satisfies the expected properties. We build
$O$ according to this(these) orientation(s).

##  Appendix B Proof of Theorem 4.4

Before the main proof, we prove Lemma 4.6 and Lemma 4.7. Remember that Lemma
4.6 states that if $(d,k)\in R_{\alpha}$ then $(d^{\prime},k^{\prime})\in
R_{\alpha}$ for all $(d^{\prime},k^{\prime})$ with $d(v)\geq
d^{\prime}(v),\forall v\in X_{\alpha}$ and $k\leq k^{\prime}\leq|Y_{\alpha}|$;
Lemma 4.7 states that
$[a^{\prime}+b^{\prime}]_{\epsilon}\sim_{\epsilon_{h+1}}(a+b)$ for
$a,b,a^{\prime},b^{\prime}\in\mathbb{R}$ satisfying
$a^{\prime}\sim_{\epsilon_{h}}a$, $b^{\prime}\sim_{\epsilon_{h}}b$ for
$\epsilon_{h}\in[0,1]$.

######  Proof B.1.

(Lemma 4.6) Let $O$ be the orientation for $(d,k)$. For each $v$, we
arbitrarily select $d(v)-d^{\prime}(v)$ out neighbors of $v$ and reverse each
edge between one selected neighbor and $v$. Let the obtained orientation be
$O_{1}$. We show that $O_{1}$ and $(d^{\prime},k^{\prime})$ satisfies the
properties. (1) and (3) are trivial. To see (2), observe that
$D^{-}_{O_{1}}(v)\leq D^{-}_{O}(v)$ for all $v\in Y_{\alpha}$.

######  Proof B.2.

(Lemma 4.7)
$a^{\prime}+b^{\prime}\in[a/(1+\epsilon_{h})+b/(1+\epsilon_{h}),a(1+\epsilon_{h})+b(1+\epsilon_{h})]$,
that is, $(a^{\prime}+b^{\prime})\sim_{\epsilon_{h}}(a+b)$. As
$[a^{\prime}+b^{\prime}]_{\epsilon}\sim_{\epsilon}(a^{\prime}+b^{\prime})$, we
have
$\max\\{[a^{\prime}+b^{\prime}]_{\epsilon}/(a+b),(a+b)/[a^{\prime}+b^{\prime}]_{\epsilon}\\}\leq(1+\epsilon)(1+\epsilon_{h})=1+\epsilon_{h+1}+\epsilon_{h}\epsilon-\epsilon\leq
1+\epsilon_{h+1}$. Thus
$[a^{\prime}+b^{\prime}]_{\epsilon}\sim_{\epsilon_{h+1}}(a+b)$.

In the following we start the main proof. Leaf nodes satisfy property (A) and
(B) since $R_{\alpha}=\hat{R}_{\alpha}$ for a leaf node $\alpha$. Fix a node
$\alpha$ of height $h$, by induction, we assume that every node descendent to
$\alpha$ satisfies (A) and (B). Now we prove $\alpha$ satisfies both (A) and
(B).

###  B.1 Proof of (A)

Recall that we have some $(d,k)\in R_{\alpha}$ now and we aim to show the
existence of some $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ which is $h$-close to
$(d,k)$. The case for leaf node is trivial. There are three other cases:

Introducing $v$ Node.

Suppose $\alpha$ is an introducing $v$ node and $\alpha_{1}$ is its child,
then we have a certificate $(d_{1},k_{1})\in R_{\alpha_{1}}$, where
$d_{1}=d\setminus v$, $k_{1}=k$. By the induction hypothesis, there exists a
record $(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ which is
$(h-1)$-close to $(d_{1},k_{1})$. By the recursive algorithm for $\hat{R}$,
there exists $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$, where $\hat{d}\setminus
v=\hat{d}_{1},\hat{d}(v)=0$ and $\hat{k}=\hat{k}_{1}$. Note that for all $u\in
X_{\alpha}\setminus\\{v\\},\hat{d}(u)=\hat{d}_{1}(u)\sim_{\epsilon_{h-1}}d_{1}(u)=d(u)$,
thus we have $\hat{d}(u)\sim_{\epsilon_{h}}d(u)$. And $\hat{d}(v)=0=d(v)$.
Since $\hat{k}=\hat{k}_{1}\sim_{\delta_{h-1}}k_{1}=k$, we get
$k\sim_{\delta_{h}}\hat{k}$. So $(\hat{d},\hat{k})$ is $h$-close to $(d,k)$.

Join Node.

If $\alpha$ is a join node with children $\alpha_{1}$ and $\alpha_{2}$, then
we have a certificate $(d_{1},k_{1})\in R_{\alpha_{1}}$ and $(d_{2},k_{2})\in
R_{\alpha_{2}}$, where for all $v\in X_{\alpha},d_{1}(v)+d_{2}(v)=d(v)$ and
$k_{1}+k_{2}=k$. By the induction hypothesis, there exist
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ and
$(\hat{d}_{2},\hat{k}_{2})\in\hat{R}_{\alpha_{2}}$ which are $(h-1)$-close to
$(d_{1},k_{1})$ and $(d_{2},k_{2})$ respectively. Note that
$(\hat{d}_{1},\hat{k}_{1}),(\hat{d}_{2},\hat{k}_{2})$ is a valid certificate,
so there exists $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$, where for all $v\in
X_{\alpha}$, $\hat{d}(v)=[\hat{d}_{1}(v)+\hat{d}_{2}(v)]_{\epsilon}$ and
$\hat{k}=\hat{k}_{1}+\hat{k}_{2}$. By Lemma 4.7, for all $v\in X_{\alpha}$,
$\hat{d}(v)\sim_{\epsilon_{h}}d(v)$ and $\hat{k}\sim_{\delta_{h}}k$.

Forgetting Node.

If $\alpha$ is a forgetting $v$ node with child $\alpha_{1}$, then we have a
certificate $(d_{1},k_{1})\in R_{\alpha_{1}}$ which satisfies one of the
following conditions:

(1)

$d_{1}(v)=|N(v)\cap Y_{\alpha}|,d_{1}\setminus v=d$ and $k_{1}=k$.

(2)

There exist $\Delta(v)\subseteq N(v)\cap X_{\alpha}$ and $A\in[|N(v)\cap
Y_{\alpha}|-c(v)+|\Delta(v)|,|N(v)\cap Y_{\alpha}|]$ such that for all
$u\in\Delta(v),d_{1}(u)=d(u)-1$ and for all $u\in
X_{\alpha_{1}}\setminus(\Delta(v)\cup\\{v\\}),d_{1}(u)=d(u),d_{1}(v)=A$ and
$k_{1}=k-1$.

Notice that these two conditions just correspond to the recursive rules with
the same index. By the induction hypothesis, there exists an approximate
counterpart of the certificate. To be specific, there exists
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ which is $(h-1)$-close to
$(d_{1},k_{1})$. Consider two sub-cases:

Type (1) certificate. As $(\hat{d}_{1},\hat{k}_{1})$ is $(h-1)$-close to
$(d_{1},k_{1})$ and $d_{1}(v)=|N(v)\cap Y_{\alpha}|$, we have
$\hat{d}_{1}(v)\sim_{\epsilon_{h-1}}|N(v)\cap Y_{\alpha}|$, which means (1a)
is satisfied. Let $(d_{t},|Y_{\alpha_{1}}|)$ be the tested pair in (1b). By
the definition of $(d_{t},|Y_{\alpha_{1}}|)$, for all $u\in
X_{\alpha_{1}}\setminus\\{v\\},d_{t}(u)=\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil\leq\lceil(1+\epsilon_{h-1})d_{1}(u)/(1+\epsilon_{h-1})\rceil=d_{1}(u)$,
and $d_{t}(v)=d_{1}(v)=|N(v)\cap Y_{\alpha}|$. Also observe that
$k_{1}\leq|Y_{\alpha_{1}}|$. Thus by Lemma 4.6, $(d_{t},|Y_{\alpha_{1}}|)\in
R_{\alpha_{1}}$, which means (1b) is satisfied. As (1a), (1b) are satisfied,
there exists $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$, where
$\hat{d}=\hat{d}_{1}\setminus v,\hat{k}=\hat{k}_{1}$. Finally, observe that
for all $u\in
X_{\alpha},d(u)=d_{1}(u)\sim_{\epsilon_{h-1}}\hat{d}_{1}(u)=\hat{d}(u)$.
$k=k_{1}\sim_{\delta_{h-1}}\hat{k}_{1}=\hat{k}$. So $(d,k)$ and
$(\hat{d},\hat{k})$ are $h$-close.

Type (2) certificate. As $(\hat{d}_{1},\hat{k}_{1})$ is $(h-1)$-close to
$(d_{1},k_{1})$ and $d_{1}(v)=A$, we have $\hat{d}_{1}(v)\geq
A/(1+\epsilon_{h-1})$, which means (2a) is satisfied. Let
$(d_{t},|Y_{\alpha_{1}}|)$ be the tested pair in (2b), i.e. for all $u\in
X_{\alpha_{1}}\setminus\\{v\\},d_{t}(u)=\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil$
and $d_{t}(v)=A$. Similarly we have that $d_{1}(u)\geq d_{t}(u)$ for all $u\in
X_{\alpha}$ while $k_{1}\leq|Y_{\alpha_{1}}|$. Thus by Lemma 4.6,
$(d_{t},|Y_{\alpha_{1}}|)\in R_{\alpha_{1}}$, which means (2b) is satisfied.
As (2a), (2b) are satisfied, there exists
$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$, where
$\hat{d}(u)=[\hat{d}_{1}(u)+1]_{\epsilon}$ for all $u\in
X_{\alpha}\setminus\Delta(v)$, $\hat{d}(u)=\hat{d}_{1}(u)$ for all
$u\in\Delta(v)$, and $\hat{k}=\hat{k}_{1}+1$. For each $u\in\Delta(v)$,
$d(u)=d_{1}(u)\sim_{\epsilon_{h-1}}\hat{d}_{1}(u)=\hat{d}(u)$; for all $u\in
X_{\alpha}\setminus\Delta(v)$, $d(u)\sim_{\epsilon_{h}}\hat{d}(u)$ by Lemma
4.7; $k-1=k_{1}\sim_{\delta_{h-1}}\hat{k}_{1}=\hat{k}-1$ and thus
$k\sim_{\delta_{h}}\hat{k}$. So $(d,k)$ and $(\hat{d},\hat{k})$ are $h$-close.

###  B.2 Proof of (B)

Now we have some $(\hat{d},\hat{k})\in\hat{R}_{\alpha}$ and we aim to show the
existence of some $(d,k)\in R_{\alpha}$ which is $h$-close to
$(\hat{d},\hat{k})$.

Introducing $v$ Node.

Suppose $\alpha$ is an introducing $v$ node with $\alpha_{1}$ as its child,
then by the the recursive rules we have a certificate
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$, where
$\hat{d}_{1}=\hat{d}\setminus v$, $\hat{k}_{1}=\hat{k}$. By induction
hypothesis, there exists $(d_{1},k_{1})\in R_{\alpha_{1}}$ which is
$(h-1)$-close to $(\hat{d}_{1},\hat{k}_{1})$. $(d_{1},k_{1})$ is a valid
certificate, so there exists $(d,k)\in R_{\alpha}$, where $d\setminus
v=d_{1},d(v)=0$ and $k=k_{1}$. For all $u\in
X_{\alpha}\setminus\\{v\\},d(u)=d_{1}(u)\sim_{\epsilon_{h-1}}\hat{d}_{1}(u)=\hat{d}(u)$
so $\hat{d}(u)\sim_{\epsilon_{h}}d(u)$; $\hat{d}(v)=0=d(v)$;
$k=k_{1}\sim_{\delta_{h-1}}\hat{k}_{1}=\hat{k}$, so
$k\sim_{\delta_{h}}\hat{k}$.

Join Node.

If $\alpha$ is a join node with $\alpha_{1}$ and $\alpha_{2}$ as its children,
then we have a certificate
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha},(\hat{d}_{2},\hat{k}_{2})\in\hat{R}_{\alpha_{2}}$,
where for all $v\in
X_{\alpha},[\hat{d}_{1}(v)+\hat{d}_{2}(v)]_{\epsilon}=\hat{d}(v)$ and
$\hat{k}_{1}+\hat{k}_{2}=\hat{k}$. By induction hypothesis, there exist
$(d_{1},k_{1})\in R_{\alpha_{1}},(d_{2},k_{2})\in R_{\alpha_{2}}$ which are
$(h-1)$-close to $(\hat{d}_{1},\hat{k}_{1})$ and $(\hat{d}_{2},\hat{k}_{2})$
respectively. Since $(d_{1},k_{1}),(d_{2},k_{2})$ is a valid certificate, we
have there exists $(d,k)\in R_{\alpha}$, where for all $v\in
X_{\alpha},d(v)=d_{1}(v)+d_{2}(v)$ and $k=k_{1}+k_{2}$. By Lemma 4.7, for all
$v\in X_{\alpha},d(v)\sim_{\epsilon_{h}}\hat{d}(v)$. And
$k\sim_{\delta_{h}}\hat{k}$.

Forgetting $v$ Node.

If $\alpha$ is a forgetting $v$ node, then we have a certificate
$(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ and a tested pair
$(d_{t},|Y_{\alpha_{1}}|)\in R_{\alpha_{1}}$ in (1b) or (2b) with one of the
following types:

(1)

$\hat{d}_{1}(v)\sim_{\epsilon_{h-1}}|N(v)\cap Y_{\alpha}|;\hat{d}_{1}\setminus
v=\hat{d}$; $\hat{k}_{1}=\hat{k}$; $d_{t}(v)=|N(v)\cap Y_{\alpha}|$;

(2)

there exists $\Delta(v)\subseteq N(v)\cap X_{\alpha}$ and $A\in[|N(v)\cap
Y_{\alpha}|-c(v)+|\Delta(v)|,|N(v)\cap Y_{\alpha}|]$ such that for all
$u\in\Delta(v),\hat{d}(u)=[\hat{d}_{1}(u)+1]_{\epsilon}$; for all $u\in
X_{\alpha_{1}}\setminus\Delta(v)\cup\\{v\\},\hat{d}_{1}(u)=\hat{d}(u);\hat{d}_{1}(v)\geq
A/(1+\epsilon_{h-1})$; $\hat{k}_{1}=\hat{k}-1$; $d_{t}(v)=A$.

In both types, for all $u\in
X_{\alpha_{1}}\setminus\\{v\\},d_{t}(u)=\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil$.
Notice that these two types just correspond to the recursive rules with the
same index. By induction hypothesis, there exists $(d_{1},k_{1})\in
R_{\alpha_{1}}$ which is $(h-1)$-close to $(\hat{d}_{1},\hat{k}_{1})$. By the
definition of $(h-1)$-closeness we have that for every $u\in
X_{\alpha_{1}}\setminus\\{v\\},d_{1}(u)\geq\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil=d_{t}(u)$.
Consider the two cases:

Type (1) certificate and tested pair.

In this case $d_{t}(v)=|N(v)\cap Y_{\alpha}|$ and
$\hat{d}_{1}(v)\sim_{\epsilon_{h-1}}|N(v)\cap Y_{\alpha}|$. Notice that for
all $u\in
X_{\alpha_{1}}\setminus\\{v\\},d_{t}(u)=\lceil\hat{d}_{1}(u)/(1+\epsilon_{h-1})\rceil\leq
d_{1}(u)$. Consider the pair $(d_{t},k_{1}^{*})$ where
$k_{1}^{*}=k_{1}+|N(v)\cap Y_{\alpha}|-d_{1}(v)$. As
$(d_{1},k_{1}),(d_{t},|Y_{\alpha_{1}}|)\in R_{\alpha_{1}}$, by Lemma 4.6 and
4.10, we have $(d_{t},k_{1}^{*})\in R_{\alpha_{1}}$. This is a valid
certificate as $d_{t}(v)=|N(v)\cap Y_{\alpha}|$. So there exists $(d,k)\in
R_{\alpha}$, where $d=d_{t}\setminus v$ and $k=k_{1}^{*}$.

Then we show that $(d,k)$ is $h$-close to $(\hat{d},\hat{k})$. Notice that
$\hat{k}=\hat{k}_{1}\sim_{\delta_{h-1}}k_{1},k=k_{1}^{*}=k_{1}+|N(v)\cap
Y_{\alpha}|-d_{1}(v)$. As $d_{1}(v)\sim_{\epsilon_{h-1}}\hat{d}_{1}(v)$, thus
$d_{1}(v)\geq|N(v)\cap Y_{\alpha}|/(1+\epsilon_{h-1})^{2}$, thus we have that
$|N(v)\cap Y_{\alpha}|-d_{1}(v)\leq((1+\epsilon_{h-1})^{2}-1)d_{1}(v)\leq
3\epsilon_{h-1}k_{1}$. Notice that $d_{1}(v)\leq k_{1}$ by Lemma 4.8. So
$k\sim_{3\epsilon_{h-1}}k_{1}\sim_{\delta_{h-1}}\hat{k}_{1}=\hat{k}$. As
$(1+3\epsilon_{h-1})(1+\delta_{h-1})=1+(4h+6)(h-1)\epsilon+24h(h-1)^{2}\epsilon^{2}\leq
1+4h(h+1)\epsilon$, we have $\hat{k}\sim_{\delta_{h}}k$.

For all $u\in X_{\alpha}$, we just have
$d(u)=d_{t}(u)\sim_{\epsilon_{h-1}}\hat{d}_{1}(u)=\hat{d}(u)$.

Type (2) certificate and tested pair.

In this case, there exists $\Delta(v)\subseteq N(v)\cap X_{\alpha}$ and
$A\in[|N(v)\cap Y_{\alpha}|-c(v)+|\Delta(v)|,|N(v)\cap Y_{\alpha}|]$ such that
$d_{t}(v)=A$. Still we have that for all $u\in
X_{\alpha_{1}}\setminus\\{v\\},d_{t}(u)\leq d_{1}(u)$. Let
$k_{1}^{*}:=k_{1}+\max\\{0,A-d_{1}(v)\\}$. As
$(d_{1},k_{1}),(d_{t},|Y_{\alpha_{1}}|)\in R_{\alpha_{1}}$, by Lemma 4.6 and
4.10, we have $(d_{t},k_{1}^{*})\in R_{\alpha_{1}}$. This is a valid
certificate as $d_{t}(v)=A$. So there exists $(d,k)\in R_{\alpha}$, where for
all $u\in X_{\alpha}\setminus\Delta(v),d(u)=d_{t}(u)$, for all
$u\in\Delta(v),d(u)=d_{t}(u)+1$ and $k=k_{1}^{*}+1$.

We use the same idea to show $\hat{k}\sim_{\delta_{h}}k$. Still, we have
$k_{1}\geq d_{1}(v)\geq A/(1+\epsilon_{h-1})^{2}$. So
$k_{1}^{*}=k_{1}+\max\\{0,A-d_{1}(v)\\}\leq 3\epsilon_{h-1}k_{1}$ and
obviously, $k_{1}^{*}\geq k_{1}$. So $k_{1}^{*}\sim_{3\epsilon_{h-1}}k_{1}$.
As $\hat{k}-1=\hat{k}_{1}\sim_{\delta_{h-1}}k_{1}$, we have
$\hat{k}-1\sim_{\delta_{h}}k_{1}^{*}=k-1$. Thus $\hat{k}\sim_{\delta_{h}}k$.

For all $u\in X_{\alpha}\setminus\Delta(v)$, we have
$d(u)={d_{1}}^{*}(u)\sim_{\epsilon_{h-1}}\hat{d}_{1}(u)=\hat{d}$. For all
$u\in\Delta(v)$, we have
$d(u)-1={d_{1}}^{*}(u)\sim_{\epsilon_{h-1}}\hat{d}_{1}(u)$ and
$\hat{d}(u)=[\hat{d}_{1}(u)+1]_{\epsilon}$, by Lemma 4.7 we have
$d(u)\sim_{\epsilon_{h}}\hat{d}(u)$.

Remark The above proof actually provides the intuition of how to modify our
algorithm so that it outputs a solution of size at most
$(1+\delta_{h_{0}})^{2}OPT$. The idea is to, for all $\alpha\in V(T)$ and all
$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$, keep track of an exact $h$-close
record $(d,k)$ of $(\hat{d},\hat{k})$ and its corresponding orientation i.e.
an orientation $O$ with which $(d,k)$ satisfies the expected properties.
Still, this is done by a bottom-up dynamic programming. Fix a non-leaf node
$\alpha$, suppose that for all its children, this has been done. Now suppose
we want to find that orientation for a record
$(\hat{d},\hat{k})\in\hat{R}_{\alpha}$. According to the recursive rules,
there exists $(\hat{d}_{1},\hat{k}_{1})\in\hat{R}_{\alpha_{1}}$ (and
$(\hat{d}_{2},\hat{k}_{2})\in\hat{R}_{\alpha_{2}}$ for join nodes) from which
we construct $(\hat{d}_{1},\hat{k}_{1})$. Proof of (B) in fact shows that if
the exact $h-1$-close exact counterpart and the corresponding orientation has
been stored, then we can construct the $h$-close record $(d,k)\in R_{\alpha}$
and its corresponding orientation. Notice that if $\alpha$ is the forgetting
node we may need Lemma 4.10 to prove the existence of such $(d,k)$. But
fortunately, Lemma 4.10 is also constructive.

##  Appendix C Proof of Theorem 5.3

We first prove that for any bag $X_{\alpha}$ in a tree decomposition for a
graph $G=(V,E)$, vertex sets $Y_{\alpha}$ and $V\setminus V_{\alpha}$ are
disconnected in $G[V\setminus X_{\alpha}]$ i.e. $X_{\alpha}$ separates
$V\setminus X_{\alpha}$ into two disconnected parts $Y_{\alpha}$ and
$V\setminus V_{\alpha}$. Assume they are connected, then there exists $u\in
Y_{\alpha}$ and $v\in V\setminus V_{\alpha}$ such that $(u,v)\in E$. So there
exists some bag containing both $u$ and $v$. This implies that the nodes whose
assigned bags containing $u$ or $v$ forms a subtree in the tree decomposition.
However, $X$ divides apart some nodes whose assigned bags containing $u$ or
$v$, a contradiction.

Since $(T,\mathcal{X})$ is a tree decomposition for $G_{I}[V_{I}\setminus D]$,
a corollary is that for any node $\alpha\in V(T)$, $X_{\alpha}\cup D$
separates $V_{I}\setminus(D\cup X_{\alpha})$ into disconnected parts
$Y_{\alpha}$ and $V_{I}\setminus(V_{\alpha}\cup D)$.

Now we analyze Algorithm 1. We use induction. Firstly let’s consider basic
cases. If $(I,D)$ has a minimum solution of size at most $l$, then the
algorithm returns at line $8$ an optimal solution. If $(I,D)$ contains no
solution, which is equivalent to $V_{I}$ is not a solution due to
monotonicity, then any leaf node is not $l$-good since
$Y_{\alpha^{\prime}}=\emptyset$ for a leaf node $\alpha^{\prime}$ and the
algorithm returns at line $12$. So in these cases, the algorithm is correct.
In the remaining case, the algorithm picks a node $\alpha$ which is not
$l$-good at line 10, then it adds some vertices to the final output and
creates a new instance to make a recursive call. Since $\alpha$ is the node
which is not $l$-good node with minimum height, its children are all $l$-good.
Let the optimal solution for $(I,D)$ be $S^{*}$. Let $S:=Solve((I,D\cup
F),(T^{\prime},\mathcal{X}),l)$ and let $S^{\prime}$ denote the optimal
solution for $(I,D\cup F)$.

######  Lemma C.1.

As the problem is monotone and splittable, we have the following:

  1. (i)

$S^{*}\cap Y_{\alpha}$ is a solution for $(I,V_{I}\setminus Y_{\alpha})$.

  2. (ii)

For all $\alpha_{c}$ a child of $\alpha$, $S^{*}\cap Y_{\alpha_{c}}$ is a
solution for $(I,V_{I}\setminus Y_{\alpha_{c}})$;

  3. (iii)

$S^{*}\setminus F$ is a solution for $(I,D\cup F)$;

  4. (iv)

$E^{\prime}\cup S$ is a solution for $(I,D)$.

######  Proof C.2.

  1. (i)

By the definition of partial instances, $S^{*}\cup D$ is a solution for $I$.
By monotonicity, $S^{*}\cup D\cup(V_{I}\setminus Y_{\alpha})=S^{*}\cap
Y_{\alpha}\cup(V_{I}\setminus Y_{\alpha})$ is also a solution for $I$. So
$S^{*}\cap Y_{\alpha}$ is a solution for $(I,V_{I}\setminus Y_{\alpha})$
according to the definition of partial solution.

  2. (ii)

Similarly as above, by monotonicity, $S^{*}\cup D\cup(V_{I}\setminus
Y_{\alpha_{c}})=S^{*}\cap Y_{\alpha_{c}}\cup(V_{I}\setminus Y_{\alpha_{c}})$
is also a solution for $I$. So $S^{*}\cap Y_{\alpha_{c}}$ is a solution for
$(I,V_{I}\setminus Y_{\alpha_{c}})$.

  3. (iii)

By monotonicity, $S^{*}\cup D\cup F$ is also a solution for $I$. So
$S^{*}\setminus F$ is a solution for $(I,D\cup F)$.

  4. (iv)

We need to use the property that $\Phi$ is splittable. By the algorithm,
$E^{\prime}=\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}X_{\alpha_{c}}\cup\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}E_{\alpha_{c}}$ and $F=\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}V_{\alpha_{c}}$. Let $X^{\prime}$ denote $\cup_{\alpha_{c}\in
N^{-}_{\alpha}}X_{\alpha_{c}}$. To use the property that $\Phi$ is splittable,
observe that $D\cup X^{\prime}$ is a separator. Each $Y_{\alpha_{c}}$ is an
isolated part (not connected to the remaining graph) in
$G_{I}[V_{I}\setminus(D\cup X^{\prime})]$. The remaining part in
$G_{I}[V_{I}\setminus(D\cup X^{\prime})]$ is thus isolated and it is
$V_{I}\setminus(D\cup X^{\prime}\cup\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}Y_{\alpha_{c}})=V_{I}\setminus(D\cup F)$. Because each
$E_{\alpha_{c}}$ is a solution for $(I,V_{I}\setminus Y_{\alpha_{c}})$, and by
induction hypothesis, $S$ is a solution for $(I,D\cup F)$, we get that $\Phi$
is splittable implies $X^{\prime}\cup D\cup S\cup\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}E_{\alpha_{c}}=E^{\prime}\cup D\cup S$ is a solution for $I$.
So $E^{\prime}\cup S$ is a solution for $(I,D)$.

By induction we assume that $|S|\leq(1+(w+1)/(l+1))|S^{\prime}|$. The
approximation ratio is

$\displaystyle\frac{|S\cup
E^{\prime}|}{|S^{*}|}\leq\frac{|S|+\sum_{\alpha_{c}\in
N^{-}_{\alpha}}|E_{\alpha_{c}}|+|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}{X_{\alpha_{c}}}|}{|S^{*}\cap F|+|S^{*}\setminus F|}.$

Since $|S|/|S^{*}\setminus F|\leq|S|/|S^{\prime}|\leq 1+(w+1)/(l+1)$, we only
need to show $(\sum_{\alpha_{c}\in
N^{-}_{\alpha}}|E_{\alpha_{c}}|+|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}{X_{\alpha_{c}}}|)/|S^{*}\cap F|\leq 1+(w+1)/(l+1)$. Notice
that by the definition, $Y_{\alpha}\subseteq F$. Since $\alpha$ is not
$l$-good, (i) implies that $|S^{*}\cap F|\geq|S^{*}\cap Y_{\alpha}|\geq l+1$.
By (ii), for all $\alpha_{c}\in N^{-}_{\alpha}$,
$|E_{\alpha_{c}}|\leq|S^{*}\cap Y_{\alpha_{c}}|$. We have

$\displaystyle\frac{\sum_{\alpha_{c}\in
N^{-}_{\alpha}}|E_{\alpha_{c}}|+|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}{X_{\alpha_{c}}}|}{|S^{*}\cap F|}$ $\displaystyle=$
$\displaystyle\frac{\sum_{\alpha_{c}\in
N^{-}_{\alpha}}|E_{\alpha_{c}}|}{|S^{*}\cap F|}+\frac{|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}X_{\alpha_{c}}|}{|S^{*}\cap F|}$ $\displaystyle\leq$
$\displaystyle\frac{\sum_{\alpha_{c}\in
N^{-}_{\alpha}}|E_{\alpha_{c}}|}{\sum_{\alpha_{c}\in N^{-}_{\alpha}}|S^{*}\cap
Y_{\alpha_{c}}|}+\frac{|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}X_{\alpha_{c}}|}{|S^{*}\cap F|}\text{ ($Y_{\alpha_{c}}$'s are
disjoint subsets of $F$)}$ $\displaystyle\leq$ $\displaystyle
1+\frac{|\bigcup_{\alpha_{c}\in N^{-}_{\alpha}}X_{\alpha_{c}}|}{|S^{*}\cap
F|}\text{ (By (ii) and the definition of $E_{\alpha_{c}}$)}$
$\displaystyle\leq$ $\displaystyle 1+\frac{|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}X_{\alpha_{c}}|}{l+1}\text{ (By $|S^{*}\cap F|\geq l+1$)}.$

In a nice tree decomposition, the only case that $|N^{-}_{\alpha}|>1$ is that
$\alpha$ is a join node, however in this case, the bags of its two children
are the same. So ${|\bigcup_{\alpha_{c}\in
N^{-}_{\alpha}}X_{\alpha_{c}}|}/(l+1)+1\leq(w+1)/(l+1)+1$. The approximation
ratio follows. Each time we make a recursive call, the optimal solution size
for the current instance decreases by at least $1$. It follows that the
algorithm makes at most $O(n)$ recursive calls, so the running time is
$f(l,w,n)n^{O(1)}$. And thus Theorem 5.3 is proved.

(a) $T$ in a tree decomposition $(T,\mathcal{X})$.

(b) The vertex sets about $\alpha$ and $\alpha_{c}$. Dotted part is
$Y_{\alpha}$

(c) $E_{\alpha_{c}}$ is added, and $F$ is the lined part.

Figure 1: Venn diagram of sets defined in Algorithm 1