Simultaneous Feedback Vertex Set: A Parameterized Perspective
Akanksha Agrawal1 , Daniel Lokshtanov1 , Amer E. Mouawad1 , and Saket Saurabh1,2
1

arXiv:1510.01557v1 [] 6 Oct 2015

University of Bergen
Bergen, Norway.
{akanksha.agrawal|daniel.lokshtanov|a.mouawad}@uib.no
2
Institute of Mathematical Sciences
Chennai, India.
saket@imsc.res.in

Abstract. Given a family of graphs F, a graph G, and a positive integer k, the F-Deletion problem
asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes
many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle
Transversal. A graph G = (V, ∪α
i=1 Ei ), where the edge set of G is partitioned into α color classes,
is called an α-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored
graphs is the α-Simultaneous F-Deletion problem. In the latter problem, we are given an α-edgecolored graph G and the goal is to find a set S of at most k vertices such that each graph Gi \ S, where
Gi = (V, Ei ) and 1 ≤ i ≤ α, is in F. In this work, we study α-Simultaneous F-Deletion for F
being the family of forests. In other words, we focus on the α-Simultaneous Feedback Vertex Set
(α-SimFVS) problem. Algorithmically, we show that, like its classical counterpart, α-SimFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant
α. In particular, we give an algorithm running in 2O(αk) nO(1) time and a kernel with O(αk3(α+1) )
vertices. The running time of our algorithm implies that α-SimFVS is FPT even when α ∈ o(log n). We
complement this positive result by showing that for α ∈ O(log n), where n is the number of vertices in
the input graph, α-SimFVS becomes W[1]-hard. Our positive results answer one of the open problems
posed by Cai and Ye (MFCS 2014).

1

Introduction

In graph theory, one can define a general family of problems as follows. Let F be a collection of graphs.
Given an undirected graph G and a positive integer k, is it possible to perform at most k edit operations
to G so that the resulting graph does not contain a graph from F? Here one can define edit operations as
either vertex/edge deletions, edge additions, or edge contractions. Such problems constitute a large fraction
of problems considered under the parameterized complexity framework. When edit operations are restricted
to vertex deletions this corresponds to the F-Deletion problem, which generalizes classical graph problems
such as Vertex Cover [6], Feedback Vertex Set [5, 8, 18], Vertex Planarization [24], Odd Cycle
Transversal [19, 21], Interval Vertex Deletion [4], Chordal Vertex Deletion [22], and Planar
F-Deletion [11, 17]. The topic of this paper is a generalization of F-Deletion problems to “edge-colored
graphs”. In particular, we do a case study of an edge-colored version of the classical Feedback Vertex
Set problem [12].
A graph G = (V, ∪α
i=1 Ei ), where the edge set of G is partitioned into α color classes, is called an αedge-colored graph. As stated by Cai and Ye [3], “edge-colored graphs are fundamental in graph theory
and have been extensively studied in the literature, especially for alternating cycles, monochromatic subgraphs, heterchromatic subgraphs, and partitions”. A natural extension of the F-Deletion problem to
edge-colored graphs is the α-Simultaneous F-Deletion problem. In the latter problem, we are given an
α-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph Gi \S, where
Gi = (V, Ei ) and 1 ≤ i ≤ α, is in F. Cai and Ye [3] studied several problems restricted to 2-edge-colored
graphs, where edges are colored either red or blue. In particular, they consider the Dually Connected
Induced Subgraph problem, i.e. find a set S of k vertices in G such that both induced graphs Gred [S]
and Gblue [S] are connected, and the Dual Separator problem, i.e. delete a set S of at most k vertices

to simultaneously disconnect the red and blue graphs of G. They show, among other results, that Dual
Separator is NP-complete and Dually Connected Induced Subgraph is W[1]-hard even when both
Gred and Gblue are trees. On the positive side, they prove that Dually Connected Induced Subgraph
is solvable in time polynomial in the input size when G is a complete graph. One of the open problems they
state is to determine the parameterized complexity of α-Simultaneous F-Deletion for α = 2 and F the
family of forests, bipartite graphs, chordal graphs, or planar graphs. The focus in this work is on one of those
problems, namely α-Simultaneous Feedback Vertex Set— an interesting, and well-motivated [2, 3, 16],
generalization of Feedback Vertex Set on edge-colored graphs.
A feedback vertex set is a subset S of vertices such that G \ S is a forest. For an α-colored graph G, an
α-simultaneous feedback vertex set (or α-simfvs for short) is a subset S of vertices such that Gi \ S is a forest
for each 1 ≤ i ≤ α. The α-Simultaneous Feedback Vertex Set is stated formally as follows.
α-Simultaneous Feedback Vertex Set (α-SimFVS)
Parameter: k
Input: (G, k), where G is an undirected α-colored graph and k is a positive integer
Question: Is there a subset S ⊆ V (G) of size at most k such that for 1 ≤ i ≤ α, Gi \ S is a forest?
Given a graph G = (V, E) and a positive integer k, the classical Feedback Vertex Set (FVS) problem
asks whether there exists a set S of at most k vertices in G such that the graph induced on V (G) \ S is
acyclic. In other words, the goal is to find a set of at most k vertices that intersects all cycles in G. FVS
is a classical NP-complete [12] problem with numerous applications and is by now very well understood
from both the classical and parameterized complexity [10] view points. For instance, the problem admits a
2-approximation algorithm [1], an exact (non-parameterized) algorithm running in O? (1.736n ) time [29], a
deterministic algorithm running in O? (3.619k ) time [18], a randomized algorithm running in O? (3k ) time [8],
and a kernel on O(k 2 ) vertices [27] (see Section 2 for definitions). We use the O? notation to describe the
running times of our algorithms. Given f : N → N, we define O? (f (n)) to be O(f (n) · p(n)), where p(·)
is some polynomial function. That is, the O? notation suppresses polynomial factors in the running-time
expression.
Our results and methods. We show that, like its classical counterpart, α-SimFVS parameterized by k is
FPT and admits a polynomial kernel, for any fixed constant α. In particular, we obtain the following results.
– An FPT algorithm running in O? (23αk ) time. For the special case of α = 2, we give a faster algorithm
running in O? (81k ) time.
– For constant α, we obtain a kernel with O(αk 3(α+1) ) vertices.
– The running time of our algorithm implies that α-SimFVS is FPT even when α ∈ o(log n). We complement this positive result by showing that for α ∈ O(log n), where n is the number of vertices in the
input graph, α-SimFVS becomes W[1]-hard.
Our algorithms and kernel build on the tools and methods developed for FVS [7]. However, we need to
develop both new branching rules as well as a new reduction rules. The main reason why our results do not
follow directly from earlier work on FVS is the following. Many (if not all) parameterized algorithms, as
well as kernelization algorithms, developed for the FVS problem [7] exploit the fact that vertices of degree
two or less in the input graph are, in some sense, irrelevant. In other words, vertices of degree one or zero
cannot participate in any cycle and every cycle containing any degree-two vertex must contain both of its
neighbors. Hence, if this degree-two vertex is part of a feedback vertex set then it can be replaced by either
one of its neighbors. Unfortunately (or fortunately for us), this property does not hold for the α-SimFVS
problem, even on graphs where edges are bicolored either red or blue. For instance, if a vertex is incident
to two red edges and two blue edges, it might in fact be participating in two distinct cycles. Hence, it is
not possible to neglect (or shortcut) this vertex in neither Gred nor Gblue . As we shall see, most of the new
algorithmic techniques that we present deal with vertices of exactly this type. Although very tightly related
to one another, we show that there are subtle and interesting differences separating the FVS problem from
the α-SimFVS problem, even for α = 2. For this reason, we also believe that studying α-Simultaneous
F-Deletion for different families of graphs F, e.g. bipartite, chordal, or planar graphs, might reveal some
new insights about the classical underlying problems.
2

In Section 3, we present an algorithm solving the α-SimFVS problem, parameterized by solution size k,
in O? (23αk ) time. Our algorithm follows the iterative compression paradigm introduced by Reed et al. [26]
combined with new reduction and branching rules. Our main new branching rule can be described as follows:
Given a maximal degree-two path in some Gi , 1 ≤ i ≤ α, we branch depending on whether there is a vertex
from this path participating in an α-simultaneous feedback vertex set or not. In the branch where we guess
that a solution contains a vertex from this path, we construct a color i cycle which is isolated from the
rest of the graph. In the other branch, we are able to follow known strategies by “simulating” the classical
FVS problem. Observe that we can never have more than k isolated cycles of the same color. Hence, by
incorporating this fact into our measure we are guaranteed to make “progress” in both branches. For the base
case, each Gi is a disjoint union of cycles (though not G) and to find an α-simultaneous feedback vertex set
for G we cast the remaining problem as an instance of Hitting Set parameterized by the size of the family.
For α = 2, we can instead use an algorithm for finding maximum matchings in an auxiliary graph. Using
this fact we give a faster, O? (81k ) time, algorithm for the case α = 2. In Section 4, we tackle the question of
kernelization and present a polynomial kernel for the problem, for constant α. Our kernel has O(αk 3(α+1) )
vertices and requires new insights into the possible structures induced by those special vertices discussed
above. In particular, we enumerate all maximal degree-two paths in each Gi after deleting a feedback vertex
set in Gi and study how such paths interact with each other. Using marking techniques, we are able to
“unwind” long degree-two paths by making a private copy of each unmarked vertices for each color class.
This unwinding leads to “normal” degree-two paths on which classical reduction rules can be applied and
hence we obtain the desired kernel.
Finally, we consider the dependence between α and both the size of our kernel and the running time
of our algorithm in Section 5. We show that even for α ∈ O(log n), where n is the number of vertices
in the input graph, α-SimFVS becomes W[1]-hard. We show hardness via a new problem of independent
interest which we denote by α-Partitioned Hitting Set. The input to this problem consists of a tuple
(U, F = F1 ∪ . . . ∪ Fα , k), where Fi , 1 ≤ i ≤ α, is a collection of subsets of the finite universe U, k is a positive
integer, and all the sets within a family Fi , 1 ≤ i ≤ α, are pairwise disjoint. The goal is to determine whether
there exists a subset X of U of cardinality at most k such that for every f ∈ F = F1 ∪ . . . ∪ Fα , f ∩ X
is nonempty. We show that O(log |U||F |)-Partitioned Hitting Set is W[1]-hard via a reduction from
Partitioned Subgraph Isomorphism and we show that O(log n)-SimFVS is W[1]-hard via a reduction
from O(log |U||F |)-Partitioned Hitting Set. Along the way, we also show, using a somewhat simpler
reduction from Hitting Set, that O(n)-SimFVS is W[2]-hard.

2

Preliminaries

