A Note on Finding Dual Feedback Vertex Set

arXiv:1510.00773v1 [cs.DS] 3 Oct 2015

Junjie Ye
Department of Computer Science and Engineering, The Chinese University of Hong
Kong, Shatin, Hong Kong SAR, China
jjye@cse.cuhk.edu.hk

Abstract. For an edge-bicolored graph G where each edge is colored
either red or blue, a vertex set S is a dual feedback vertex set if S hits
all blue cycles and red cycles of G. In this paper, we show that a dual
feedback vertex set of size at most k can be found in time O∗ (ck1 ) and all
minimal dual feedback vertex set of size at most k can be enumerated in
2
time O∗ (c2k +k ) by compact representations for constants c1 and c2 .
Keywords: edge-bicolored graph, dual feedback vertex set, parameterized complexity.

1

Introduction

Given an undirected graph G, the Feedback Vertex Set problem (FVS) asks
if there is a vertex set of size at most k that hits all cycles of G. FVS is one
of the most fundamental graph problems whose NP-completeness is proved by
Karp [15]. FVS has been extensively studied under the framework of parameterized complexity [12]. Since Downey and Fellows [11], and Bodlaender [3] gave
the first FPT algorithms of FVS, there is a long race for the fastest FPT algorithm [12,18,14,19,13,10,7,6,16]. Besides the classical feedback vertex set problem, many interesting generalizations of FVS have been studied. For example,
Subset Feedback Vertex Set, which requires to hit all cycles going through
some specified vertices, is shown to be FPT [21,17]. Group Feedback Vertex
Set, a more generalized problem, is studied and proved to be FPT by Cygan et
al. [9], where each edge is labeled with some group element, and it requires to
hit all cycles that evaluate to a non-null element.
In this paper, we focus on edge-bicolored graphs that are simple undirected
graphs with each edge colored either blue or red, and consider the parameterized
complexity of the following generalization of FVS:
Dual Feedback Vertex Set (DFVS):
Input: Edge-bicolored graph G, parameter k.
Question: Find a vertex set S of size at most k that hits all blue and
red cycles.
Recently, Cai and Ye [5] have systematically considered such kind of vertex deletion problems on edge-bicolored graphs, i.e., problems of deleting vertices on an edge-bicolored graph to make the blue and red graphs satisfy some

2

properties respectively. They give a complete characterization of the Induced
(Πb , Πr )-Subgraphs problems for hereditary properties Πb and Πr , which finds,
on an edge-bicolored graph, an induced subgraph of k vertices whose blue and
red graphs satisfy the properties Πb and Πr respectively. Their results include
the W[1]-hardness of the parametric dual of DFVS, i.e., Induced (Πb , Πr )Subgraphs for Πb = Πr being acyclic.
In this paper, we give an FPT algorithm for DFVS, and show that all minimal
solutions of size at most k can be enumerated in FPT time by compact representations. In connection with these results, we generalize the FPT algorithm of
DFVS to show that, given an edge-colored graph G with h colors, it takes time
O∗ (chk log k ) 1 to find a vertex set of size at most k that hits all monochromatic
cycles of G.
For a graph G, V (G) and E(G) denote its vertex set and edge set respectively,
and n and m, respectively, are numbers of vertices and edges of G. For a subset
V ′ ⊆ V (G), NG (V ′ ) denotes the neighbors of V ′ in V (G) − V ′ and G[V ′ ] the
subgraph of G induced by V ′ .
For an edge-bicolored graph G = (V, Eb ∪Er ), Gb = (V, Eb ) and Gr = (V, Er ),
respectively, denote the blue graph and red graph of G. For a vertex v ∈ V , db (v)
and dr (v) denote the degree of v in Gb and Gr respectively. We use d(v) = (d1 , d2 )
to denote the degree of v in G, where d1 = db (v) and d2 = dr (v). A subset
V ′ ⊆ V (G) is a dual feedback vertex set of G if both Gb − V ′ and Gr − V ′ are
acyclic.
An instance (I, k) of a parameterized problem Π consists of two parts: an
input I and a parameter k. We say that a parameterized problem Π is fixed
parameter tractable (FPT) if there is an algorithm solving every instance (I, k)
in time f (k)|I|O(1) for some computable function f .
In the rest of the paper, we present FPT algorithms for DFVS in Section
2, and show how to enumerate minimal solutions of DFVS in Section 3. We
conclude with discussions in Section 4.

2

Dual Feedback Vertex Set