We start with some basic definitions and introduce terminology from graph theory and algorithms. We also
establish some of the notation that will be used throughout.
Graphs. For a graph G, by V (G) and E(G) we denote its vertex set and edge set, respectively. We only
consider finite graphs possibly having loops and multi-edges. In the following, let G be a graph and let H be
a subgraph of G. By dH (v), we denote the degree of vertex v in H. For any non-empty subset W ⊆ V (G),
the subgraph of G induced by W is denoted by G[W ]; its vertex set is W and its edge set consists of all
those edges of E with both endpoints in W . For W ⊆ V (G), by G \ W we denote the graph obtained by
deleting the vertices in W and all edges which are incident to at least one vertex in W .
A path in a graph is a sequence of distinct vertices v0 , v1 , . . . , vk such that (vi , vi+1 ) is an edge for all
0 ≤ i < k. A cycle in a graph is a sequence of distinct vertices v0 , v1 , . . . , vk such that (vi , v(i+1) mod k ) is an
edge for all 0 ≤ i ≤ k. We note that both a double edge and a loop are cycles. We also use the convention
that a loop at a vertex v contributes 2 to the degree of v.
An edge α-colored graph is a graph G = (V, ∪α
i=1 Ei ). We call Gi the color i (or i-color) graph of G, where
Gi = (V, Ei ). For notational convenience we sometimes denote
Pα an α-colored graph as G = (V, E1 , E2 , ..., Eα ).
For an α-colored graph G, the total degree of a vertex v is i=1 dGi (v). By color i edge (or i-color edge) we
refer to an edge in Ei , for 1 ≤ i ≤ α. A vertex v ∈ V (G) is said to have a color i neighbor if there is an
edge (v, u) in Ei , furthermore u is a color i neighbor of v. We say a path or a cycle in G is monochromatic if
3

all the edges on the path or cycle have the same color. Given a vertex v ∈ V (G), a v-flower of order k is a
set of k cycles in G whose pairwise intersection is exactly {v}. If all cycles in a v-flower are monochromatic
then we have a monochromatic v-flower. An α-colored graph G = (V, E1 , E2 , · · · , Eα ) is an α-forest if each
Gi is a forest, for 1 ≤ i ≤ α. We refer the reader to [9] for details on standard graph theoretic notation and
terminology we use in the paper.
Parameterized Complexity. A parameterized problem Π is a subset of Γ ∗ × N, where Γ is a finite
alphabet. An instance of a parameterized problem is a tuple (x, k), where x is a classical problem instance,
and k is called the parameter. A central notion in parameterized complexity is fixed-parameter tractability
(FPT) which means, for a given instance (x, k), decidability in time f (k) · p(|x|), where f is an arbitrary
function of k and p is a polynomial in the input size.
Kernelization. A kernelization algorithm for a parameterized problem Π ⊆ Γ ∗ × N is an algorithm that,
given (x, k) ∈ Γ ∗ × N, outputs, in time polynomial in |x| + k, a pair (x0 , k 0 ) ∈ Γ ∗ × N such that (a) (x, k) ∈ Π
if and only if (x0 , k 0 ) ∈ Π and (b) |x0 |, k 0 ≤ g(k), where g is some computable function. The output instance
x0 is called the kernel, and the function g is referred to as the size of the kernel. If g(k) = k O(1) (resp.
g(k) = O(k)) then we say that Π admits a polynomial (resp. linear) kernel.

3

FPT algorithm for α-Simultaneous Feedback Vertex Set

We give an algorithm for the α-SimFVS problem using the method of iterative compression [26, 7]. We only
describe the algorithm for the disjoint version of the problem. The existence of an algorithm running in
ck · nO(1) time for the disjoint variant implies that α-SimFVS can be solved in time (1 + c)k · nO(1) [7]. In
the Disjoint α-SimFVS problem, we are given an α-colored graph G = (V ,E1 ,E2 , . . . , Eα ), an integer k,
and an α-simfvs W in G of size k + 1. The objective is to find an α-simfvs X ⊆ V (G) \ W of size at most k,
or correctly conclude the non-existence of such an α-simfvs.
3.1

Algorithm for Disjoint α-SimFVS

Let (G = (V, E1 , E2 , . . . , Eα ), W, k) be an instance of Disjoint α-SimFVS and let F = G \ W . We start
with some simple reduction rules that clean up the graph. Whenever some reduction rule applies, we apply
the lowest-numbered applicable rule.
– Reduction α-SimFVS.R1. Delete isolated vertices as they do not participate in any cycle.
– Reduction α-SimFVS.R2. If there is a vertex v which has only one neighbor u in Gi , for some i ∈
{1, 2, . . . , α}, then delete the edge (v, u) from Ei .
– Reduction α-SimFVS.R3. If there is a vertex v ∈ V (G) with exactly two neighbors u, w (the total
degree of v is 2), delete edges (v, u) and (v, w) from Ei and add an edge (u, w) to Ei , where i is the color
of edges (v, u) and (v, w). Note that after reduction α-SimFVS.R2 has been applied, both edges (v, u)
and (v, w) must be of the same color.
– Reduction α-SimFVS.R4. If for some i, i ∈ {1, 2, . . . , α}, there is an edge of multiplicity larger than
2 in Ei , reduce its multiplicity to 2.
– Reduction α-SimFVS.R5. If there is a vertex v with a self loop, then add v to the solution set X,
delete v (and all edges incident on v) from the graph and decrease k by 1.
The safeness of reduction rule α-SimFVS.R4 follows from the fact that edges of multiplicity greater than
two do not influence the set of feasible solutions. Safeness of reduction rule α-SimFVS.R5 follows from the
fact that any vertex with a loop must be present in every solution set X. Note that all of the above reduction
rules can be applied in polynomial time. Moreover, after exhaustively applying all rules, the resulting graph
G satisfies the following properties:
(P1) G contains no loops,
(P2) Every edge in Gi , for i ∈ {1, 2, . . . , α} is of multiplicity at most two.
(P3) Every vertex in G has either degree zero or degree at least two in each Gi , for i ∈ {1, 2, . . . , α}.
(P4) The total degree of every vertex in G is at least 3.
4

Algorithm 1: Disjoint α-SimFVS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

19
20
21
22
23
24

Input: G = (V, E1 , E2 , . . . , Eα ), W , k, and C = {C1 , . . . , Cα }
Output: YES if G has an α-simfvs S ⊆ V (G) \ W of size at most k, NO otherwise.
Apply α-SimFVS R.1 to α-SimFVS R.5 exhaustively;
if k < 0 or for any i ∈ {1, 2, . . . , α}, |Ci | > k then
return NO
while for some i ∈ {1, 2, . . . , α}, Gi [Fi ∪ Wi ] is not a forest do
find a cordate vertex vc of highest index in some tree of Fi ;
Let uc , wc be the vertices in tree Tvic with a neighbor u, w respectively in Wi ;
Also let P = uc , x1 , . . . , xt , vc and P 0 = vc , y1 , . . . , yt0 , wc be the path in Fi from uc to vc and vc to wc
respectively;
G1 = (G \ {vc }, W, k − 1, C), Add G1 to G;
if V 0 = V (P ) \ {vc } =
6 ∅ then
Ci = Ci ∪ {(uc , x1 , . . . , xt )};
G2 = (G \ V 0 , W, k − 1, C), Add G2 to G;
if V 0 = V (P 0 ) \ {vc } 6= ∅ then
Ci = Ci ∪ {(y1 , . . . , yt0 , wc )};
G3 = (G \ V 0 , W, k − 1, C), Add G3 to G;
if u, w are in
W the same component of Wi then
return G∈G Disjoint α-SimFVS(G)
else
W
return ( G∈G Disjoint α-SimFVS(G)) ∨ Disjoint
α-SimFVS(G \ (V (P ) ∪ V (P 0 )), W ∪ V (P ) ∪ V (P 0 ), k, C)
// Solve the remaining instance using the hitting set problem
For i ∈ {1, 2, . . . , α} let V (Ci ) = ∪C∈Ci V (C), U = ∪i∈{1,2,...,α} V (Ci );
F = ∪i∈{1,2,...,α} Ci ;
Find a hitting set S = Hitting Set(F, U);
if |S| ≤ k then
return YES
return NO

Lemma 1. Reduction rule α-SimFVS.R2 is safe.
Proof. Let G be an α-colored graph and v be a vertex whose only neighbor in Gi is u, for some i ∈
{1, 2, . . . , α}. Consider the α-colored graph G0 with vertex set V (G) and edge sets Ei (G0 ) = Ei (G) \ {(v, u)}
and Ej (G0 ) = Ej (G), for j ∈ {1, 2, . . . , α} \ {i}. We show that G has an α-simfvs of size at most k if and
only if G0 has an α-simfvs of size at most k.
In the forward direction, consider an α-simfvs S in G of size at most k. Since G0j = Gj , S intersects all
the cycles in G0j , j ∈ {1, 2, . . . , α} \ {i}. Note that in Gi , there is no cycle containing the edge (u, v) as v is
a degree-one vertex in Gi . Hence, all the cycles in Gi are also cycles in G0i . S intersects all cycles in Gi and,
in particular, S intersects all cycles in G0i . Therefore, S is an α-simfvs in G0 of size at most k.
For the reverse direction, consider an α-simfvs S in G0 of size at most k. If S is not an α-simfvs of G
then there is a cycle C in some Gt , for t ∈ {1, 2, . . . , α}. Note that C cannot be a cycle in Gj as Gj = G0j , for
j ∈ {1, 2, . . . , α} \ {i}. Therefore C must be a cycle in Gi . The cycle C must contain the edge (v, u), as this
is the only edge in Gi which is not an edge in G0i . But v is a degree-one vertex in Gi , so it cannot be part of
any cycle in Gi , contradicting the existence of cycle C. Thus S is an α-simfvs of G of size at most k.
t
u
Lemma 2. Reduction rule α-SimFVS.R3 is safe.
Proof. Consider an α-colored graph G. Let v be a vertex in V (G) such that v has total degree 2 and let
u, w be the neighbors of v in Gi , where u 6= w and i ∈ {1, 2, . . . , α}. Consider the α-colored graph G0
with vertex set V (G) and edge sets Ei (G0 ) = (Ei (G) \ {(v, u), (v, w)}) ∪ {(u, w)} and Ej (G0 ) = Ej (G), for
5