In this section, we show that DFVS can be solved in time O∗ (ck ) following
the result of Guo et al.’s [13] which enumerates all minimal feedback vertex
sets in FPT time by compact representations. A compact representation C is a
collection of pairwise disjoint vertex sets. A vertex set S that contains exactly one
element of every set of a compact representation C is a minimal dual feedback
set of size at most k, and we say that S is represented by C.
Theorem 1. DFVS can be solved in time O∗ (ck ) for a constant c.
Proof. We first enumerate all compact representations of minimal feedback vertex set of size at most k for both Gb and Gr in time O∗ (ck1 ) for a constant c1 by
Guo et al.’s algorithm [13]. Since a minimal dual feedback vertex set is always
1

The O∗ -notation suppresses factors polynomial in the input size.

3

a union of a minimal feedback vertex set of Gb and a minimal feedback vertex
set of Gb , a minimal solution of DFVS is a minimal vertex set that covers every
vertex set in Cb ∪ Cr for two compact representations Cb of Gb and Cr of Gr .
Given two compact representations Cb and Cr of Gb and Gr respectively, we
show that a minimum vertex set S that intersects every vertex set in Cb ∪ Cr
can be found in polynomial time.
To this end, we build an auxiliary graph H as following:
• For a vertex set Si ∈ Cb ∪ Cr , create a vertex si .
• If a vertex v is in both Si ∈ Cb and Sj ∈ Cr , add an edge ev = si sj .
• If there are t parallel edges between a pair of vertices, select one edge to
represent the t edges and delete other t − 1 edges.
Note that each edge represents the intersection of two sets, thus if there are t
parallel edges we can arbitrary delete t − 1 edges. Since Cb , also Cr , contains at
most k vertex disjoint sets, H has at most 2k vertices and k 2 edges. For each
isolated vertex si of H, we arbitrary put a vertex v ∈ Si into S. Then we find
a minimum edge set F that covers all non-isolated vertices, which can be done
in time O(k 3 ) following the Theorem 3.7 in Cai’s paper [4]. For an edge ev ∈ F ,
put the vertex v into S. Then S is a minimum vertex set that covers all sets of
Cb ∪ Cr .
As there are ck1 ways to select a compact representation Cb , also Cr , the
∗ k
running time for this algorithm is O∗ (c2k
1 ) = O (c ) for a constant c.
One crucial step of the above algorithm is to find a minimal set that covers
two compact representations. We observe that the analogous step can be done
in FPT time for Multi-Feedback Vertex Set (MFVS) which is the problem
of finding a vertex set of size at most k that hits all monochromatic cycles on
an edge-colored graph. Based on the observation, we can establish the fixed
parameter tractability of MFVS.
Theorem 2. MFVS can be solved in time O∗ (chk log k ) where h is the number
of colors of the input edge-colored graph.
Proof. Let G be an edge-colored graph with h colors, and G1 , . . . , Gh be the
monochromatic subgraphs of G. We first obtain compact representations of minimal feedback vertex set of size at most k for Gi by the algorithm of Guo et
al.’s [13], which takes time O∗ (hck1 ) for a constant c1 .
Let Ci be a compact representation of Gi . Since a minimal solution of MultiFeedback Vertex Set is always a union of minimal feedback sets of Gi , a
vertex set of size at most k that intersects all sets of Ci for 1 ≤ i ≤ h will be a
solution. To find such a vertex set, we build an auxiliary graph H as following:
• For each vertex set Si ∈ C1 ∪ · · · ∪ Ch , create a set-vertex si .
• For each vertex v of G, create a copy-vertex v ′ and add edge v ′ si if v ∈ Si .
• Create an edge v ∗ u∗ , and add all edges between v ∗ and copy-vertices.

4