j ∈ {1, 2, . . . , α} \ {i}. We show that G has an α-simfvs of size at most k if and only if G0 has an α-simfvs of
size at most k.
In the forward direction, let S be an α-simfvs in G of size at most k. Suppose S is not an α-simfvs of G0 .
Then, there is a cycle C in G0t , for some t ∈ {1, 2, . . . , α}. Note that C cannot be a cycle in G0j as G0j = Gj ,
for j ∈ {1, 2, . . . , α} \ {i}. Therefore C must be a cycle in G0i . All the cycles C 0 not containing the edge (u, w)
are also cycles in Gi and therefore S must contain some vertex from C 0 . It follows that C must contain the
edge (u, w). Note that the edges (E(C) \ {(u, w)}) ∪ {(v, u), (w, v)} form a cycle in Gi . Therefore S must
contain a vertex from V (C) ∪ {v}. We consider the following cases:
– Case 1: v ∈
/ S. In this case S must contains a vertex from V (C). Hence, S is an α-simfvs in G0 .
– Case 2: v ∈ S. Let S 0 = (S \ {v}) ∪ {u}. Any cycle C 0 containing v in Gi must contain u and w (since
dGi (v) = 2). But S 0 intersects all such cycles C 0 , as u ∈ S 0 . Therefore S 0 is an α-simfvs of G0 of size at
most k.
In the reverse direction, consider an α-simfvs S of G0 . S intersects all cycles in Gj , since Gj = G0j , for
j ∈ {1, 2, . . . , α} \ {i}. All cycles in Gi not containing v are also cycles in G0i and therefore S intersects all
such cycles. A cycle C in Gi containing v must contain u and w (v is a degree-two vertex in Gi ). Note that
(E(C) \ {(v, u)(v, w)}) ∪ {(u, w)} is a cycle in G0i and S, being an α-simfvs in G0 , must contain a vertex from
V (C) \ {v}. Therefore S ∩ V (C) 6= ∅, so S intersects cycle C in G0i . Hence S an α-simfvs in G0 .
t
u
Algorithm: We give an algorithm for the decision version of the Disjoint α-SimFVS problem, which only
verifies whether a solution exists or not. Such an algorithm can be easily modified to find an actual solution
X. We follow a branching strategy with a nontrivial measure function. Let (G, W, k) be an instance of the
problem, where G is an α-colored graph. If G[W ] is not an α-forest then we can safely return that (G, W, k)
is a no-instance. Hence, we assume that G[W ] is an α-forest in what follows. Whenever any of our reduction
rules α-SimFVS.R1 to α-SimFVS.R5 apply, the algorithm exhaustively does so (in order). If at any point
in our algorithm the parameter k drops below zero, then the resulting instance is again a no-instance.
Recall that initially F is an α-forest, as W is an α-simfvs. We will consider each forest Fi , for i ∈
{1, 2, . . . , α}, separately (where Fi is the color i graph of the α-forest F ). For i ∈ {1, 2, . . . , α}, we let
Wi = (W, Ei (G[W ])) and ηi be the number of components in Wi . Some of the branching rules that we apply
create special vertex-disjoint cycles. We will maintain this set of special cycles in Ci , for each i, and we let
C = {Ci , . . . , Cα }. Initially, Ci = ∅. Each cycle that we add to Ci will be vertex disjoint from previously added
cycles. Hence, if at any point |Ci | > k, for any i, then we can stop exploring the corresponding branch.
Moreover, whenever we “guess” that some vertex v must belong to a solution, we also traverse the family
C and remove any cycles containing v. For the running time analysis of our algorithm we will consider the
following measure:
µ = µ(G, W, k, C) = αk + (

α
X
i=1

α
X
ηi ) − ( |Ci |)
i=1

The input to our algorithm consists of a tuple (G, W, k, C). For clarity, we will denote a reduced input by
(G, W, k, C) (the one where reduction rules do not apply).
We root each tree in Fi at some arbitrary vertex. Assign an index t to each vertex v in the forest Fi ,
which is the distance of v from the root of the tree it belongs to (the root is assigned index zero). A vertex
v in Fi is called cordate if one of the following holds:
– v is a leaf (or degree-zero vertex) in Fi with at least two color i neighbors in Wi .
– The subtree Tvi rooted at v contains two vertices u and w which have at least one color i neighbor in Wi
(v can be equal to u or w).
Lemma 3. For i ∈ {1, 2, . . . , α}, let vc be a cordate vertex of highest index in some tree of the forest Fi
and let Tvc denote the subtree rooted at vc . Furthermore, let uc be one of the vertices in Tvc such that uc has
a neighbor in Wi . Then, in the path P = uc , x1 , . . . , xt , vc (t could be equal to zero) between uc and vc the
vertices x1 , . . . , xt are degree-two vertices in Gi .
6

Proof. Let P = uc , x1 , . . . , xt , vc be the path from vc to uc . In P , if there is a vertex x (other than uc and
vc ) which has an edge of color i to a vertex in Wi , then x is a cordate vertex of higher index, contradicting
the choice of vc . Also, if there is a vertex x in P other than vc and uc of degree at least three in Fi , the
subtree rooted at x has at least two leaves, and all the leaves have a color-i neighbor in Wi . Therefore, x is
a cordate vertex and has a higher index than vc , contradicting the choice of vc . It follows that x1 , . . . , xt (if
they exist) are degree-two vertices in Gi .
t
u
We consider the following cases depending on whether there is a cordate vertex in Fi or not.

X

Wi

w

X

v∈

C ni

/
∈

u

v

Ci

C1

k drops by 1

Gi \ W

vc
x t y1
x1
uc

x1

yt�

xt

uc
|Ci | increases by 1

wc

y1
yt�
wc
|Ci | increases by 1

Fig. 1. Branching in Case 1.a

– Case 1: There is a cordate vertex in Fi . Let vc be a cordate vertex with the highest index in some tree
in Fi and let the two vertices with neighbors in Wi be uc and wc (vc can be equal to uc or wc ). Let
P = uc , x1 , x2 , · · · , xt , vc and P 0 = vc , y1 , y2 , · · · , yt0 , wc be the unique paths in Fi from uc to vc and
from vc to wc , respectively. Let Pv = uc , x1 , · · · , xt , vc , y1 , · · · , yt0 , wc be the unique path in Fi from uc
to wc . Consider the following sub-cases:
Case 1.a: uc and wc have a neighbor in the same component of Wi . In this case one of the vertices from
path Pv must be in the solution (Figure 1). We branch as follows:
• vc belongs to the solution. We delete vc from G and decrease k by 1. In this branch µ decreases
by α. When vc does not belong to the solution, then at least one vertex from uc , x1 , x2 , · · · , xt or
y1 , y2 , · · · , yt0 , wc must be in the solution. But note that these are vertices of degree at most two in
Gi by Lemma 3. So with respect to color i, it does not matter which vertex is chosen in the solution.
The only issue comes from some color j cycle, where j 6= i, in which choosing a particular vertex from
uc , x1 , · · · , xt or y1 , y2 , · · · , yt0 , wc would be more beneficial. We consider the following two cases.
• One of the vertices from uc , x1 , x2 , · · · , xt is in the solution. In this case we add an edge (uc , xt ) (or
(uc , uc ) when uc and vc are adjacent) to Gi and delete the edge (xt , vc ) from Gi . This creates a cycle
C in Gi \ W , which is itself a component in Gi \ W . We remove the edges in C from Gi and add the
cycle C to Ci . We will be handling these sets of cycles independently. In this case |Ci | increases by 1,
so the measure µ decreases by 1.
• One of the vertices from y1 , y2 , · · · , yt , wc is in the solution. In this case we add an edge (y1 , wc ) to
Gi and delete the edge (vc , y1 ) from Gi . This creates a cycle C in Gi \ W as a component. We add
C to Ci and delete edges in C from Gi \ W . In this branch |Ci | increases by 1, so the measure µ
decreases by 1.
The resulting branching vector is (α, 1, 1).
Case 1.b: uc and wc do not have a neighbor in the same component. We branch as follows (Figure 2):
• vc belongs to the solution. We delete vc from G and decrease k by 1. In this branch µ decreases by
α.
7

• One of the vertices from uc , x1 , x2 , · · · , xt is in the solution. In this case we add an edge (uc , xt ) to
Gi and delete the edge (xt , vc ) from Gi . This creates a cycle C in Gi \ W as a component. As in Case
1, we add C to Ci and delete edges in C from Gi \ W . |Ci | increases by 1, so the measure µ decreases
by 1.
• One of the vertices from y1 , y2 , · · · , yt , wc is in the solution. In this case we add an edge (y1 , wc ) to
Gi and delete the edge (vc , y1 ) from Gi . This creates a cycle C in Gi \ W as a component. We add
C to Ci and delete edges in C from Gi \ W . In this branch |Ci | increases by 1, so the measure µ
decreases by 1.
• No vertex from path Pv is in the solution. In this case we add the vertices in Pv to W , the resulting
instance is (G \ Pv , W ∪ Pv , k). The number of components in Wi decreases and we get a drop of 1
in ηi , so µ decreases by 1. Note that if G[W ∪ Pv ] is not acyclic we can safely ignore this branch.
The resulting branching vector is (α, 1, 1, 1).
– Case 2: There is no cordate vertex in Fi . Let F be a family of sets containing a set fC = V (C) for each
α
C ∈ ∪α
i=1 Ci and let U = ∪i=1 (∪C∈Ci V (C)). Note that |F| ≤ αk. We find a subset U ⊆ U (if it exists)
which hits all the sets in F, such that |U | ≤ k.

C1

Ci

Cj

u

C ni

Wi

A vertex from
Pv is in X

X

v∈

/
∈

Gi \ W

vc

No vertex from
Pv is in X

v

X

w

Merge Components
Ci and Cj
ηi drops by 1

k drops by 1

x t y1
x1

yt�

uc

wc

x1

xt

uc
|Ci | increases by 1

y1
yt�
wc
|Ci | increases by 1

Fig. 2. Branching: Case 1.b

Note that in Case 1, if the cordate vertex vc is a leaf, then uc = wc = vc . Therefore, from Case 1.a we
are left with one branching rule. Similarly, we are left with the first and the last branching rules for Case
1.b. If vc is not a leaf but vc is equal to uc or wc , say vc = wc , then for both Case 1.a and Case 1.b we do
not have to consider the third branch. Finally, when none of the reduction or branching rules apply, we solve
the problem by invoking an algorithm for the Hitting Set problem as a subroutine.
Lemma 4. The presented algorithm for Disjoint α-SimFVS is correct.
Proof. Consider an input (G, W, k, C) to the algorithm for Disjoint α-SimFVS, where G is an α-colored
graph, W is an α-simfvs of size k+1, and k is a positive integer and C = {C1 , C2 , . . . , C1 }. Let µ = µ(G, W, k, C)
be the measure as defined earlier. We prove the correctness of the algorithm by induction on the measure µ.
The base case occurs when one of the following holds:
– k < 0,
– for some i ∈ {1, 2, . . . , α}, |Ci | > k, or
– µ ≤ 0.
8

If k < 0, then we can safely conclude that G is a no-instance. If for some i ∈ {1, 2, . . . , α} we have |Ci | > k,
then we need to pick at least one vertex from each of the vertex-disjoint cycles in Ci and there are at least
k + 1 of them.
correctly concludes
Pα Our algorithm
Pα
Pαthat the graph is also a no-instance in such cases. If
µ = αk + ( i=1 ηP
|C
|)
≤
0
then
αk
≤
i) − (
i
i=1
i=1 |Ci |. But for each i ∈ {1, 2, . . . , α}, we have |Ci | ≤ k.
Pα
α
Therefore αk ≤ i=1 |Ci | ≤ αk, i=1 |Ci | = αk, and |Ci | = k, for all i ∈ {1, 2, . . . , α}. This implies that
for each i ∈ {1, 2, . . . , α}, Gi [Fi ∪ Wi ] must be acyclic. Assume otherwise. Then, for some i ∈ {1, 2, . . . , α},
Gi [Fi ∪ Wi ] contains a cycle which is vertex disjoint from the k cycles in Ci . Therefore, at least k + 1 vertices
are needed to intersect these cycles and we again have a no-instance. Recall that when a new vertex v is
added to the solution set we delete all those cycles in ∪α
i=1 Ci which contain v.
We are now left with cycles in ∪α
C
.
Intersecting
a cycle C ∈ ∪α
i
i=1
i=1 Ci is equivalent to hitting the set
V (C). Hence, we construct a family F consisting of a set fC = V (C) for each C ∈ ∪α
i=1 Ci and we let
U = ∪α
(∪
V
(C)).
Note
that
|F|
≤
αk.
If
we
can
find
a
subset
U
⊆
U
which
hits
all
the sets in F,
C∈C
i
i=1
such that |U | ≤ k, then U is the required solution. Otherwise, we have a no-instance. It is known that the
Hitting Set problem parameterized by the size of the family F is fixed-parameter tractable and can be
solved in O? (2|F | ) time [7]. In particular, we can find an optimum hitting set U ⊆ U, hitting all the sets in
F. Therefore, we have a subset of vertices that intersects all the cycles in Ci , for i ∈ {1, 2, . . . , α}.
Putting it all together, at a base case, our algorithm correctly decides whether (G, W, k, C) is a yesinstance or not. For the induction hypothesis, assume that the algorithm correctly decides an instance for
µ ≤ t. Now consider the case µ = t + 1. If some reduction rule applies then we create an equivalent instance
(since all reduction rules are safe). Therefore, either we get an equivalent instance with the same measure
or we get an equivalent instance with µ ≤ t (the case when α-SimFVS.R5 is applied). In the latter case, by
the induction hypothesis, our algorithm correctly decides the instance where µ ≤ t. In the former case, we
apply one of the branching rules. Each branching rule is exhaustive and covers all possible cases. In addition,
the measure decreases at each branch by at least one. Therefore, by the induction hypothesis, the algorithm
correctly decides whether the input is a yes-instance or not.
t
u
Lemma 5. Disjoint α-SimFVS is solvable in time O? (22αk ).
Proof. All of the reduction rules α-SimFVS.R1 to α-SimFVS.R5 can be applied in time polynomial in the
input size. Also, at each branch we spend a polynomial amount of time. For each of the recursive calls at a
branch, the measure µ decreases at least by 1. When µ ≤ 0, then we are able to solve the remaining instance
in time O(2αk ) or correctly conclude that the corresponding branch cannot lead to a solution. At the start
of the algorithm µ ≤ 2αk. Therefore, the height of the search tree is bounded by 2αk. The worst-case
branching vector for the algorithm is (α, 1, 1, 1). The recurrence relation for the worst case branching vector
is: T (µ) ≤ T (µ − α) + 3T (µ − 1) ≤ T (µ − 2) + 3T (µ − 1), since α ≥ 2. The running time corresponding
to the above recurrence relation is 3.3032αk . At each branch we spend a polynomial amount of time but
we might require O(2αk ) time. for solving the base case. Therefore, the running time of the algorithm is
O? (2αk · 3.3032αk ) = O? (22αk ).
t
u
Theorem 1. α-Simultaneous Feedback Vertex Set is solvable in time O? (23αk ).
3.2

Faster algorithm for 2-Simultaneous Feedback Vertex Set

We improve the running time of the FPT algorithm for α-SimFVS when α = 2. Given two sets of disjoint
cycles C1 and C2 and a set V = ∪C∈C1 ∪C2 V (C), we want to find a subset H ⊆ V such that H contains
at least one vertex from V (C), for each C ∈ C1 ∪ C2 . We construct a bipartite graph GM as follows.
We set V (GM ) = {c1x |Cx ∈ C1 } ∪ {c2y |Cy ∈ C2 }. In other words, we create one vertex for each cycle in
C1 ∪ C2 . We add an edge between c1x and c2y if and only if V (Cx ) ∩ V (Cy ) 6= ∅. Note that for i ∈ {1, 2}
and C, C 0 ∈ Ci , V (C) ∩ V (C 0 ) = ∅. In Lemma 6, we show that finding a matching M in GM , such that
|M | + |V (GM ) \ V (M )| ≤ k, corresponds to finding a set H of size at most k, such that H contains at least
one vertex from each cycle C ∈ C1 ∪ C2 .
9

Lemma 6. For i ∈ {1, 2}, let Ci be a set of vertex-disjoint cycles, i.e. for each C, C 0 ∈ Ci , C =
6 C 0 implies
0
V (C) ∩ V (C ) = ∅. Let F = {V (C)|C ∈ C1 ∪ C2 } and U = ∪C∈C1 ∪C2 V (C). There exists a vertex subset
H ⊆ ∪C∈C1 ∪C2 V (C) of size k such that H ∩ V (C) 6= ∅, for each C ∈ C1 ∪ C2 , if and only if GM has a
matching M , such that |M | + |V (GM ) \ V (M )| ≤ k.
Proof. For the forward direction, consider a minimal vertex subset H ⊆ V (C1 ) ∪ V (C2 ) of size at most k
such that for each C ∈ C1 ∪ C2 , H ∩ V (C) 6= ∅. Note that a vertex h ∈ H can be present in at most one
cycle from Ci , for i ∈ {1, 2}, since Ci is a set of vertex-disjoint cycles. Therefore, h can be present in at
most 2 cycles from C1 ∪ C2 . If h is present in 2 cycles, say Cx ∈ C1 and Cy ∈ C2 , then in GM we must
have an edge between c1x and c2y (since h belongs to both Cx and Cy ). We include the edge (c1x , c2y ) in the
matching M . If h belongs to only one cycle, say Czi ∈ C1 ∪ C2 , then we include vertex ciz in a set I. Note
that (V (GM ) \ V (M )) ⊆ I. For each h ∈ H, we either add a matching edge or add a vertex to I. Therefore
|M | + |V (GM ) \ V (M )| ≤ |M | + |I| ≤ k.
In the reverse direction, consider a matching M such that |M | + |V (GM ) \ V (M )| ≤ k. We construct a
set H of size at most k containing a vertex from each cycle in C1 ∪ C2 . For each edge (c1x , c2y ) in the matching,
where Cx ∈ C1 and Cy ∈ C2 , there is a vertex h that belongs to both V (Cx ) and V (Cy ). Include h in H.
For each ciz ∈ V (GM ) \ V (M ), add an arbitrary vertex v ∈ V (Cz ) to H. Note that |H| ≤ k, since for each
matching edge and each unmatched vertex we added one vertex to H. Moreover, for each cycle C ∈ C1 ∪ C2 ,
its corresponding vertex in GM is either part of the matching or is an unmatched vertex; in both cases there
is a vertex in H that belongs to C. Therefore, H is a subset of size at most k which contains at least one
vertex from each cycle in C1 ∪ C2 .
t
u
Note that a matching M in GM minimizing |M | + |V (GM ) \ V (M )| is one of maximum size. Therefore,
at the base case for 2-SimFVS we compute a maximum matching of the corresponding graph GM , which
is a polynomial-time solvable problem, and return an optimal solution for intersecting all cycles in C1 ∪ C2 .
Moreover, if we set µ = 2k +(η1 /α+η2 /α)−(|C1 |+|C2 |), then the worst case branching vector is (2, 1, 1, 1/2).
Corresponding to this worst case branching vector, the running time of the algorithm is O? (81k ).
Theorem 2. 2-Simultaneous Feedback Vertex Set is solvable in time O? (81k ).

4

Polynomial kernel for α-Simultaneous Feedback Vertex Set

In this section we give a kernel with O(αk 3(α+1) ) vertices for α-SimFVS. Let (G, k) be an instance of
α-SimFVS, where G is an α-colored graph and k is a positive integer. We assume that reduction rules αSimFVS.R1 to α-SimFVS.R5 have been exhaustively applied. The kernelization algorithm then proceeds in
two stages. In stage one, we bound the maximum degree of G. In the second stage, we present new reduction
rules to deal with degree-two vertices and conclude a bound on the total number of vertices.
To bound the total degree of each vertex v ∈ V (G), we bound the degree of v in Gi , for i ∈ {1, 2, . . . , α}.
To do so, we need the Expansion Lemma [7] as well as the 2-approximation algorithm for the classical
Feedback Vertex Set problem [1].
A q-star, q ≥ 1, is a graph with q + 1 vertices, one vertex of degree q and all other vertices of degree 1.
Let G be a bipartite graph with vertex bipartition (A, B). A set of edges M ⊆ E(G) is called a q-expansion
of A into B if (i) every vertex of A is incident with exactly q edges of M and (ii) M saturates exactly q|A|
vertices in B.
Lemma 7 (Expansion Lemma [7]). Let q be a positive integer and G be a bipartite graph with vertex
bipartition (A, B) such that |B| ≥ q|A| and there are no isolated vertices in B. Then, there exist nonempty
vertex sets X ⊆ A and Y ⊆ B such that:
– (1) X has a q-expansion into Y and
– (2) no vertex in Y has a neighbour outside X, i.e. N (Y ) ⊆ X.
Furthermore, the sets X and Y can be found in time polynomial in the size of G.
10

4.1

Bounding the degree of vertices in Gi

We now describe the reduction rules that allow us to bound the maximum degree of a vertex v ∈ V (G).
Lemma 8 (Lemma 6.8 [25]). Let G be an undirected multi-graph and x be a vertex of G without a self
loop. Then in polynomial time we can either decide that (G, k) is a no-instance of Feedback Vertex Set
or check whether there is an x-flower of order k + 1, or find a set of vertices Z ⊆ V (G) \ {x} of size at most
3k intersecting every cycle in G, i.e. Z is a feedback vertex set of G.
The next proposition easily follows from Lemma 8.
Proposition 1. Let G be an undirected α-colored multi-graph and x be a vertex without a self loop in
Gi , for i ∈ {1, 2, . . . , α}. Then in polynomial time we can either decide that (G, k) is a no-instance of αSimultaneous Feedback Vertex Set or check whether there is an x-flower of order k + 1 in Gi , or find
a set of vertices Z ⊆ V (G) \ {x} of size at most 3k intersecting every cycle in Gi .
After applying reduction rules α-SimFVS.R1 to α-SimFVS.R5 exhaustively, we know that the degree
of a vertex in each Gi is either 0 or at least 2 and no vertex has a self loop. Now consider a vertex v whose
degree in Gi is more than 3k(k + 4). By Proposition 1, we know that one of three cases must apply:
– (1) (G, k) is a no-instance of α-SimFVS,
– (2) we can find (in polynomial time) a v-flower of order k + 1 in Gi , or
– (3) we can find (in polynomial time) a set Hv ⊆ V (Gi ) of size at most 3k such that v ∈
/ Hv and Gi \ Hv
is a forest.
The following reduction rule allows us to deal with case (2). The safeness of the rule follows from the fact
that if v in not included in the solution then we need to have at least k + 1 vertices in the solution.
Reduction α-SimFVS.R6. For i ∈ {1, 2, . . . , α}, if Gi has a vertex v such that there is a v-flower of
order at least k + 1 in Gi , then include v in the solution X and decrease k by 1. The resulting instance is
(G \ {v}, k − 1).

When in case (3), we bound the degree of v as follows. Consider the graph G0i = Gi \ (Hv ∪ {v} ∪ V0i ),
where V0i is the set of degree 0 vertices in Gi . Let D be the set of components in the graph G0i which have
a vertex adjacent to v . Note that each D ∈ D is a tree and v cannot have two neighbors in D, since Hv is
a feedback vertex set in Gi . We will now argue that each component D ∈ D has a vertex u such that u is
adjacent to a vertex in Hv . Suppose for a contradiction that there is a component D ∈ D such that D has
no vertex which is adjacent to a vertex in Hv . D ∪ {v} is a tree with at least 2 vertices, so D has a vertex
w, such that w is a degree-one vertex in Gi , contradicting the fact that each vertex in Gi is either of degree
zero or of degree at least two.
After exhaustive application of α-SimFVS.R4, every pair of vertices in Gi can have at most two edges
between them. In particular, there can be at most two edges between h ∈ Hv and v. If the degree of v in Gi
is more than 3k(k + 4), then the number of components |D|, in G0i is more than 3k(k + 2), since |Hv | ≤ 3k.
Consider the bipartite graph B, with bipartition (Hv , Q), where Q has a vertex qD corresponding to each
component D ∈ D. We add an edge between h ∈ Hv and qD ∈ Q to E(B) if and only if D has a vertex d
which is adjacent to h in Gi .
Reduction α-SimFVS.R7. Let v be a vertex of degree at least 3k(k + 4) in Gi , for i ∈ {1, 2, . . . , α}, and
let Hv be a feedback vertex set in Gi not containing v and of size at most 3k.
– Let Q0 ⊆ Q and H ⊆ Hv be the sets of vertices obtained after applying Lemma 7 with q = k +2, A = Hv ,
and B = Q, such that H has a (k + 2)-expansion into Q0 in B;
– Delete all the edges (d, v) in Gi , where d ∈ V (D) and qD ∈ Q0 ;
– Add double edges between v and h in Gi , for all h ∈ H (unless such edges already exist).
By Lemma 7 and Proposition 1, α-SimFVS.R7 can be applied in time polynomial in the input size.
11

Lemma 9. Reduction rule α-SimFVS.R7 is safe.
Proof. Let G be an α-colored graph where reductions α-SimFVS.R1 to α-SimFVS.R6 do not apply. Let
v be a vertex of degree more than 3k(k + 4) in Gi , for i ∈ {1, 2, . . . , α}. Let H ⊆ Hv , Q0 ⊆ Q be the sets
defined above and let G0 be the instance obtained after a single application of reduction rule α-SimFVS.R7.
We show that G has an α-simfvs of size at most k if and only if G0 has an α-simfvs of size at most k. We
need the following claim.
Claim. Any k-sized α-simfvs S of G or G0 either contains v or contains all the vertices in H.
Proof. Since there exists a cycle (double edge) between v and every vertex h ∈ H in G0i , it easily follows
that either v or all vertices in H must be in any solution for G0 .
Consider the case of G. We assume v ∈
/ S and there is a vertex h ∈ H such that h ∈
/ S. Note that H
has a (k + 2)-expansion into Q0 in B, therefore h is the center of a (k + 2)-star in B[H ∪ Q0 ]. Let Qh be the
set of neighbors of h in B[H ∪ Q0 ] (|Qh | ≥ k + 2). For each qD , qD0 ∈ Qh , their corresponding components
D, D0 ∈ D form a cycle with v and h. If both h and v are not in S, then we need to pick at least k + 1 vertices
to intersect the cycles formed by D, D0 , h, and v, for each qD , qD0 ∈ Q0 . Therefore, H ⊆ S, as needed.
t
u
In the forward direction, consider an α-simfvs S of size at most k in G. For j ∈ {1, 2, . . . , α}\{i}, G0j = Gj
and therefore S intersects all the cycles in G0j . By the previous claim, we can assume that either v ∈ S or
H ⊆ S. In both cases, S intersects all the new cycles created in G0i by adding double edges between v and
h ∈ H. Moreover, apart from the double edges between v and h ∈ H, all the cycles in G0i are also cycles in
Gi , therefore S intersects all those cycles in G0i . It follows that S is an α-simfvs in G0 .
In the reverse direction, consider an α-simfvs S in G0 of size at most k. Note that for j ∈ {1, 2, . . . , α}\{i},
0
Gj = Gj . Therefore S intersects all the cycles in Gj . By the previous claim, at least one of the following
must hold: (1) v ∈ S or (2) H ⊆ S.
Suppose that (1) v ∈ S. Since G0i \ {v} = Gi \ {v}, S \ {v} intersects all the cycles in G0i \ {v} and Gi \ {v}.
Therefore S intersects all the cycles in Gi and S is an α-simfvs in G. In case (2), i.e. when v 6∈ S but H ⊆ S,
any cycle in G which does not intersect with S is also a cycle in G0 (since such a cycle does not intersect with
H and the only deleted edges from G0 belong to cycles passing through H). In other words, S \ H intersects
all cycles in both G0i \ H and Gi \ H and, consequently, S is an α-simfvs in G.
t
u
After exhaustively applying all reductions α-SimFVS.R1 to α-SimFVS.R7, the degree of a vertex v ∈
V (Gi ) is at most 3k(k + 4) − 1 in Gi , for i ∈ {1, 2, . . . , α}.
4.2

Bounding the number of vertices in G

Having bounded the maximum total degree of a vertex in G, we now focus on bounding the number of vertices
in the entire graph. To do so, we first compute an approximate solution for the α-SimFVS instance using
the polynomial-time 2-approximation algorithm of Bafna et al. [1] for the Feedback Vertex Set problem
in undirected graphs. In particular, we compute a 2-approximate solution Si in Gi , for i ∈ {1, 2, . . . , α}. We
let S = ∪α
i=1 Si . Note that S is an α-simfvs in G and has size at most 2α|SOP T |, where |SOP T | is an optimal
i
i
α-simfvs in G. Let Fi = Gi \ Si . Let T≤1
, T2i , and T≥3
, be the sets of vertices in Fi having degree at most
one in Fi , degree exactly two in Fi , and degree greater than two in Fi , respectively.
i
Later, we shall prove that bounding the maximum degree in G is sufficient for bounding the sizes of T≤1
i
i
and T≤1 , for all i ∈ {1, 2, . . . , α}. We now focus on bounding the size of T2 which, for each i ∈ {1, 2, . . . , α},
corresponds to a set of degree-two paths. In other words, for a fixed i, the graph induced by the vertices
in T2i is a set of vertex-disjoint paths. We say a set of distinct vertices {v1 , . . . , v` } in T2i forms a maximal
degree-two path if (vj , vj+1 ) is an edge, for all 1 ≤ j ≤ `, and all vertices {v1 , . . . , v` } have degree exactly two
in Gi .
We enumerate all the maximal degree-two paths in Gi \ Si , for i ∈ {1, 2, . . . , α}. Let this set of paths
in Gi \ Si be Pi = {P1i , P2i , . . . , Pni i }, where ni is the number of maximal degree-two paths in Gi \ Si . We
12

introduce a special symbol φ and add φ to each set Pi , for i ∈ {1, 2, . . . , α}. The special symbol will be used
later to indicate that no path is chosen from the set Pi .
Let S = P1 × P2 × · · · × Pα be the set of all tuples of maximal degree-two paths of different colors. For τ ∈ S, j ∈ {1, 2, . . . , α}, j(τ ) denotes the element from the set Pj in the tuple τ , i.e. for
τ = (Q1 , φ, . . . , Qj , . . . , Qα ), j(τ ) = Qj (for example 2(τ ) = φ).
For a maximal degree-two path Pji ∈ Pi and τ ∈ S, we define Intercept(Pji , τ ) to be the set of vertices
in path Pji which are present in all the paths in the tuple (of course a φ entry does not contribute to this
set). Formally, Intercept(Pji , τ ) = ∅ if Pji 6∈ τ otherwise Intercept(Pji , τ ) = {v ∈ V (Pji )| for all 1 ≤ t ≤ α, if
t(τ ) 6= φ then v ∈ V (t(τ ))}.
We define the notion of unravelling a path Pji ∈ Pi from all other paths of different colors in τ ∈ S at a
vertex u ∈ Intercept(Pji , τ ) by creating a separate copy of u for each path. Formally, for a path Pji ∈ Pi , τ ∈ S,
and a vertex u ∈Intercept(Pji , τ ), the Unravel (Pji , τ, u) operation does the following. For each t ∈ {1, 2, . . . , α}
let xt and yt be the unique neighbors of u on path t(τ ). Create a vertex ut(τ ) for each path t(τ ), for 1 ≤ t ≤ α,
delete the edges (xt , u) and (u, yt ) from Gt and add the edges (xt , ut(τ ) ) and (ut(τ ) , yt ) in Gt . Figure 3
illustrates the unravel operation for two paths of different colors.

(a)

(b)

Fig. 3. Unravelling two paths with five common vertices (a) to obtain two paths with one common vertex (b).

Reduction α-SimFVS.R8. For a path Pji ∈ Pi , τ ∈ S, if |Intercept(Pji , τ )| > 1, then for a vertex u ∈
Intercept(Pji , τ ), Unravel (Pji , τ, u).
Lemma 10. Reduction rule α-SimFVS.R8 is safe.
Proof. Let G be an α-colored graph and Si be a 2-approximate feedback vertex set in Gi , for i ∈ {1, 2, . . . , α}.
Let Pi be the set of maximal degree-two paths in Gi \ Si and S = P1 × P2 × · · · × Pα . For a path Pji ∈ Pi ,
τ ∈ S, |Intercept(Pji , τ )| > 1, and u ∈ Intercept(Pji , τ ), let G0 be the α-colored graph obtained after applying
Unravel(Pji , τ, u) in G. We show that G has an α-simfvs of size at most k, if and only if G0 has an α-simfvs of
size at most k.
In the forward direction, consider an α-simfvs S in G of size at most k. Let x be a vertex in Intercept(Pji , τ ) \ {u}. We define S 0 = S if u 6∈ S and S 0 = (S \ {u}) ∪ {x} otherwise. A cycle C in the graph G0t
not containing ut(τ ) , where ut(τ ) is the copy of u created for path t(τ ), τ ∈ S, and t ∈ {1, 2, . . . , α}, is also
a cycle in Gt . Therefore S 0 intersects C. Let Pt be the path in Pt containing u, for t ∈ {1, 2, . . . , α}. Note
that in Pi , there is exactly one maximal degree-two path containing u and all the cycles in Gt containing u
13

must contain Pt . All the cycles in G0t containing ut(τ ) must contain x, since ut(τ ) is the private copy of u for
the degree-two path t(τ ) containing x. We consider the following cases depending on whether u belongs to
S or not.
– u ∈ S: A cycle C in G0t , t ∈ {1, 2, . . . , α}, containing ut(τ ) also contains x. Therefore S 0 intersects C.
– u∈
/ S: Corresponding to a cycle C in G0t , t ∈ {1, 2, . . . , α}, containing ut(τ ) , there is a cycle C 0 on vertices
(V (C) ∪ {u}) \ {ut(τ ) } in Gt . But S is an α-simfvs in G and therefore both S and S 0 must contain a
vertex y ∈ V (C 0 ) \ {u}.

In the reverse direction, let S be an α-simfvs in G0 . We define S 0 = S if {ul(τ ) |ul(τ ) ∈ S, 1 ≤ l ≤ α}∩S 6= ∅
and S 0 = (S \ {ul(τ ) |ul(τ ) ∈ S, 1 ≤ l ≤ α}) ∪ {u} otherwise. All the cycles in Gt not containing u are the
cycles in G0t not containing ut(τ ) . Therefore S 0 intersects all those cycles. We consider the following cases
depending on whether there is some t0 ∈ {1, 2, . . . , α} for which ut0 (τ ) belongs to S or not.

– For all t0 ∈ {1, 2, . . . , α}, ut0 (τ ) ∈
/ S. Let C be a cycle in Gt containing u, for t ∈ {1, 2, . . . , α}. Note that
G0t has a cycle C 0 corresponding to C, with V (C 0 ) = (V (C) \ {u}) ∪ {ut(τ ) }. S intersects C 0 , therefore
both S and S 0 have a vertex y ∈ V (C 0 ) \ {ut(τ ) }. Since y ∈ V (C), S 0 intersects the cycle C in Gt .
– For some t0 ∈ {1, 2, . . . , α}, ut0 (τ ) ∈ S. Note that S 0 intersects all the cycles in Gt containing u, for
t ∈ {1, 2, . . . , α}. Moreover, the only purpose of ut0 (τ ) being in S is to intersect a cycle C 0 in G0t containing
ut0 (τ ) . However, the corresponding cycle in Gt can be intersected by a single vertex, namely u. Therefore,
S 0 is an α-simfvs in G.
t
u

This completes the proof.
Theorem 3. α-SimFVS admits a kernel on O(αk 3(α+1) ) vertices.

Proof. Consider an α-colored graph G on which reduction rules α-SimFVS.R1 to α-SimFVS.R8 have been
exhaustively applied. For i ∈ {1, 2, . . . , α}, the degree of a vertex v ∈ Gi is either 0 or at least 2 in Gi . Hence,
in what follows, we do not count the vertices of degree 0 in Gi while counting the vertices in Gi ; since the
total degree of a vertex v ∈ V (G) is at least three, there is some j ∈ {1, 2, . . . , α} such that the degree of
v ∈ V (Gj ) is at least 2.
Let Si be a 2-approximate feedback vertex set in Gi , for i ∈ {1, 2, . . . , α}. Note that S = ∪α
i=1 Si is a
i
i
2α-approximate α-simfvs in G. Let Fi = Gi \ Si . Let T≤1
, T2i , and T≥3
, be the sets of vertices in Fi having
degree at most one in Fi , degree exactly two in Fi , and degree greater than two in Fi , respectively.
The degree of each vertex v ∈ V (Gi ) is bounded by O(k 2 ) in Gi , for i ∈ {1, 2, . . . , α}. In particular, the
i
degree of each s ∈ S is bounded by O(k 2 ) in Gi . Moreover, each vertex v ∈ T≤1
has degree at least 2 in Gi
i
3
and must therefore be adjacent to some vertex in S. It follows that |T≤1 | ∈ O(k ).
In a tree, the number t of vertices of degree at least three is bounded by l − 2, where l is the number of
i
leaves. Hence, |T≥3
| ∈ O(k 3 ). Also, in a tree, the number of maximal degree-two paths is bounded by t + l.
Consequently, the number of degree-two paths in Gi \ Si is in O(k 3 ). Moreover, no two maximal degree-two
paths in a tree intersect.
Note that there are at most O(k 3 ) maximal degree-two paths in Pi , for i ∈ {1, 2, . . . , α}, and therefore
|S| = O(k 3α ). After exhaustive application of α-SimFVS.R8, for each path Pji ∈ Pi , i ∈ {1, 2, . . . , α},
and τ ∈ S, there is at most one vertex in Intercept(Pji , τ ). Also note that after exhaustive application
of reductions α-SimFVS.R1 to α-SimFVS.R7, the total degree of a vertex in G is at least 3. Therefore,
there can be at most O(k 3α ) vertices in a degree-two path Pji ∈ Pi . Furthermore, there are at most O(k 3 )
degree-two maximal paths in Gi , for i ∈ {1, 2, . . . , α}. It follows that |T2i | ∈ O(k 3(α+1) ) and |V (Gi )| ≤
i
i
|T≤1
| + |T2i | + |T≥3
| + |Si | = O(k 3 ) + O(k 3(α+1) ) + O(k 3 ) + 2k ∈ O(k 3(α+1) ). Therefore, the number of vertices
3(α+1)
in G is in O(αk
).
t
u

5

Hardness results

In this section we show that O(log n)-SimFVS, where n is the number of vertices in the input graph, is
W[1]-hard. We give a reduction from a special version of the Hitting Set (HS) problem, which we denote
14

by α-Partitioned Hitting Set (α-PHS). We believe this version of Hitting Set to be of independent
interest with possible applications for showing hardness results of similar flavor. We prove W[1]-hardness
of α-Partitioned Hitting Set by a reduction from a restricted version of the Partitioned Subgraph
Isomorphism (PSI) problem.
Before we delve into the details, we start with a simpler reduction from Hitting Set showing that
O(n)-SimFVS is W[2]-hard. The reduction closely follows that of Lokshtanov [20] for dealing with the
Wheel-Free Deletion problem. Intuitively, starting with an instance (U, F, k) of HS, we first construct
a graph G on 2|U||F | vertices consisting of |F| vertex-disjoint cycles. Then, we use |F| colors to uniquely
map each set to a separate cycle; carefully connecting these cycles together guarantees equivalence of both
instances.
Theorem 4. O(n)-SimFVS parameterized by solution size is W[2]-hard.
Proof. Given an instance (U, F, k) of Hitting Set, we let U = {u1 , . . . , u|U | } and F = {f1 , . . . , f|F | }. We
assume, without loss of generality, that each element in U belongs to at least one set in F. For each fi ∈ F,
1 ≤ i ≤ |F |, we create a vertex-disjoint cycle Ci on 2|U| vertices and assign all its edges color i. We let
V (Ci ) = {ci1 , ci2 , . . . , ci2|U | } and we define β(i, uj ) = ci2j−1 , for 1 ≤ i ≤ |F | and 1 ≤ j ≤ |U |. In other words,
every odd-numbered vertex of Ci is mapped to an element in U. Now for every element uj ∈ U, 1 ≤ j ≤ |U|,
we create a vertex vj , we let γ(uj ) = {ci2j−1 |1 ≤ i ≤ |F | ∧ uj ∈ fi }, and we add an edge (of some special
color, say zero) between vj and every vertex in γ(uj ) (see Figure 4).
v2

v1

c23

c11
c18

c12

c14

c16
c15

c34

c22

c21
c13

c17

c25

c27
c26

c35
c36

c33

c24

c28

v4

v3

c37

c32

c38

c31

Fig. 4. The graph G before contracting all edges colored zero for U
{{u1 , u2 }, {u2 , u3 }, {u2 , u4 }}.

=

{u1 , u2 , u3 , u4 } and F

=

To finalize the reduction, we contract all the edges colored zero to obtain an instance (G, k) of O(n)SimFVS. Note that |V (G)| = |E(G)| = 2|U||F | and the total number of used colors is |F|. Moreover, after
contracting all 0-colored edges, |γ(uj )| = 1 for all uj ∈ U.
Claim. If F admits a hitting set of size at most k then G admits an |F|-simfvs of size at most k.
Proof. Let X = {ui1 , . . . , uik } be such a hitting set. We construct a vertex set Y = {γ(ui1 ), . . ., γ(uik )}. If
Y is not an |F|-simfvs of G then G[V (G) \ Y ] must contain some cycle where all edges are assigned the same
color. By construction, every set in F corresponds to a uniquely colored cycle in G. Hence, the contraction
operations applied to obtain G cannot create new monochromatic cycles, i.e. every cycle in G which does
not correspond to a set from F must include edges of at least two different colors. Therefore, if G[V (G) \ Y ]
contains some monochromatic cycle then X cannot be a hitting set of F.
t
u
Claim. If G admits an |F|-simfvs of size at most k then F admits a hitting set of size at most k.
Proof. Let X = {vi1 , . . . , vik } be such an |F|-simfvs. First, note that if some vertex in X does not correspond
to an element in U, then we can safely replace that vertex with one that does (since any such vertex belongs
to exactly one monochromatic cycle). We construct a set Y = {ui1 , . . . , uik }. If there exists a set fi ∈ F such
15

that Y ∩ fi = ∅ then, by construction, there exists an i-colored cycle Ci in G such that X ∩ V (Ci ) = ∅, a
contradiction.
t
u
Combining the previous two claims with the fact that our reduction runs in time polynomial in |U|, |F|,
and k, completes the proof of the lemma.
t
u
Notice that if we assume that |U| and |F| are linearly dependent, then Theorem 4 in fact shows that
√
O( n)-SimFVS is W[2]-hard. However, The proof of Theorem 4 crucially relies on the fact that each cycle is “uniquely identified” by a separate color. In order to get around this limitation and prove W[1]hardness of O(log n)-SimFVS we need, in some sense, to group separate sets of a Hitting Set instance into
O(log(|U||F |)) families such that sets inside each family are pairwise disjoint. By doing so, we can modify
the proof of Theorem 4 √
to identify all sets inside a family using the same color, for a total of O(log n) colors
(instead of O(n) or O( n)). We achieve exactly this in what follows. We refer the reader to the work of
Impagliazzo et al. [14, 15] for details on the Exponential Time Hypothesis (ETH).
α-Partitioned Hitting Set
Parameter: k
Input: A tuple (U, F = F1 ∪ . . . ∪ Fα , k), where Fi , 1 ≤ i ≤ α, is a collection of subsets of the finite
universe U and k is a positive integer. Moreover, all the sets within a family Fi , 1 ≤ i ≤ α, are pairwise
disjoint.
Question: Is there a subset X of U of cardinality at most k such that for every f ∈ F = F1 ∪ . . . ∪ Fα ,
f ∩ X is nonempty?
Partitioned Subgraph Isomorphism
Parameter: k = |E(G)|
Input: A graph H, a graph G with V (G) = {g1 , . . . , g` }, and a coloring function col : V (H) → [`].
Question: Is there an injection inj : V (G) → V (H) such that for every i ∈ [`], col(inj(gi )) = i and
for every (gi , gj ) ∈ E(G), (inj(gi ), inj(gj )) ∈ E(H)?
Theorem 5 ([13, 23]). Partitioned Subgraph Isomorphism parameterized by |E(G)| is W[1]-hard,
even when the maximum degree of the smaller graph G is three. Moreover, the problem cannot be solved in
k
time f (k)no( log k ) , where f is an arbitrary function, n = |V (H)|, and k = |E(G)|, unless ETH fails.
We make a few simplifying assumptions: For an instance of Partitioned Subgraph Isomorphism, we
let Hi denote the subgraph of H induced on vertices colored i. We assume that |Hi | = 2t , for 1 ≤ i ≤ `
and t some positive integer; adding isolated vertices to each set is enough to guarantee this size constraint.
Moreover, we assume G is connected and whenever there is no edge (gi , gj ) ∈ E(G), then there are no edges
between V (Hi ) and V (Hj ) in H (see Figure 5 for an example of an instance). Since the PSI problem asks
for a “colorful” subgraph of H isomorphic to G such that one vertex from Hi is mapped to the vertex gi ,
1 ≤ i ≤ `, it is also safe to assume that Hi , 1 ≤ i ≤ `, is edgeless.
Theorem 6. O(log(|U||F |))-Partitioned Hitting Set parameterized by solution size is W[1]-hard. Morek
over, the problem cannot be solved in time f (k)no( log k ) , where f is an arbitrary function, n = |U|, and k is
the required solution size, unless ETH fails.
Proof. Given an instance (H, G, col, ` = |V (G)|, k = |E(G)|) of PSI, where G has maximum degree three, we
reduce it into an instance (U, F = F1 ∪ . . . ∪ Fα , k 0 = k + `) of α-PHS, where α = 16 log 2t + 1 = 16t + 1, Fi ,
1 ≤ i ≤ α, is a collection of subsets of the finite universe U, and all the sets within a family Fi are pairwise
disjoint.
We start by constructing the universe U. For each vertex hij ∈ V (Hi ), 1 ≤ i ≤ ` and 0 ≤ j ≤ 2t − 1,
we create an element vji . For each edge (hij11 , hij22 ) ∈ E(H), we create an element eij11,i,j22 where j1 is the index
of the vertex in Hi1 , j2 is the index of the vertex in Hi2 , 1 ≤ i1 , i2 ≤ `, and 0 ≤ j1 , j2 ≤ 2t − 1. Note that
|U| = |V (H)| + |E(H)| = `2t + |E(H)| < 4t 2`2 .
16

G

H2

H1

1

2

3

4
H3

H4

Fig. 5. An instance of the PSI problem.

We now create “selector gadgets” between elements corresponding to vertices and elements corresponding
to edges. For every ordered pair (x, y), 1 ≤ x, y ≤ `, such that there exists an edge between Hx and Hy in
H (or equivalently there exists an edge (gx , gy ) in G), we create 2t sets. We denote half of those sets by
Ux,y,p and the order half by Dx,y,p , where 1 ≤ p ≤ t. Let Ux denote the set of all elements corresponding
to vertices in Hx and let Ux,y (x and y unordered in Ux,y ) denote the set of all elements corresponding to
edges between vertices in Hx and vertices Hy . We let bit(i)[p], 0 ≤ i ≤ 2t − 1 and 1 ≤ p ≤ t, be the pth bit
in the bit representation of i (where position p = 1 holds the most significant bit). For each vix ∈ Ux and
for all p from 1 to t, if bit(i)[p] = 0 we add vix to set Dx,y,p and we add vix to set Ux,y,p otherwise. For each
x,y
x,y
ex,y
i,j ∈ Ux,y and for all p from 1 to t, if bit(i)[p] = 0 we add ei,j to set Ux,y,p and we add ei,j to set Dx,y,p
x,y
x
otherwise. Recall that for ei,j , i corresponds to the index of element vi ∈ Ux .

U

v21 v31

v11 v31

1,2
e1,2
0,0 e1,1

e1,2
0,0

D

v01 v11

U1

v01 v11 v21

v31

v01 v21

D

e1,2
1,1

1,2
U1,2 e1,2
0,0 e1,1

v02 v12

U

1,2 1,2
D e0,0 e1,1
v22 v32

U2

U

1,3
e1,3
0,0 e1,1

U1,3

v02 e1,2
1,1
v22

U

2
e1,2
0,0 v1

D

v32

v02 v12 v22 v32

v03 v13

v23 v33 U3

3,4
e3,4
0,0 e1,1 U3,4

2,4
U2,4 e2,4
0,0 e1,1

v04 v14 v24 v34

U4

Fig. 6. Parts of the reduction for the PSI instance from Figure 5. Rectangles represents subsets of the universe and
circles represent sets in the family.

17

Finally, for each x, 1 ≤ x ≤ `, we add a set Qx = Ux , and for each (unordered) pair x,y such that
(gx , gy ) ∈ E(G) we add a set Qx,y = Ux,y . Put differently, a set Qx contains all elements corresponding to
vertices in Hx and a set Qx,y contains all elements corresponding to edges between Hx and Hy . The role
of these ` + k sets is simply to force a solution to pick at least one element from every Ux and one element
from every Uy,z , 1 ≤ x, y, z ≤ `. Note that we have a total of 4t|E(G)| + |E(G)| + ` < 4t`2 + `2 + ` sets and
therefore 16t + 1 ∈ O(log(|U||F |)). We set k 0 = |V (G)| + |E(G)| = ` + k. This completes the construction.
An example of the construction for the instance given in Figure 5 is provided in Figure 6.
Claim. In the resulting instance (U, F = F1 ∪ . . . ∪ Fα , k 0 = k + `), α = 16 log 2t + 1 = 16t + 1.
Proof. First, we note that all sets Qx and Qy,z , 1 ≤ x, y, z ≤ `, are pairwise disjoint. Hence, we can group
all these sets into a single partition. We now prove that 16t is enough to partition the remaining sets.
Since G has maximum degree three, we know by Vizing’s theorem [28] that G admits a proper 4-edgecoloring, i.e. no two edges incident on the same vertex receive the same color. Let us fix such a 4-edge-coloring
and denote it by β : E(G) → {1, 2, 3, 4}. Recall that for every ordered pair (x, y), 1 ≤ x, y ≤ `, we define
two groups of sets Ux,y,p and Dx,y,p , 1 ≤ p ≤ t. Given any set Xx,y,p , X ∈ {U, D}, we define the partition
to which Xx,y,p belongs as part(X, x, y, p) = (β(gx , gy ), p, {U, D}, {x < y, x > y}). In other words, we have
a total of 16t partitions depending on the color of the edge (gx , gy ) in G, the position p, whether X = U or
X = D, and whether x < y or x > y (recall that we assume x 6= y).
Since β is a proper 4-coloring of the edges of G, we know that if two sets belong to the same partition they
must be of the form Xx1 ,y1 ,p and Xx2 ,y2 ,p , where X ∈ {U, D}, x1 6= x2 , y1 6= y2 , β(gx1 , gy1 ) = β(gx2 , gy2 ),
x1 < y1 (x1 > y1 ), and x2 < y2 (x2 > y2 ). It follows from our construction that Xx1 ,y1 ,p ∩ Xx2 ,y2 ,p = ∅;
Xx1 ,y2 ,p only contains elements from Ux1 ∪ Ux1 ,y1 , Xx2 ,y2 ,p only contains elements from Ux2 ∪ Ux2 ,y2 , and
(Ux1 ∪ Ux1 ,y1 ) ∩ (Ux2 ∪ Ux2 ,y2 ) is empty.
t
u
Claim. The resulting instance (U, F = F1 ∪ . . . ∪ Fα , k 0 = k + `) admits no hitting set of size k 0 − 1.
Proof. If there exists a hitting set S of size k 0 − 1, then either (1) there exists Ux , 1 ≤ x ≤ `, such that
S ∩ Ux = ∅ or (2) there exists Uy,z , 1 ≤ y, z ≤ `, such that S ∩ Uy,z = ∅. In case (1), we are left with a set
Qx which is not hit by S. Similarly, for case (2), there exists a set Qy,z which is not hit by S. In both cases
we get a contradiction as we assumed S to be a hitting set, as needed.
t
u
Claim. Any hitting set of size k 0 of the resulting instance (U, F = F1 ∪ . . . ∪ Fα , k 0 = k + `) must pick
exactly one element from each set Ux , 1 ≤ x ≤ `, and exactly one element from each set Uy,z , 1 ≤ y, z ≤ `.
Moreover, for every ordered pair (x, y), 1 ≤ x, y ≤ `, a hitting set of size k 0 must pick vix ∈ Ux and ex,y
i,j ∈ Ux,y ,
y
t
x
x
0 ≤ i, j ≤ 2 − 1. In other words, the vertex hi ∈ V (H) is incident to the edge (hi , hj ) ∈ E(H).
Proof. The first part of the claim follows from the previous claim combined with the fact that k 0 = k + `. For
the second part, assume that there exists a hitting set S of size k 0 such that for some ordered pair, (x, y),
S includes vix1 ∈ Ux and ex,y
i2 ,j ∈ Ux,y , where i1 6= i2 . Since i1 6= i2 , then bit(i1 )[p] 6= bit(i2 )[p] for at least one
position p. For that position, we know that vix1 and ex,y
i2 ,j must both belong to only one of Ux,y,p or Dx,y,p .
Hence, either Ux,y,p or Dx,y,p is not hit by vix1 and ex,y
t
u
i2 ,j when i1 6= i2 .
Claim. If (H, G, col, ` = |V (G)|, k = |E(G)|), where G has maximum degree three, is a yes-instance of PSI
then (U, F = F1 ∪ . . . ∪ Fα , k 0 = k + `) is a yes-instance of α-PHS.
Proof. Let S, a subgraph of H, denote the solution graph and let V (S) = {h1i1 , . . . , h`i` }. We claim that
S 0 = {vi11 , . . . , vi`` } ∪ {ex,y
j1 ,j2 |(gx , gy ) ∈ E(G) ∧ j1 , j2 ∈ {i1 , . . . , i` }} is a hitting set of F. That is, the hitting
set picks ` elements corresponding to the ` vertices in S (or G) and k elements corresponding to the k edges
in G.
Clearly, all sets Qx and Qy,z , 1 ≤ x, y, z ≤ `, are hit since we pick one element from each. We now show
that all sets Ux,y,p and Dx,y,p , 1 ≤ x, y ≤ ` and 1 ≤ p ≤ t, are also hit. Assume, without loss of generality,
that for fixed x, y, and p, some set Ux,y,p is not hit. Let vix1 ∈ Ux be the element we picked from Ux and let
ex,y
i2 ,j be the element we picked from Ux,y . If Ux,y,p is not hit, it must be the case that i1 6= i2 which, by the
previous claim, is not possible.
t
u
18

Claim. If (U, F = F1 ∪. . .∪Fα , k 0 = k+`) is a yes-instance of α-PHS then (H, G, col, ` = |V (G)|, k = |E(G)|)
is a yes-instance of PSI.
Proof. Let S = {vi11 , . . . , vi`` } ∪ {ex,y
j1 ,j2 |(gx , gy ) ∈ E(G) ∧ j1 , j2 ∈ {i1 , . . . , i` }} be a hitting set of F. Note
that we can safely assume that the hitting set picks such elements since it has to hit all sets Qx and Qy,z ,
1 ≤ x, y, z ≤ `. We claim that the subgraph S 0 of H with vertex set V (S 0 ) = {h1i1 , . . . , h`i` } is a solution to
the PSI instance.
By construction, there is an injection inj : V (G) → V (S 0 ) such that for every i ∈ [`], col(inj(gi )) = i. In
fact, S 0 contains exactly one vertex for each color i ∈ [`]. Assume that there exists an edge (gi , gj ) ∈ E(G)
such that (inj(gi ), inj(gj )) 6∈ E(S 0 ). This implies that there exists two vertices hxi , hyj ∈ V (S 0 ) such that
(hxi , hyj ) 6∈ E(S 0 ). But we know that there exists at least one edge, say (hxi0 , hyj0 ), between vertices in Hx and
vertices in Hy (from our assumptions). Since i0 6= i, j 0 6= j, vix , vjy ∈ S, and ex,y
i,j 6∈ S, it follows that S cannot
be a hitting set of F as at least one set in Ux,y,p ∪ Dx,y,p and one set in Uy,x,p ∪ Dy,x,p is not hit by S, a
contradiction.
t
u
t
u

This completes the proof of the theorem.

We are now ready to state the main result of this section. The proof of Theorem 7 follows the same steps
as the proof of Theorem 4 with one exception, i.e we reduce from O(log(|U||F |))-Partitioned Hitting
Set and use O(log(|U||F |)) colors instead of |F|.
Theorem 7. O(log n)-SimFVS parameterized by solution size is W[1]-hard.
Proof. Given an instance (U, F = F1 ∪ . . . ∪ Fα , k) of α-PHS, we let U = {u1 , . . . , u|U | } and Fi =
i
{f1i , . . . , f|F
}, 1 ≤ i ≤ α. We assume, without loss of generality, that each element in U belongs to at
i|
least one set in F.
For each fji ∈ Fi , 1 ≤ i ≤ α and 1 ≤ j ≤ |Fi |, we create a vertex-disjoint cycle Cji on 2|U| vertices and
i,j
i,j
assign all its edges color i. We let V (Cji ) = {ci,j
1 , . . . , c2|U | } and we define β(i, j, up ) = c2p−1 , 1 ≤ i ≤ α,
i
1 ≤ j ≤ |Fi |, and 1 ≤ p ≤ |U |. In other words, every odd-numbered vertex of Cj is mapped to an element
in U. Now for every element up ∈ U, 1 ≤ p ≤ |U |, we create a vertex vp , we let γ(up ) = {ci,j
2p−1 |1 ≤ i ≤
α ∧ 1 ≤ j ≤ |Fi | ∧ up ∈ fji }, and we add an edge (of some special color, say 0) between vp and every
vertex in γ(up ). To finalize the reduction, we contract all the edges colored 0 to obtain an instance (G, k) of
O(log n)-SimFVS. Note that |V (G)| = |E(G)| = 2|U||F | and the total number of used colors is α. Moreover,
after contracting all special edges, |γ(up )| = 1 for all up ∈ U.
Claim. If F admits a hitting set of size at most k then G admits an α-simfvs of size at most k.
Proof. Let X = {up1 , . . . , upk } be such a hitting set. We construct a vertex set Y = {γ(up1 ), . . ., γ(upk )}. If
Y is not an α-simfvs of G then G[V (G) \ Y ] must contain some monochromatic cycle. By construction, only
sets from the same family Fi , 1 ≤ i ≤ α, correspond to cycles assigned the same color in G. But since we
started with an instance of α-PHS, no two such sets intersect. Hence, the contraction operations applied to
obtain G cannot create new monochromatic cycles. Therefore, if G[V (G) \ Y ] contains some monochromatic
cycle then X cannot be a hitting set of F.
t
u
Claim. If G admits an α-simfvs of size at most k then F admits a hitting set of size at most k.
Proof. Let X = {vp1 , . . . , vpk } be such an α-simfvs. First, note that if some vertex in X does not correspond
to an element in U, then we can safely replace that vertex with one that does (since any such vertex belongs
to exactly one monochromatic cycle). We construct a set Y = {up1 , . . . , upk }. If there exists a set fji ∈ Fi
such that Y ∩ fji = ∅ then, by construction, there exists an i-colored cycle Ci in G such that X ∩ V (Ci ) = ∅,
a contradiction.
t
u
Combining the previous two claims with the fact that our reduction runs in time polynomial in |U|, |F|,
and k, completes the proof of the theorem.
t
u
19

6

Conclusion

We have showed that α-SimFVS parameterized by solution size k is fixed-parameter tractable and can be
solved by an algorithm running in O? (23αk ) time, for any constant α. For the special case of α = 2, we
gave a faster O? (81k ) time algorithm which follows from the observation that the base case of the general
algorithm can be solved in polynomial time when α = 2. Moreover, for constant α, we presented a kernel for
the problem with O(αk 3(α+1) ) vertices.
It is interesting to note that our algorithm implies that α-SimFVS can be solved in (2O(α) )k nO(1) time.
However, we have also seen that α-SimFVS becomes W[1]-hard when α ∈ O(log n). This implies that (under
plausible complexity assumptions) an algorithm running in (2o(α) )k nO(1) time cannot exist. In other words,
the running time cannot be subexponential in either k or α.
As mentioned by Cai and Ye [3], we believe that studying generalizations of other classical problems
to edge-colored graphs is well motivated and might lead to interesting new insights about combinatorial
and structural properties of such problems. Some of the potential candidates are Vertex Planarization,
Odd Cycle Transversal, Interval Vertex Deletion, Chordal Vertex Deletion, Planar FDeletion, and, more generally, α-Simultaneous F-Deletion.

References
1. V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem.
SIAM J. Discret. Math., 12(3):289–297, Sept. 1999.
2. J. Bang-Jensen and G. Gutin. Alternating cycles and paths in edge-coloured multigraphs: A surve. Discrete
Mathematics, 165–166:39–60, 1997. Graphs and Combinatorics.
3. L. Cai and J. Ye. Dual connectedness of edge-bicolored graphs and beyond. In Mathematical Foundations of
Computer Science 2014, volume 8635 of Lecture Notes in Computer Science, pages 141–152. Springer Berlin
Heidelberg, 2014.
4. Y. Cao and D. Marx. Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms, 11(3):21:1–21:35,
Jan. 2015.
5. J. Chen, F. V. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved algorithms for feedback vertex set problems.
Journal of Computer and System Sciences, 74(7):1188 – 1198, 2008.
6. J. Chen, I. A. Kanj, and G. Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736–
3756, Sept. 2010.
7. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.
Parameterized Algorithms. Springer, 2015.
8. M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. v. Rooij, and J. O. Wojtaszczyk. Solving connectivity
problems parameterized by treewidth in single exponential time. In Proceedings of the 2011 IEEE 52Nd Annual
Symposium on Foundations of Computer Science, FOCS ’11, pages 150–159, Washington, DC, USA, 2011. IEEE
Computer Society.
9. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
10. R. G. Downey and M. R. Fellows. Parameterized complexity. Springer-Verlag, 1997.
11. F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-Deletion: Approximation, kernelization and
optimal FPT algorithms. In FOCS, pages 470–479. IEEE Computer Society, 2012.
12. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.
H. Freeman & Co., New York, NY, USA, 1979.
13. M. Grohe and D. Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series
B, 99(1):218 – 228, 2009.
14. R. Impagliazzo and R. Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367
– 375, 2001.
15. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of
Computer and System Sciences, 63(4):512 – 530, 2001.
16. M. Kano and X. Li. Monochromatic and heterochromatic subgraphs in edge-colored graphs - a survey. Graphs
and Combinatorics, 24(4):237–263, 2008.
17. E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau, and S. Sikdar. Linear kernels and singleexponential algorithms via protrusion decompositions. In Automata, Languages, and Programming, volume 7965
of Lecture Notes in Computer Science, pages 613–624. Springer Berlin Heidelberg, 2013.

20

18. T. Kociumaka and M. Pilipczuk. Faster deterministic feedback vertex set. Information Processing Letters,
114(10):556 – 560, 2014.
19. S. Kratsch and M. Wahlstrom. Representative sets and irrelevant vertices: New tools for kernelization. 2013
IEEE 54th Annual Symposium on Foundations of Computer Science, 0:450–459, 2012.
20. D. Lokshtanov. Wheel-free deletion is W[2]-Hard. In M. Grohe and R. Niedermeier, editors, Parameterized
and Exact Computation, volume 5018 of Lecture Notes in Computer Science, pages 141–147. Springer Berlin
Heidelberg, 2008.
21. D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. Faster parameterized
algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1–15:31, Oct. 2014.
22. D. Marx. Chordal deletion is fixed-parameter tractable. In F. Fomin, editor, Graph-Theoretic Concepts in
Computer Science, volume 4271 of Lecture Notes in Computer Science, pages 37–48. Springer Berlin Heidelberg,
2006.
23. D. Marx. Can you beat treewidth? In Proceedings of the 48th Annual IEEE Symposium on Foundations of
Computer Science, FOCS ’07, pages 169–179, Washington, DC, USA, 2007. IEEE Computer Society.
24. D. Marx and I. Schlotter. Obtaining a planar graph by vertex deletion. In Graph-Theoretic Concepts in Computer
Science, volume 4769 of Lecture Notes in Computer Science, pages 292–303. Springer Berlin Heidelberg, 2007.
25. P. Misra, V. Raman, M. Ramanujan, and S. Saurabh. Parameterized algorithms for even cycle transversal. In
M. Golumbic, M. Stern, A. Levy, and G. Morgenstern, editors, Graph-Theoretic Concepts in Computer Science,
volume 7551 of Lecture Notes in Computer Science, pages 172–183. Springer Berlin Heidelberg, 2012.
26. B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Operations Research Letters, 32(4):299 – 301,
2004.
27. S. Thomassé. A 4k2 kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1–32:8, Apr. 2010.
28. V. G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz No., 3:25–30, 1964.
29. M. Xiao and H. Nagamochi. An improved exact algorithm for undirected feedback vertex set. In P. Widmayer,
Y. Xu, and B. Zhu, editors, Combinatorial Optimization and Applications, volume 8287 of Lecture Notes in
Computer Science, pages 153–164. Springer International Publishing, 2013.

21