It is easy to check that H has a dominating set of size at most k+1 iff there is a set
of at most k copy-vertices that dominates all set-vertices, and thus corresponds
to a solution of MFVS. Furthermore, given a dominating set S of size at most
k+1 of H, we can obtain a set of copy-vertices which corresponds to a solution of
MFVS by replacing each set-vertex si ∈ S − {v ∗ , u∗ } by a copy-vertex in N (si ).
Since the vertex sets are pairwise disjoint in a compact representation, each
copy-vertex is adjacent to at most one set-vertex of a compact representation.
Each copy-vertex has degree at most h + 1, and thus H is a (h + 1)-degenerated
bipartite graph. Then we can apply the algorithm of Alon and Gutner [1], which
finds a dominating set of size at most l on a d-degenerated graph in time lO(dl) n,
to obtain a dominating set of size at most k + 1 in time (k + 1)O((h+1)(k+1)) n =
log k
O(chk
n) for a constant c2 . Therefore, given one compact representation of
2
each Gi , we can find a solution among these compact representations in time
log k
O(chk
n).
2
Since there are ck1 ways to choose a compact representation Ci of Gi , the total
hk log k
) = O∗ (chk log k ) for a constant c.
running time of the algorithm is O∗ (chk
1 c2

3

Dual Feedback Vertex Set Enumeration

In this section we give two FPT algorithms to enumerate all minimal dual feedback vertex set of size at most k by compact representations.
We first introduce the algorithm based on the proof of Theorem 1. In the
auxiliary graph H of Theorem 1, a vertex si represents a set Si and an edge
si sj represents the vertex set Si ∩ Sj . We need to cover all vertices of H by
selecting at most k edges or vertices. Since H contains at most 2k vertices and
k 2 edges, we can enumerate all minimal sets of at most k elements that covers
2
all vertices of H in time O∗ (2k +2k ) by exhausted search. Each minimal set is
a compact representation of minimal dual feedback vertex sets of the original
2
∗ k2 +k
edge-bicolored graph G. And the running time is O∗ (2k +2k c2k
) for
1 ) = O (c
a constant c.
Next we present another FPT algorithm which follows the idea of iterative
compression introduced by Reed, Smith and Vetta [20]. The main portion is to
solve the following problem:
Problem 1. Given an edge-bicolored graph G = (V, Eb ∪ Er ) and a dual feedback
vertex set S, find a dual feedback vertex set S ′ such that S ′ ∩S = ∅ and |S ′ | < |S|.
We show that all minimal solutions of Problem 1 can be enumerated by
compact representations in FPT time. To this end, we introduce some simple
reduction rules.
Rule 1. If there is a vertex v with d(v) = (0, 0), reduce to G = G − v.
Rule 2. If there is a vertex v with db (v) = 1 (resp., dr (v) = 1), remove the blue
(resp., red) edge incident to v.

5

Rule 3. For vertices v ∈
/ S and x, y ∈ S such that x and y belong to the same
blue (resp., red) component of G[S], and there are two blue (resp., red) edges vx
and vy, reduce to G = G − v and add v to S ′ .
Above three rules are obviously safe, and can be executed in polynomial time.
Call an edge-bicolored graph reduced graph if none of above rules is applicable.
Then in a reduced graph, there are no vertex v ∈
/ S such that d(v) = (0, 0),
b
r
(1, ∗) or (∗, 1). In a reduced graph G, let V>2
(resp., V>2
) be the set of vertices
in V (G) − S whose blue (resp., red) degree is larger than 2, V≤2 be the set
of vertices whose both blue degree and red degree are at most 2, i.e., V≤2 =
b
r
V (G) − S − V>2
− V>2
. A blue path P = {v1 , v2 , . . . , vp } is a maximal blue path
if vi ∈
/ S, db (vi ) = 2 for 1 ≤ i ≤ p and both v1 and vp are adjacent to vertices in
b
S ∪ V>2
. A maximal red path is defined similarly.
Now we introduce two rules that reduce the size of a maximal blue (red) path
in a reduced graph.
Rule 4. Let Pb (resp., Pr ) be a maximal blue (resp., red) path, and V ∗ be the
vertex set containing all vertices of Pb (resp., Pr ) with degree (2, 0) (resp., (0, 2)).
If |V ∗ | ≥ 2, select one vertex v ∈ V ∗ to represent V ∗ . For other vertices u ∈ V ∗ ,
remove u and add a blue (resp., red) edge between u’s two blue (resp., red)
neighbors.
Rule 5. Let Pb and Pr be a maximal blue path and red path respectively. If
Pb and Pr share common vertices, select one common vertex v to represent all
common vertices, i.e., V (Pb ) ∩ V (Pr ). For other vertices u ∈ V (Pb ) ∩ V (Pr ),
remove u and add a blue (resp., red) edge between u’s two blue (resp., red)
neighbors.
Lemma 1. Rule 4 and Rule 5 are safe. Let mb and mr , respectively, be the
numbers of maximal blue paths and maximal red paths. After applying Rule 4
and Rule 5, |V≤2 | ≤ (mb + 1) ∗ (mr + 1).
Proof. Suppose that v and u are both on a maximal blue path Pb and a maximal
red path Pr . Since all monochromatic cycles going through vertex u also go
through v, if a solution contains u, we can replace u with v. A minimal solution
may contain at most one vertex from V (Pb ) ∩ V (Pr ), and if it does contain
one such vertex, it doesn’t matter which vertex it contains. Thus we can use
one arbitrary vertex to represent V (Pb ) ∩ V (Pr ) and dissolve other vertices.
Therefore, Rule 5 is safe. Similarly, Rule 4 is safe. Note that Rule 4 and Rule 5
can be executed in polynomial time.
Now consider a maximal blue path Pb . We bound the number of vertices
in V (Pb ) ∩ V≤2 . By Rule 4, Pb contains at most one vertex with degree (2, 0).
By Rule 2, Pb contains no vertices with degree (2, 1). Then we consider vertices of Pb with degree (2, 2). Note that each such vertex is an intersection of
Pb and a maximal red path. By Rule 5, the number of such vertices is at most
mr . Therefore |V (Pb ) ∩ V≤2 | ≤ 1 + mr . Similarly, for a maximal red path Pr ,
|V (Pr ) ∩ V≤2 | ≤ 1 + mb . Since each vertex in V≤2 is on a maximal blue (red)

6

path, we have |V≤2 | ≤ (mb + 1) ∗ (mr + 1).
Let us focus on the blue (red) subgraph of an reduced graph. Guo et al. show
that there are at most 14|S| vertices with degree larger than 2 and at most 16|S|
maximal blue (red) paths in the proof of Lemma 2 and Lemma 6 in [13]. Relying
on these results, we enumerate all minimal solutions of Problem 1 in FPT time.
Lemma 2. All minimal solutions of Problem 1 can be enumerated in O∗ (c|S|
time for a constant c by compact representations.

2

+|S|

)

Proof. Reduce the input edge-bicolored graph G by Rule 1 to Rule 5.
b
r
We first determine which vertices of V>2 = V>2
∪ V>2
of G are in a minimal
solution. By the proof of Lemma 2 in [13], we have |V>2 | ≤ 28|S|. We guess
|S|−1
P 28|S|
which vertices of V>2 are in a solution S ′ and branch into
cases. In
t
t=0

each case, we put t one-element sets into C, delete these vertices in G and apply
Rule 1 to Rule 5 to further reduce the graph. Denote by G′ the resulting new
edge-bicolored graph .
Then we determine, for each case, which vertices of V≤2 of G′ are in a minimal
solution. Note that every vertex, that is in V≤2 and also remains in G′ , is on
a maximal blue (red) path of G′ . By the proof of Lemma 6 in [13], there are
at most 16|S| maximal blue paths, also maximal red paths in G′ . According to
Lemma 1, |V≤2 | ≤ (16|S| + 1)2, and we can use exhausted search to find vertices
in V≤2 ∩ S ′ .
|S|−1
P 28|S|+(16|S|)2 
2
The total running time is O∗ (
) = O∗ (c|S| +|S| ) for a cont
t=0

stant c.
Obtaining Lemma 2, we are capable to enumerate all minimal solutions of
DFVS by compact representations.
Theorem 3. All minimal solutions of DFVS can be enumerated in time O∗ (ck
by compact representations for a constant c.

2

+k

Proof. We first find feedback vertex sets Sb and Sr of size at most 2k for Gb
and Gr respectively, by the approximation algorithm of Bafna et al. [2]. Then
X = Sb ∪Sr is a dual feedback vertex set of size at most 4k. Let X ′ be a minimal
solution of size at most k. We guess which vertices of X are in X ′ , i.e., the vertex
k
P
|X|
set Y = X ∩ X ′ , and branch into
cases. For each case, X − Y is a
|Y |
|Y |=0

dual feedback vertex set of G − Y and X ′ − Y is a smaller dual feedback vertex
set that is disjoint from X − Y . By Lemma 2, all possible sets X ′ − Y can
(|X|−|Y |)2 +|X|−|Y |
be enumerated in time O∗ (c1
). Then combining Y and X ′ − Y ,
we get all minimal solutions of size at most k. The total running time for the
k
2
P
2
|X| (|X|−|Y |) +|X|−|Y |
algorithm is O∗ (
c
) which is O∗ (ck +k ) for a constant
|Y | 1
|Y |=0

c as |X| ≤ 4k and |Y | ≤ k.

)

7

4

Concluding remarks

In this paper, we established the fixed parameter tractability of DFVS, and
provided two algorithms to enumerate all minimal solutions of DFVS by compact
representations in FPT time. Furthermore, we established the fixed parameter
tractability of MFVS by generalizing the algorithm of DFVS.
Note that there are at most hk set-vertices in the auxiliary graph H in the
proof of Theorem 2, and each copy-vertex dominates at most h set-vertices.
Thus there are at most hk
which means
h copy-vertices with different neighbors,

that the number of copy-vertices can be up bounded by hk
.
Then
we can use
h
exhausted search of these copy-vertices to enumerate all minimal solutions of
MFVS.
Theorem 4. All minimal solutions of MFVS can be enumerated in FPT time
by compact representations.
For edge-bicolored graphs, instead of considering monochromatic cycles, we
can study alternating cycles which are cycles alternates between blue and red
edges. As suggested by Cai Leizhen, it is very interesting to consider the parameterzied complexity of the following problem:
Feedback Vertex Set for Alternating Cycles (AFVS):
Input: Edge-bicolored graph G, parameter k.
Question: Find a vertex set S of size at most k that hits all alternating
cycles.
We observe that AFVS is a generalization of Directed Feedback Vertex
Set [8] which hits all cycles of a digraph. Given a digraph G, we can obtain an
edge-bicolored graph G′ by replacing each arc uv by a blue edge ux and a red
edge xv. It is easy to check that G′ has a feedback vertex set of size at most k
for alternating cycles iff G has a directed feedback vertex set of size at most k.
Acknowledgments. The author is grateful to Cai Leizhen for helpful discussions and suggestions.

References
1. Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed
size in degenerated graphs. Algorithmica 54(4), 544–556 (2009)
2. Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected
feedback vertex set problem. SIAM Journal on Discrete Mathematics 12(3), 289–
297 (1999)
3. Bodlaender, H.L.: On disjoint cycles. International Journal of Foundations of Computer Science 5(01), 59–68 (1994)
4. Cai, L.: Parameterized complexity of cardinality constrained optimization problems. The Computer Journal 51(1), 102–121 (2008)

8
5. Cai, L., Ye, J.: Dual connectedness of edge-bicolored graphs and beyond. In:
Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS. LNCS, vol. 8635, pp.
141–152. Springer (2014)
6. Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures.
In: Kaplan, H. (ed.) SWAT. LNCS, vol. 6139, pp. 93–104. Springer (2010)
7. Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for
feedback vertex set problems. Journal of Computer and System Sciences 74(7),
1188–1198 (2008)
8. Chen, J., Liu, Y., Lu, S., O’sullivan, B., Razgon, I.: A fixed-parameter algorithm
for the directed feedback vertex set problem. Journal of the ACM 55(5), 21 (2008)
9. Cygan, M., Pilipczuk, M., Pilipczuk, M.: On group feedback vertex set parameterized by the size of the cutset. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern,
G. (eds.) WG. LNCS, vol. 7551, pp. 194–205. Springer (2012)
10. Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An O(2O(k) n3 )
FPT algorithm for the undirected feedback vertex set problem. Theory of Computing Systems 41(3), 479–492 (2007)
11. Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. In:
Complexity Theory: Current Research. pp. 191–225. Cambridge University Press,
Cambridge (1992)
12. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York
(1999)
13. Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based
fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal
of Computer and System Sciences 72, 1386–1396 (2006)
14. Kanj, I., Pelsmajer, M., Schaefer, M.: Parameterized algorithms for feedback vertex
set. In: IWPEC. LNCS, vol. 3162, pp. 235–247. Springer (2004)
15. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations. pp. 85–103. Plenum Press, New York (1972)
16. Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Information Processing Letters 114(10), 556–560 (2014)
17. Lokshtanov, D., Ramanujan, M., Saurabh, S.: Linear time parameterized algorithms for subset feedback vertex set. In: Halldórsson, M.M., Iwama, K.,
Kobayashi, N., Speckmann, B. (eds.) ICALP. LNCS, vol. 9134, pp. 935–946.
Springer (2015)
18. Raman, V., Saurabh, S., Subramanian, C.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) Algorithms
and Computation. LNCS, vol. 2518, pp. 241–248. Springer (2002)
19. Raman, V., Saurabh, S., Subramanian, C.: Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms 2(3),
403–415 (2006)
20. Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research
Letters 32(4), 299–301 (2004)
21. Wahlström, M.: Half-integrality, LP-branching and FPT algorithms. In: Chekuri,
C. (ed.) SODA. pp. 1762–1781. SIAM (2014)

