Algorithmica (2008) 52: 203–225

DOI 10.1007/s00453-007-9148-9

Short Cycles Make W -hard Problems Hard:

FPT Algorithms for W -hard Problems in Graphs
with no Short Cycles

Venkatesh Raman · Saket Saurabh

Received: 15 November 2006 / Accepted: 26 November 2007 / Published online: 3 January 2008
© Springer Science+Business Media, LLC 2007

Abstract We show that several problems that are hard for various parameterized
complexity classes on general graphs, become fixed parameter tractable on graphs
with no small cycles.
More specifically, we give fixed parameter tractable algorithms for D OMINATING
S ET, t -V ERTEX C OVER (where we need to cover at least t edges) and several of their
variants on graphs with girth at least five. These problems are known to be W [i]-hard
for some i ≥ 1 in general graphs. We also show that the D OMINATING S ET problem
is W [2]-hard for bipartite graphs and hence for triangle free graphs.
In the case of I NDEPENDENT S ET and several of its variants, we show these prob-
lems to be fixed parameter tractable even in triangle free graphs. In contrast, we show
that the D ENSE S UBGRAPH problem where one is interested in finding an induced
subgraph on k vertices having at least l edges, parameterized by k, is W [1]-hard even
on graphs with girth at least six.
Finally, we give an O(log p) ratio approximation algorithm for the D OMINATING
S ET problem for graphs with girth at least 5, where p is the size of an optimum dom-
inating set of the graph. This improves the previous O(log n) factor approximation
algorithm for the problem, where n is the number of vertices of the input graph.

Keywords Dominating set · Independent set · Set cover · t-vertex cover ·

Parameterized complexity

A preliminary version of this paper appeared in the Proceedings of 10th Scandinavian Workshop on
Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 4059, pp. 304–315, 2006.
V. Raman · S. Saurabh ()
The Institute of Mathematical Sciences, Chennai 600 113, India
e-mail: [email protected]
V. Raman
e-mail: [email protected]
204 Algorithmica (2008) 52: 203–225

1 Introduction

Parameterized complexity is a practical approach to deal with intractable computa-

tional problems having some small parameters. For decision problems with input
size n, and a parameter k (which typically, and in all the problems we consider
in this paper, is the solution size), the goal here is to design an algorithm with
runtime f (k)nO(1) where f is a function of k alone, as contrasted with a trivial
nk+O(1) algorithm. Problems having such an algorithm is said to be fixed parame-
ter tractable (FPT), and such algorithms are practical when small parameters cover
practical ranges. The book by Downey and Fellows [7] provides a good introduction
to the topic of parameterized complexity. For recent developments see the books by
Flum and Grohe [14] and Niedermeier [22].
There is a hierarchy of intractable parameterized problem classes above FPT, the
main ones are:

FPT ⊆ M[1] ⊆ W [1] ⊆ M[2] ⊆ W [2] ⊆ · · · ⊆ W [P ] ⊆ XP.

The principal analogue of the classical intractability class NP is W [1]. A convenient

source of W [1]-hardness reductions is provided by the result that I NDEPENDENT S ET
is complete for W [1] [7]. Other highlights of the theory include that D OMINATING
S ET, by contrast, is complete for W [2] [7]. Surprisingly we show that these problems
and several of their variants that are known to be hard in the W -hierarchy, are fixed
parameter tractable on graphs that have no short cycles—more specifically on graphs
with girth at least five. These problems are known to be NP-complete on such graphs
as well [3, 4]. We also look at the S ET C OVER problem where the size of the inter-
section of any pair of sets is bounded by a fixed constant. While the general version
of S ET C OVER is known to be W [2]-complete, we prove this special version fixed
parameter tractable.
Most of our algorithms are based on the method of kernelization. The main idea of
kernelization is to replace a given instance (I, k) by a simpler instance (I  , k  ) using
some data reduction rules in polynomial time such that (I, k) is a yes instance if and
only if (I  , k  ) is a yes instance and |I  | is bounded by a function of k alone. The
reduced instance is called kernel for the problem. For most of our problems we give
polynomial sized kernel in polynomial time.

1.1 Organization of the Rest of the Paper

In Sect. 2, we look at the D OMINATING S ET problem and show that the problem
is W [2]-complete even in bipartite graphs and split graphs (a graph in which the
vertices can be partitioned into a clique and an independent set). Though variations
of D OMINATING S ET like R ED -B LUE D OMINATING S ET [8] and C ONSTRAINED
D OMINATING S ET [13] have been studied before and shown to be W [2]-complete,
to the best of our knowledge the standard D OMINATING S ET problem (which we
consider here) in bipartite graphs has not been studied before. Our observation means
that the dominating set problem is W [2]-complete in triangle free graphs. Then we
show that the problem is FPT if the input graph has girth at least 5. It turns out that
Algorithmica (2008) 52: 203–225 205

this result can be generalized to several variants of the D OMINATING S ET problem

on graphs with girth at least five.
In Sect. 3, we look at the S ET C OVER problem for which D OMINATING S ET is a
special instance. S ET C OVER problem is known to be W [2]-complete [7]. Here we
show that if the set cover instance satisfies the property that the intersection of any
pair of its sets is bounded by a fixed constant then the problem is fixed parameter
tractable.
In Sect. 4, we look at t -V ERTEX C OVER and t -D OMINATING S ET problems.
These are generalizations of V ERTEX C OVER and D OMINATING S ET problems. In
the t -V ERTEX C OVER problem, we are interested in finding a set of at most k ver-
tices covering at least t edges and in the t -D OMINATING S ET problem the objective
is to find a set of at most k vertices that dominates at least t vertices. Both these
problems have been parameterized in two different ways: by k alone and by both
k and t. Both these problems are fixed parameter tractable when parameterized by
both k and t. Bläser [5] gave O(2O(t) nO(1) ) algorithm for both the problems using
color coding technique. Guo et. al. [16] have shown that t -V ERTEX C OVER is W [1]-
complete when parameterized by k alone. It is easy to see that the t -D OMINATING
S ET is W [2]-complete by a reduction from D OMINATING SET when parameterized
by k alone. We show that both these problems are fixed parameter tractable in graphs
with girth at least five, when parameterized by k alone.
In Sect. 5, we look at the I NDEPENDENT S ET problem and several of its variants.
We show that these problems are fixed parameter tractable in triangle free graphs
while they are W [1]-complete in general graphs.
In contrast to our results in earlier sections, in Sect. 6, we exhibit a problem that
is W [1]-hard in graphs with no small cycles. This is the D ENSE S UBGRAPH prob-
lem [20]. Here, given a graph G = (V , E) and positive integers k and l, the problem
is to determine whether there exists a set of at most k vertices C ⊆ V such that the
induced subgraph on C has at least l edges; here k is the parameter.
In Sect. 7, we deviate and look at the approximability result of the D OMINAT-
ING S ET problem. We conclude that the D OMINATING S ET problem is as hard to
approximate in bipartite graphs as in general undirected graphs. We also give an ap-
proximation algorithm of factor O(log p) for the D OMINATING S ET problem if the
input graph has girth at least 5, where p is the size of an optimum dominating set
of the input graph. This improves the previously known approximation algorithm of
factor O(log n), where n is the number of vertices in the input graph.
Section 8 gives some concluding remarks and open problems.
We assume that all our graphs are simple and undirected. Given a graph G =
(V , E), n represents number of vertices, and m represents the number of edges. For
a subset V  ⊆ V , by G[V  ] we mean the subgraph of G induced on V  . By N (u) we
represent all vertices (excluding u) that are adjacent to u, and by N [u], we refer to

N(u) ∪ {u}. Similarly, for a subset D ⊆ V , we define N [D] = v∈D N[v]. By the
girth of a graph, we mean the length of the shortest cycle in the graph. We say that a
graph is a Gi graph if the girth of the graph is at least i. A vertex is said to dominate
all its neighbors.
206 Algorithmica (2008) 52: 203–225

2 D OMINATING S ET and Its Variants

In this section we look at the D OMINATING S ET problem and its variants.

D OMINATING S ET: Given a graph G = (V , E) and an integer k ≥ 0, determine
whether there exists a set D ⊆ V , of size at most k, such that for every vertex
u ∈ V , N[u] ∩ D = ∅.
We say that the set D “dominates” the vertices of G. We first show that D OMINATING
S ET problem is W [2]-complete in bipartite graphs and split graphs by a reduction
from the same problem in general undirected graphs. Then we give a fixed parameter
tractable algorithm for the problem in graphs with girth at least 5.

2.1 D OMINATING S ET in Bipartite and Split Graphs

Theorem 1 D OMINATING S ET problem is W [2]-complete in bipartite graphs.

Proof We prove this by giving a reduction from the D OMINATING S ET problem in

general undirected graphs. Given an instance (G = (V , E), k) of D OMINATING S ET,
we construct a bipartite graph H = (V  , E  ). Let z1 and z2 be two new vertices (not
in V ). Now V  = V1 ∪V2 where V1 = {u1 | u ∈ V }∪{z1 } and V2 = {u2 | u ∈ V }∪{z2 }.
If there is an edge (u, v) in E then we draw the edges (u1 , v2 ) and (v1 , u2 ). We also
draw edges of the form (u1 , u2 ) for every u ∈ V . Finally, we add an edge from every
vertex in V1 to z2 . This completes the construction of H .
We show that G has a dominating set of size k if and only if H has a dominating set
of size k + 1. Let D be a dominating set of size k in G. Then clearly D  = {u1 | u ∈ D}
∪ {z2 } is a dominating set of size k + 1 in H . Conversely, let K be a dominating set
in H of size k + 1. Observe that either z1 or z2 must be part of K as z2 is the unique
neighbor of z1 . Without loss of generality, we can assume that z2 ∈ K, as otherwise
we could delete z1 and include z2 in K and still have a dominating set of size at most
k + 1 in H . Now take D = {u | u ∈ V , u1 or u2 ∈ K}. Clearly D is of size k. We
show that D is a dominating set in G. For any u ∈ / D, u2 ∈/ K and hence there exists
some v1 ∈ K such that v1 dominates u2 in H . But this implies v ∈ D and (v, u) ∈ E,
which shows that v dominates u. This proves that D is a dominating set of size k for
G and establishes the theorem. 

Since every bipartite graph is also triangle free, we have the following corollary.

Corollary 1 D OMINATING S ET problem is W [2]-complete in triangle free graphs.

Theorem 2 D OMINATING S ET problem is W [2]-complete in split graphs.

Proof We again prove this by giving a reduction from the D OMINATING S ET prob-
lem in general undirected graphs. Given an instance (G = (V , E), k) of D OMINAT-
ING S ET , we construct a split graph H = (V  , E  ). We create two copies of V namely
V1 = {u1 | u ∈ V } and V2 = {u2 | u ∈ V }. If there is an edge (u, v) in E then we draw
the edges (u1 , v2 ) and (v1 , u2 ). We also draw edges of the form (u1 , u2 ) for every
Algorithmica (2008) 52: 203–225 207

u ∈ V . Now we make H [V1 ] a complete graph by adding all arcs of the form (u1 , v1 )
for every pair of vertex u1 , v1 ∈ V1 . This completes the construction of H . It is easy
to see that H is a split graph with H [V1 ] as a clique and H [V2 ] as an independent
set.
As in the proof of Theorem 1, it is easy to see that G has a dominating set of size k
if and only if H has a dominating set of size k. 

An undirected graph is chordal if every cycle of length greater than three possesses
a chord, that is, an edge joining two non consecutive vertices of the cycle. It is well
known that every split graph is also a chordal graph and hence Theorem 2 implies
that the D OMINATING S ET is W [2]-complete in chordal graphs. As a corollary of
Theorem 2 we get the following.

Corollary 2 D OMINATING S ET problem is W [2]-complete in chordal graphs.

2.2 FPT Algorithm for D OMINATING S ET in G5 Graphs

We give a fixed parameter tractable algorithm for the D OMINATING S ET problem in

graphs with girth at least 5 (G5 graphs) and also observe that various other W -hard
problems become tractable for G5 graphs.
Our algorithm follows a branching strategy where at every iteration we find a
vertex that needs to be included in the D OMINATING S ET which we are trying to
construct. Once a vertex is included, we can at best delete that vertex. Though the
neighbors of the vertex are dominated, we can not remove these vertices from further
consideration as they can be useful to dominate other vertices.
Hence we resort to a coloring scheme for the vertices, similar to the one suggested
by Alber et al. in [1, 2]. At any point of time of the algorithm, the vertices are colored
as below:
1. Red—The vertex is included in the dominating set D which we are trying to con-
struct.
2. White—The vertex is not in the set D, but it is dominated by some vertex in D.
3. Black—The vertex is not dominated by any vertex of D.
Now we define the dominating set problem on the graph with vertices colored with
White, Black or Red as above. We call a graph colored red, white and black as above,
as a rwb-graph.
RWB-D OMINATING S ET: Let G be a G5 graph (graph with girth at least 5)
with vertices colored with Red, White or Black satisfying the following condi-
tions, and let k be a positive integer parameter. Let R, W and B be the set of
vertices colored red, white and black respectively.
1. Every white vertex is a neighbor of a red vertex.
2. Black vertices have no red neighbors.
3. |R| ≤ k.
Does G have at most k − |R| vertices that dominate all the black vertices?
208 Algorithmica (2008) 52: 203–225

It is easy to verify that if we start with a general G5 graph with all vertices colored
black, and color all vertices we want to include in the dominating set as red, and their
neighbors as white, the graph we obtain at every intermediate step is a rwb-graph,
and the problem we will have at the intermediate steps is the RWB-D OMINATING
S ET problem.
The following lemma essentially shows that if the rwb-graph has a black or white
vertex dominating more than k black vertices, then such a vertex must be part of every
solution of size at most k, if one exists.

Lemma 1 Let (G = (R ∪ W ∪ B, E), k) be an instance of the RWB-D OMINATING

S ET problem where G is a G5 graph and k a positive integer. Let v be a black or
white vertex with more than k − |R| black neighbors. Then if G has a set of size at
most k − |R| that dominates all black vertices, then v must be part of every such set.

Proof Let D be a set of size k − |R| that dominates all black vertices in G, and
suppose v ∈/ D. Let X be the set of black neighbors of v which are not in D and Y
be the set of black neighbors of v in D. So |X| + |Y | > k − |R|. Observe that for
every vx ∈ X we have a neighbor ux ∈ D which is not in Y (otherwise v, vx , ux is
a 3 length cycle). Similarly, for x, y ∈ X, x = y ⇒ ux = uy . Otherwise v, x, ux , y
will form a cycle of length 4. This means that |D| ≥ |X| + |Y | > k − |R| which is a
contradiction. 

Given a rwb-graph, Lemma 1 suggests the following simple reduction rule:

(R1) If there is a white or a black vertex v having more than k − |R| black neighbors,
then color v red and color its neighbors white.
Our goal now is to pick enough white or black vertices to dominate the black vertices.
So the following reduction rules are obviously justified.
(R2) If a white vertex is not adjacent to a black vertex, delete the white vertex.
(R3) If there is an edge between two white vertices, delete the edge.
(R4) If |R| > k, then stop and return NO.
The following lemma follows from Lemma 1.

Lemma 2 Let G = (R ∪ W ∪ B, E) be an instance of RWB-D OMINATING S ET

and let G = (R  ∪ W  ∪ B  , E  ) be the reduced instance after applying rules (R1) to
(R4) once. Let k be an integer parameter. Then G is a yes instance if and only if G
is a yes instance. That is G has a set of size at most k − |R| dominating all vertices
in B if and only G has a set of size at most k − |R  | dominating all vertices in B  .

Let G be an instance of RWB-D OMINATING S ET and let G be the reduced in-

stance after applying the reduction rules (R1)–(R4) until no longer possible. Then
we show that if G is a yes instance (and hence G is a yes instance), the number of
vertices in G is bounded by polynomial in k. More precisely we show the following
lemma.
Algorithmica (2008) 52: 203–225 209

Lemma 3 Let (G, k) be a yes instance of RWB-D OMINATING S ET and (G , k  )

be the reduced instance of (G, k) after applying the rules (R1)–(R4) until no longer
possible. Then, the number of vertices in G is O(k 3 ), that is, a kernel of size at most
O(k 3 ) can be obtained for RWB-D OMINATING S ET.

Proof Let R  , B  and W  be the set of vertices colored red, black and white respec-
tively in G . We argue that each of |R  |, |B  | and |W  | is bounded by a function of k.
Because of (R4) (and the fact that G is a yes instance), |R  | ≤ k.
Because of (R1), every vertex colored white or black has at most k − |R  | black
neighbors. Also we know that no red vertex has a black neighbor. Since G is a yes
instance, there are at most k (k − |R  | to be more precise) black or white vertices dom-
inating all black vertices. Since each of them can dominate at most k black vertices,
we conclude that |B  | can be at most k 2 .
We argue that |W  | ≤ k 3 . Towards this end, we just show that every black vertex
has at most k white neighbors. Since |B  | ≤ k 2 , and every white vertex is adjacent to
some black neighbor (because of (R2) and (R3)), the conclusion will follow.
Note that every white vertex has a red neighbor. Observe that the white neighbors
of any black vertex (any vertex for that matter) will have all distinct red neighbors.
I.e. if w1 and w2 are white neighbors of a black vertex b, then there is no overlap
between the red neighbors of w1 and the red neighbors of w2 . This is because if w1
and w2 have a common red neighbor r, then we will have a 4-cycle b, w1 , r, w2 , b.
Since |R  | ≤ k, it follows that a black vertex can have at most k white neighbors.
This proves the required claim. 

Thus we have the following theorem.

Theorem 3 The RWB-D OMINATING S ET problem can be solved in

O(k k+O(1) + nO(1) ) time for G5 graphs.

Proof It is easy to see that the reduction rules (R1) to (R4) take polynomial time to
execute. When none of these rules can be executed, by Lemma 3, we have that the
number of vertices in the resulting graph is O(k 3 ), and each vertex has at most k
black neighbors. We can just try all possible subsets of size at most k of the vertex
set of the reduced graph, to see whether that subset dominates all the black vertices.
If any of them does, then we say YES and NO otherwise. This will take O(k 3k+O(1) )
time.
Alternatively, we can apply a branching technique on the black vertices, by select-
ing a black vertex or any of its neighbors in the dominating set. More precisely, let
v be a black vertex. Then we branch on N [v] by including w ∈ N [v] in the possible
dominating set D we are constructing and look for a solution of size k − 1 in G − {w}
where w is colored red and all its neighbors are colored white for every w ∈ N[v].
This results in an O((k + 1)k+O(1) ) time algorithm. 

Now to solve the general D OMINATING S ET problem in G5 graphs, simply color

all vertices black and solve the resulting RWB-D OMINATING S ET problem using
Theorem 3. Thus we have
210 Algorithmica (2008) 52: 203–225

Theorem 4 Parameterized D OMINATING S ET problem can be solved in O(k k+O(1)

+ nO(1) ) time for G5 graphs.

Parameterized version of C ONNECTED D OMINATING S ET (where one is inter-

ested in dominating set which is connected) or I NDEPENDENT D OMINATING S ET
(where one is interested in dominating set which is independent) are also known to
be W [2]-complete [7]. Since the reduction rules (R1)–(R4) apply for any dominat-
ing set, using Lemma 3 we can obtain a kernel of size at most O(k 3 ) for both these
problems. For the I NDEPENDENT D OMINATING S ET problem we also check that R
remains an independent set when we add a vertex to it while applying reduction rule
(R1), else we return NO. Furthermore in the proof of the Theorem 3, we try all possi-
ble subsets of size at most k and look for a connected or independent dominating set,
as required. This results in the following corollary.

Corollary 3 Parameterized C ONNECTED D OMINATING S ET and I NDEPENDENT

D OMINATING S ET problems can be solved in O(k 3k+O(1) + nO(1) ) time for G5
graphs.

A number of other variants of dominating set problem which are W [2]-hard can be
shown to be fixed parameter tractable in a similar way for G5 graphs though not using
kernelization. We give necessary details for a few of them in the next subsections.

2.3 R ED -B LUE D OMINATING S ET and C ONSTRAINT B IPARTITE D OMINATING

S ET

In this section we give FPT algorithms for R ED -B LUE D OMINATING S ET and C ON -

STRAINED B IPARTITE D OMINATING S ET problems for G5 graphs. We first give an
algorithm for R ED -B LUE D OMINATING S ET problem which is defined as follows.
R ED -B LUE D OMINATING S ET [8]: Given a bipartite graph G = (V , E) with
V bipartitioned as Vred ∪ Vblue and a positive integer k. Does there exist a subset
D ⊆ Vred with |D| ≤ k and Vblue ⊆ N (D)?

Theorem 5 R ED -B LUE D OMINATING S ET is FPT for G5 graphs.

Proof Any two vertices in Vred have at most one common neighbor in Vblue as other-
wise there will be a four cycle in G. Hence, the following reduction rule is justified.
(R1 ) If x ∈ Vred has degree more than k then include x ∈ D.
The correctness of (R1 ) follows from the fact that if we do not select x in D then
we need more than k vertices from Vred to dominate N (x) as any vertex y ∈ Vred ,
y = x, can dominate at most one vertex of N (x). Hence after exhaustively applying
reduction rule (R1 ) if the size of D is more than k we answer NO.
Remove N[D] from G, i.e., set Vred = Vred \ D and Vblue = Vblue \ N (D). Now
the degree of every vertex in Vred is at most k and we are looking for a set of size
at most k − |D| in Vred such that it dominates all the vertices of Vblue . Since every
vertex in Vred has degree at most k, the size of the set Vblue is bounded above by k 2
Algorithmica (2008) 52: 203–225 211

((k − |S|)k to be precise) else the answer is NO. We can not bound the size of the set
Vred anymore, as we do not have any bound on the degree of the vertices in Vblue . So
to find the desired dominating set in Vred (dominating all the vertices in Vblue ) we do
as follows:
– For all partitions P of Vblue into at most k − |D| parts, say P = {P1 , P2 , . . . , Pj },
1 ≤ j ≤ k − |D|, for each Pi , 1 ≤ i ≤ j , check whether there exists a vertex ui ∈
Vred such that Pi ⊆ N (ui ). Call the partition P valid if for all 1 ≤ i ≤ j , there
exists ui ∈ Vblue such that Pi ⊆ N (ui ) and the set {ui | 1 ≤ i ≤ j } is called the
witness set. If any partition P is valid then return YES with the corresponding
witness set else return NO.
It is easy to see that there exists a subset of Vred of size at most k − |D| dominating all
vertices of Vblue if and only if there exists a valid partition. Number
 of ways in which
n indistinguishable objects can be partitioned into r ways is n+r−1 r−1 [18]. Hence the
total number of partitions P considered for our case is upper bounded by

 k 2
k−|D|
+i −1

.
i −1
i=1

Since the total number of partitions is upper bounded by O(k 2k+O(1) ), the result that
R ED -B LUE D OMINATING S ET is FPT for G5 graphs follows. 

Next we study C ONSTRAINT B IPARTITE D OMINATING S ET problem which is

defined as follows:
C ONSTRAINT B IPARTITE D OMINATING S ET (CBDS) [13]: Given a bipartite
graph G = (V , E) with V partitioned as V1 ∪ V2 and positive integers k1 and k2 .
Does there exist subsets D1 ⊆ V1 and D2 ⊆ V2 with |D1 | ≤ k1 and |D2 | ≤ k2
such that V2 ⊆ N (D1 ) and V1 ⊆ N (D2 ).

Theorem 6 Parameterized C ONSTRAINT B IPARTITE D OMINATING S ET is FPT for

G5 graphs.

Proof To solve this problem we just need to solve two instances of R ED -B LUE D OM -
INATING S ET problem. The instances of R ED -B LUE D OMINATING S ET problem we
solve are:
1. Vred = V1 , Vblue = V2 and parameter is k1 .
2. Vred = V2 , Vblue = V1 and parameter is k2 .
We return YES for CBDS problem if both the instances return YES and as D1 the
red-blue dominating set returned by instance 1 and as D2 the red-blue dominating set
returned by instance 2. If either of the instances of R ED -B LUE D OMINATING S ET
problem returns NO, then we return NO for the CBDS problem. 

2.4 T HRESHOLD D OMINATING S ET

This problem generalizes D OMINATING S ET and is formally defined as follows:

212 Algorithmica (2008) 52: 203–225

T HRESHOLD D OMINATING S ET (TDS) [6]: Given a graph G = (V , E) and

positive integers k and r. Is there a set of at most k vertices V  ⊆ V such that
for every vertex u ∈ V , N[u] contains at least r elements of V  ?

Theorem 7 T HRESHOLD D OMINATING S ET parameterized by k is FPT for G5

graphs.

Proof First we observe that if k < r, then the answer is NO. We assume that r ≤ log n,
as otherwise k ≥ log n and we have a kernel of size at most 2k . Now we can solve the
problem by checking all subsets of size at most k for the desired threshold dominating
set.
Our algorithm is again based on the following simple reduction rule whose cor-
rectness follows from Lemma 1.
(R1 ) If x ∈ V has degree more than k then include x ∈ V  .
So basically we select all the vertices of degree more than k of V in V  and hence if
the size of V  is more than k then we answer NO.
Next we assign a color to all the vertices. We assign white color to all the vertices
(including vertices in V  ) which have enough (at least r) neighbors in V  and black
to the rest. Let B and W , as usual, represent the set of black and white vertices
respectively and set B  = B \ V  and W  = W \ V  . Apply reduction rules (R2) and
(R3) of Lemma 2 exhaustively. The rule (R3) makes G[W ] an independent set. Now
the problem reduces to finding a set S  of size at most k − |V  | in V \ V  such that
V  ∪ S  is a desired threshold dominating set for G, in particular for the vertices of B.
Since every vertex in V \ V  has degree at most k and we are looking for S  of size
at most k in V \ V  , the size of |B| is bounded above by k 2 , as otherwise we answer
NO.
Now what we have is a generalized version of T HRESHOLD D OMINATING S ET
problem where we have a set of j ≤ k 2 black vertices B = {u1 , . . . , uj }, each with
a positive integer ri (ri = r − |N[vi ] ∩ V  |), 1 ≤ i ≤ j . We are looking for a set
S  ⊆ (W  ∪ B  ) of size at most k − |V  | such that for every ui ∈ B, |N (ui ) ∩ S  | ≥ ri
in G where the vertex set of G is V (G ) = B ∪ W  and the edge set of G is E(G ) =
{(u, v) ∈ E | u ∈ W  , v ∈ B or u ∈ B, v ∈ B}.
To solve this generalized version of T HRESHOLD D OMINATING S ET problem, we
need to generalize our partition arguments used in the Theorem 5 suitably. The major
differences are that G is no more bipartite and that there are vertices which need more
than 1 (possibly r) vertices in the desired threshold dominating set. To overcome this
difficulty, we make a multiset M from B by having ri copies for each vertex ui ∈ B.
Clearly the size of |M| is bounded above by rk 2 . Now if we apply the partition idea
of Theorem 5 it is possible that the same vertex may dominate multiple copies of the
same vertex. To deal with this call a partition P = {P1 , P2 , . . . , Pα } valid if (a) there
exists a subset S  ⊆ B  ∪ W  forming a system of distinct representatives; that is for
all 1 ≤ i ≤ α, there exists a distinct ui ∈ S  such that Pi ⊆ N (ui ) and (b) each Pi
contains at most one copy of any vertex of B. The set S  is a witness set. So to find
the desired threshold dominating set in B  ∪ W  we proceed as follows.
Algorithmica (2008) 52: 203–225 213

– For all partitions P of M in at most k − |V  | parts, say P = {P1 , P2 , . . . , Pα },

1 ≤ α ≤ k − |V  |, we check whether P is a valid partition. If any partition P is
valid then return YES with the corresponding witness set else return NO.
For a fixed partition P = {P1 , P2 , . . . , Pα }, we can do the validity testing and find a
corresponding witness set in polynomial time as follows. Testing for duplicate copies
in Pi ’s are easy. For the other part we first define the set

Ii = {u ∈ (B  ∪ W  ) | Pi ⊆ NG (u)},

where NG (u) denotes the neighbors of u in G . Now we make the bipartite incidence
bipartite graph G∗ = (X ∪ Y, E  ), where X
graph for the sets {I1 , . . . , Iα }, that is a 
has a vertex xi for every set Ii and Y = αl=1 Il and there is an edge between (xi , u)
if u ∈ Ii . Now finding a valid system of distinct representatives reduces to finding
a maximum bipartite matching in G∗ saturating X, for which there is a classical
polynomial time algorithm of Edmonds [11].
The total number of partitions P considered for our case is upper bounded by

 | 
k−|V 
rk 2 + i − 1
,
i−1
i=1

which is at most O((rk 2 )k+O(1) ). Since r ≤ log n and (log n)k ≤ n + (2k log k)k for
all n and k ≤ n, we have the desired result that T HRESHOLD D OMINATING S ET
problem is FPT for G5 graphs. 

3 S ET C OVER with Bounded Intersection among Sets

D OMINATING S ET problem is well known to be a special instance of the S ET C OVER

problem defined below.
S ET C OVER : Given a base set (or universe) U = {s1 , s2 , . . . , sn }, a collection
S = {S1 , S2 , . . . , Sm } of subsets of U (Si ⊆ U, 1 ≤ i ≤ m) such that m i=1 Si =
U and a positive  integers k, does there exist a sub-collection S  of S of size at
most k such that Sj ∈S  Sj = U .
Given an instance (G = (V , E), k) of the D OMINATING S ET problem, we can for-
mulate it as an instance of the S ET C OVER problem by taking U = V and S = {Sv =
N[v] | v ∈ V }. It is easy to verify that G has a dominating set of size k if and only if
(U, S) has a set cover of size at most k. Hence the parameterized version of the S ET
C OVER problem is W [2]-complete [7].
Here, we show that a special case of the S ET C OVER problem, that generalizes
the D OMINATING S ET problem for G5 graphs to be fixed parameter tractable. More
specifically, we show if the S ET C OVER instance (U, S) satisfies the property that for
any pair of sets Si and Sj in S, |Si ∩ Sj | ≤ c, for a fixed constant c, then the problem
is fixed parameter tractable. We call this variant of the S ET C OVER problem, where
every pair of sets in the given family intersect in at most c elements, as B OUNDED
I NTERSECTION S ET C OVER (BISC) problem.
214 Algorithmica (2008) 52: 203–225

Observe that if the input graph G of the dominating set problem is a G5 graph
then the sets in its corresponding set cover instance satisfies a property that for any
pair of sets Su and Sv in S, |Su ∩ Sv | ≤ 2.

Theorem 8 The BISC problem is fixed parameter tractable.

Proof If there is a set Si ∈ S such that |Si | > ck then Si must be in every k-sized
set cover. Otherwise, we need more than k sets to cover all the elements of U since
every other set can cover at most c elements of Si . So this gives us a following simple
reduction rule:

Rule 1 Given a set cover instance, (U, S, k), if there exists Si ∈ S such that |Si | > ck
then obtain a new reduced instance of set cover as following:
– U ← U − Si .
– S ← {S − Si | S ∈ S}. If there are multiple copies of some set, then remove all but
one copy of the same.
– k ← k − 1.

If k becomes 0 and U is non-empty then this is a no instance for the problem and
we stop. We apply the Rule 1 until all the sets in S is of size at most ck  , where k  ≤ k.
As k  sets of size ck  can only cover at most ck 2 ≤ ck 2 elements of U , if |U| > ck 2
then it is a no instance of the problem. The reduction rule also ensures that every set
in S is distinct. But then the number of distinct sets of size at most ck in S can be at
most the number of distinct subsets of U . This gives us that if |U| ≥ 2ck then
ck 
     ck
|U| |U| cek 2
|S| = ≤ ck ≤ ck = ceck k ck+1
i ck ck
i=1

and if |U| < 2ck then

ck 
 
|U|
|S| = ≤ 22ck = 4ck .
i
i=1

Now it suffices to try each sub-collection S  ⊆ S of size k and return YES if any of
them covers the set U and NO otherwise. This has following time complexity:
   ck ck+1 k
ceck k ck+1 ce k e 2
≤ = (ce)k (ek)ck .
k k
Since c is a fixed constant, it follows that the running time results in a fixed parameter
tractable algorithm. 

4 t -V ERTEX C OVER and t -D OMINATING S ET Problems

t -V ERTEX C OVER and t -D OMINATING S ET problems are respectively, generaliza-

tions of classical V ERTEX C OVER and D OMINATING S ET problems. Here the objec-
tive is not to cover all the edges or to dominate all the vertices but to cover at least t
Algorithmica (2008) 52: 203–225 215

edges or to dominate at least t vertices with at most k vertices. More precisely they
are defined as follows:
t -V ERTEX C OVER : Given a graph G = (V , E) and positive integers k and t,
does there exist a set of at most k vertices C ⊆ V such that |{e = (u, v) ∈
E | C ∩ {u, v} = ∅}| ≥ t.
t -D OMINATING S ET: Given a graph G = (V , E) and positive integers k and t,
does there exist a set of at most k vertices D ⊆ V such that |N[D]| ≥ t.
The t -V ERTEX C OVER and t -D OMINATING S ET problems have been parame-
terized in two ways. They are either parameterized by k or by t and k. Both these
problems are FPT when parameterized by both k and t [5] and are hard for different
level of W -hierarchy when parameterized by k alone. t -V ERTEX C OVER is W [1]-
complete [16] and t -D OMINATING S ET is W [2]-complete when parameterized by k
alone.
Here, we first give a simple algorithm for the t -V ERTEX C OVER when parameter-
ized by both t and k and then show that this problem is FPT even when parameterized
by k alone in G5 graphs. We then extend this result to the t -D OMINATING S ET prob-
lem for G5 graphs when parameterized by k alone.
Our algorithms for the t -V ERTEX C OVER depend on the following lemma.

Lemma 4 Let (G = (V , E), k, t) be a yes instance of the t -V ERTEX C OVER and

v be a vertex of maximum degree in G. Then there exists a t-vertex cover C whose
intersection with N[v] is nonempty, i.e. N[v] ∩ C = ∅.

Proof Since G is a yes instance of the problem there exists a t-vertex cover C of
size at most k and covering at least t edges. If N[v] ∩ C = ∅ then choose C  =
C − {u} + {v} where u is any vertex in C. Since v is a vertex of highest degree and
none of its neighbors is in C, C  also covers at least t edges and is of size at most k. 

Suppose that the given graph has maximum degree bounded by d. Since there
exists a t-vertex cover containing either a maximum degree vertex u or one of the
neighbors of u, we can branch on u and on each of the (at most) d neighbors of u
giving rise to a (d + 1)-way branching. The following theorem is immediate from
this.

Theorem 9 Let G be a graph with maximum degree d. Then t-V ERTEX C OVER can
be solved in O((d + 1)k n) time.

Given a graph G = (V , E) and positive integer parameters t and k, if there exists

a vertex of degree at least t then we get a t-vertex cover by choosing the vertex. So
without loss of generality, we can assume that every vertex has degree at most t − 1.
Then from Theorem 9, we have

Corollary 4 t-V ERTEX C OVER can be solved in O(t k n) in general graphs.

Suppose, instead of trying to cover at least t edges, we want to cover all but t
edges (where t is a parameter) using at most k vertices. That is, we want an induced
216 Algorithmica (2008) 52: 203–225

subgraph on n − k vertices with at most t edges. We call it the (m − t)-V ERTEX

C OVER problem. Such a parameterization is known as dual parameterization and
dual problems are, in general, natural and equally interesting [7, 19]. For example
V ERTEX C OVER is fixed parameter tractable whereas the dual of V ERTEX C OVER
is the I NDEPENDENT S ET problem (which is the same as choosing n − k vertices to
cover all edges) and is W [1] complete.
The (m − t)-V ERTEX C OVER problem can also be parameterized in two ways,
by k alone and by k and t. When we have both t and k as parameters then we solve
this problem by branching on an edge e = (u, v). Here we branch by choosing either
the vertex u or the vertex v or e which means that we are looking for a solution
which contains either u or v or does not cover e. So we get the following branching
recurrence:
T (k, t) ≤ 2T (k − 1, t) + T (k, t − 1).
This immediately gives us the following theorem.

Theorem 10 (m − t)-V ERTEX C OVER can be solved in O(3t+k (n + m)) time. Thus
(m − t)-V ERTEX C OVER is fixed parameter tractable if parameterized by t and k.

When (m−t)-V ERTEX C OVER problem is parameterized by k alone, we can show

the following theorem.

Theorem 11 The (m − t)-V ERTEX C OVER problem is W [1]-hard when parameter-

ized by k alone.

Proof We give a reduction from W [1]-complete t-V ERTEX C OVER problem where
we need at most k vertices to cover at least t edges. Given (G = (V , E), k, t1 ), an
instance of t-V ERTEX C OVER problem, we map it to (G = (V , E), k, t2 ) where t2 =
|E| − t1 as an instance of (m − t)-V ERTEX C OVER problem. Now it is easy to see
that (G = (V , E), k, t1 ) is a yes instance of t-V ERTEX C OVER problem if and only if
(G = (V , E), k, t2 ) is a yes instance of (m − t)-V ERTEX C OVER problem. 

Now we show that the t-V ERTEX C OVER problem is FPT for G5 graphs when
parameterized by k alone. We will see that this result also applies to (m − t)-V ERTEX
C OVER problem when parameterized by k alone.

Theorem 12 t-V ERTEX C OVER is fixed parameter tractable for G5 graphs when
parameterized by k alone. The algorithm runs in O((k + 1)k (n + m)) time.

Proof Without loss of generality we can assume that the maximum degree of this
graph is not bounded by a function of k, otherwise the problem is fixed parameter
tractable by Theorem 9. Let v0 be a vertex of highest degree and let v1 , v2 , . . . , vr be
its neighbors. Further assume that

deg(v1 ) ≥ deg(v2 ) ≥ · · · ≥ deg(vk ) ≥ · · · ≥ deg(vr ).

Algorithmica (2008) 52: 203–225 217

Let A = {v0 , v1 , . . . , vk }. We show that if there exists any t-vertex cover then there is
one which contains either v0 or one of its k highest degree neighbors. More precisely,
we prove the following claim:

Claim There exists a t-vertex cover C such that A ∩ C = ∅, if one exists.

The claim says that if there exists any t-vertex cover then there exists a t-vertex
cover C containing at least one vertex of A. We then branch on the vertices of the
set A, and look for a solution of size k − 1, covering t-deg(vi ) edges in G − {vi },
where 0 ≤ i ≤ k and recursively use this claim on the respective subgraphs. Hence
the claim proves that t-vertex cover is fixed parameter tractable.
Now we are left with proving the claim. We show the claim by contradiction.
Assume to the contrary that no t-vertex cover intersects A. By Lemma 4 we know
that there exists a t-vertex cover C containing one of v0 ’s neighbors. Let vl be
a neighbor of v0 in C. Because of our assumption l > k. Suppose for some vi ,
1 ≤ i ≤ k, N (vi ) ∩ C = ∅. Then we can obtain a t-vertex cover C  = C − {vl } + {vi }
of size at most k and covering at least t edges as deg(vi ) ≥ deg(vl ). So we now as-
sume that for each vi , 1 ≤ i ≤ k, N (vi ) ∩ C = ∅. Let Bi = N (vi ) ∩ C. Observe that
for each i, Bi does not contain vl otherwise that will imply v0 , vi , vl is a triangle.
Suppose for some i = j , u ∈ Bi ∩ Bj then v0 , vi , u, vj is a cycle of length 4. Hence
Bi ∩ Bj = ∅ for all i, j such that i = j . So this implies that


k
|Bi | ≥ k.
i=1

So we have Bi = ∅, Bi ⊆ C − {vl } and their pairwise intersections are empty. But this
implies


k
|Bi | ≤ |C − {vl }| ≤ k − 1
i=1

which contradicts that ki=1 |Bi | ≥ k. This in turn proves the claim.
Since we branch on the vertices of A whose size is bounded by k + 1, we get an
algorithm of time complexity O((k + 1)k n). 

Since the runtime in Theorem 12 was independent of t, we get

Theorem 13 (m − t)-V ERTEX C OVER can be solved in O((k + 1)k (n + m)) time
for G5 graphs when parameterized by k only.

By arguments similar to those used in Theorem 12, we can show the following.

Theorem 14 t-D OMINATING S ET can be solved in O((k + 1)k nO(1) ) time for G5
graphs when parameterized by k only.
218 Algorithmica (2008) 52: 203–225

5 I NDEPENDENT S ET and Its Variants in G4 Graphs

I NDEPENDENT S ET problem asks for an induced subgraph on k vertices which only

contains isolated vertices. More precisely:
I NDEPENDENT S ET: Given a graph G = (V , E) and an integer k ≥ 0, deter-
mine whether there exists a set of at most k vertices I ⊆ V such that the sub-
graph induced by I does not contain any edges.
I NDEPENDENT S ET problem is W [1]-complete for general graphs. We show that the
I NDEPENDENT S ET and some of its variants are fixed parameter tractable for triangle
free graphs. We use Ramsey theory to get a kernel of size O(k 2 ) for these problems.

Theorem 15 Parameterized I NDEPENDENT S ET problem can be solved in O(kn +

k O(k) ) in G4 graphs (triangle free graphs).

Proof Given any two integers p and q, there exists a number R(p, q) such that any
graph on at least R(p, q) vertices contains an independent set of size p or a clique
of size q. R(p, q), for various values of p and q are known as Ramsey Numbers.
It is well known that R(p, q) ≤ p+q−2 q−1 [18]. And if n > R(p, q) then either an
independent set of size p or a clique of size q can be found in O((p + q)n) time by
transforming the inductive arguments used in the proof of Theorem 27.3 in [18] for
the upper bound of R(p, q) to a constructive algorithm.
If k ≤ 2, then we can check in linear time whether the graph has an independent
set of size 2 or not. So let us assume that k ≥ 3. If the number of vertices n > k 2 ≥
R(k, 3) then we know that this graph has either an independent set of size k or a
clique of size 3. But since the input graph is triangle free, we know that it must have
an independent set of size k and can be found in O(kn) time. Otherwise we know
that n ≤ k 2 . In this case, we try all possible subsets of size at most k to see whether
the graph has an independent set of size k or not. If any of them does, then we answer
YES and answer NO otherwise. This will take O(k O(k) ) time. This completes the
proof. 

Theorem 15 can be extended to a larger class of problems where one is interested

in finding a subset inducing a “hereditary property”. A graph property Π is a col-
lection of graphs. A graph property Π is non-trivial if Π has at least one graph and
does not include all graphs. A non-trivial property is said to be hereditary if a graph
G is in property Π implies that every induced subgraph of G is also in Π . Given any
property Π , let P (G, k, Π) be the problem defined below:
P (G, k, Π ): Given a graph G = (V , E) and a positive integer k, determine
whether there exists a set of k vertices V  ⊆ V such that G[V  ] is in Π .
Khot and Raman [19] studied this problem and showed the following theorem.

Theorem 16 (Khot and Raman [19]) Let Π be a hereditary property that includes
all independent sets but not all cliques (or vice versa). Then the problem P (G, k, Π)
is W [1] hard.
Algorithmica (2008) 52: 203–225 219

The proof of the following theorem is exactly as in the proof of Theorem 15, by
considering the Ramsey numbers R(k, c).

Theorem 17 Let Π be a hereditary property that includes all independent sets. Then
the problem P (G, k, Π) restricted to Gc graphs for any fixed constant c ≥ 3 is fixed
parameter tractable and can be solved in O(kn + k O(k) nO(1) ) time.

Given a graph G = (V , E) and a positive integer k ≥ 0, ACYCLIC S UBGRAPH,

B IPARTITE S UBGRAPH and P LANAR S UBGRAPH problems ask whether there exists
a subset V  ⊆ V , such that |V  | ≥ k and G[V  ] is acyclic, bipartite or planar respec-
tively. All these problems are known to be W [1]-hard [7, 19] in general graphs. As a
corollary to Theorem 17 we have following:

Corollary 5 ACYCLIC , B IPARTITE and P LANAR S UBGRAPH problems are fixed

parameter tractable with time complexity O(kn + k O(k) nO(1) ) for Gc graphs for any
fixed constant c ≥ 3.

Corollary 5 shows that ACYCLIC and P LANAR S UBGRAPH problems are fixed
parameter tractable for bipartite graphs. In fact we can easily obtain much improved
FPT algorithms for these problems for bipartite graphs. Observe that a bipartite graph
has an independent set (and hence planar or acyclic induced subgraph) on n/2 ver-
tices. So, if k ≤ n/2 then for both these problems the answer is YES and otherwise
k > n/2 or n < 2k and hence we get a kernel of size at most 2k for both the ACYCLIC
and P LANAR S UBGRAPH problems for bipartite graphs. Now we check all k sized
subsets of the vertex set to see
 whether the subset induces an acyclic subgraph or
planar subgraph. Since nk ≤ 2k k ≤ 2 2k = 4k , we get an O(4k nO(1) ) time algorithm

for both these problems for bipartite graphs.

Minimum feedback vertex set, which is a subset of vertices whose removal makes
the graph acyclic, is a complement of the vertex set of the maximum ACYCLIC S UB -
GRAPH problem. Fomin et al. [15] have shown that the minimum feedback vertex set
can be found in O(1.7548n ) time in undirected graphs. So together with this result
and the kernel of size 2k we get O(1.75482k nO(1) ) = O(3.0793k nO(1) ) time algo-
rithm for the ACYCLIC S UBGRAPH problem. Putting together everything we get the
following theorem.

Theorem 18 The parameterized ACYCLIC S UBGRAPH and P LANAR S UBGRAPH

problems can be solved in O(3.08k k O(1) + nO(1) ) and O(4k k O(1) + nO(1) ) time,
respectively, for bipartite graphs.

Another problem which can be shown to be FPT for Gc graphs for any fixed
constant c ≥ 3 is the I RREDUNDANT S ET problem, which is known to be W [1]-
complete [9] in general graphs.
I RREDUNDANT S ET: Given a graph G = (V , E) and a positive integer k. Is
there a set V  ⊆ V of cardinality at least k having the property that each vertex
u ∈ V  has a private neighbor? A private neighbor of a vertex u ∈ V  is a vertex
u ∈ N [u] (possibly u = u) with the property that for every vertex v ∈ V  \ {u},
u ∈
/ N[v].
220 Algorithmica (2008) 52: 203–225

This follows from a simple observation that every independent set is also an irredun-
dant set. Then the following theorem can be proved on the lines of Theorem 15, by
considering the Ramsey Numbers R(k, c).

Theorem 19 I RREDUNDANT S ET is FPT for Gc graphs for any fixed constant c ≥ 3.

6 Is Everything Easy on Graphs with no Small Cycles?

In contrast to the results presented in the previous sections, here we show a problem
to be W [1]-hard even in bipartite graphs with girth at least 6 (G6 graphs). Observe
that in graphs with large girth the C LIQUE problem is trivial. We look at D ENSE
S UBGRAPH problem [20] which is a generalization of the C LIQUE problem.
D ENSE S UBGRAPH: Given a graph G = (V , E) and positive integers k and l,
determine whether there exists a set of at most k vertices C ⊆ V such that G[C]
has at least l edges,
  i.e. the induced subgraph on C has at least l edges. (Note
that l is at most k2 .)
It is easy to observe that D ENSE S UBGRAPH problem is W [1]-hard when parameter-
ized by k, by a simple reduction from C LIQUE. But we give a reduction from C LIQUE
to D ENSE S UBGRAPH problem parameterized by k which shows that the problem is
W [1]-hard even in bipartite graphs with girth at least 6.

Theorem 20 D ENSE S UBGRAPH is W [1]-hard for bipartite graphs with girth at

least 6 when parameterized by k.

Proof We give a reduction from C LIQUE. Let (G, k) be an instance of C LIQUE with
k ≥ 3. We make the graph G = (V , E) bipartite by subdividing every edge. Let G =
(V  , E  ) be the resulting subgraph. Here, V  = V ∪ W where W = {wuv | (u, v) ∈ E}
and E  , the   consists of (u, wuv ) and (v, wuv ) for every wuv ∈ W . Take
 set of edges,
k  = k + k2 and l = 2 k2 .
Observe that G is a bipartite graph as every cycle is of even length and the girth
is at least 6 as the girth of G is at least 3. We claim that G has a clique of size k
if and only if G has a subgraph on k  vertices with at least l edges. Also note that
every vertex in W has degree 2 as they represent edges in the original graph. Now
suppose G has a clique of size k on vertex set C = {v1 , v2 , . . . , vk }. Then C  = C ∪
{wuv | u, v ∈ C} is a vertex
 set of dense subgraph in G having k  vertices and l edges
as G[C] has at least k2 edges.
Conversely, let C  be a set of k  vertices such that G [C  ] has at least l edges. Let
O = V ∩ C  . Clearly G [C  ] is bipartite with O and N = C  − O as the two parts of
the vertex set, and every
 vertex in N has degree at most 2. Since the number of edges 
in G [C  ] = l = 2 k2 , and since every vertex in N has degree at most 2, |N | ≥ k2
and hence |O| ≤ k. Let t = |O|. We claim that t = k. Suppose not. Then t ≤ k − 1.
Also, since k ≥ 3, t ≥ 1. Let n1 and n2 be the degree 1 and degree 2 vertices in N
respectively. Since G has no multiple edges, no pair of vertices in N with degree 2
Algorithmica (2008) 52: 203–225 221
t 
can be adjacent to the same pair of vertices in O and hence n2 ≤ 2 . Then the number
of edges in G[C  ] is:
 
k
2 ≤ |E(G[C  ])| = 2n2 + n1
2
= k  − t + n2
 
k
=k+ − t + n2
2
      
k t t
≤k+ −t + since n2 ≤ .
2 2 2

From the above it implies that

   
k t
t+ ≤k+ . (1)
2 2

If t = 1 then
   
1 k
k+ =k<1+ ,
2 2
a contradiction to inequality (1). So let 2 ≤ t ≤ k − 1. But then
       
t k−1 k k
k+ ≤k+ = +1< + t,
2 2 2 2

again a contradiction
 to inequality (1). This implies that |O| = k. As a result of this,
|N| = k2 and every vertex in N has degree 2. Every vertex of degree 2 in N repre-
sents an edge in G[O]. This shows that the vertices of O form a clique in the original
graph. 

7 Approximation of D OMINATING S ET

In this section we give some results concerning approximation of the D OMINATING

S ET problem for bipartite and G5 graphs. We refer to [24] for all the basic definitions
regarding approximation algorithms.
Feige [12] showed that (1 − o(1)) ln n is a threshold below which the D OMINAT-
ING S ET problem cannot be approximated efficiently unless NP has slightly super-
polynomial time algorithm. Here, ln n represents natural logarithm. Under the same
ln n
hypothesis (1−o(1))
2 is a threshold below which the D OMINATING S ET problem
can not be approximated for bipartite graphs. This result follows from the reduction
in Theorem 1. Towards this end, we just show that if we have a factor α approxima-
tion algorithm for the dominating set problem in bipartite graphs then it implies 2α
factor approximation algorithm for the dominating set problem in general undirected
graphs. Given a graph G, we apply Theorem 1 to obtain the bipartite graph H and
apply the factor α approximation algorithm for dominating set problem in bipartite
222 Algorithmica (2008) 52: 203–225

graphs to get a dominating set D for H . We obtain a dominating set D  for G from
the dominating set D for H as in the proof of Theorem 1. Let OPTG denote the size
of an optimum dominating set for the graph G. Now note that

|D  | < |D|
≤ α · OPTH
≤ α · (OPTH − 1) + α
≤ α · OPTG + α · OPTG (since OPTH − 1 = OPTG )
= (2α) · OPTG .

Furthermore the result of Feige [12] together with Theorem 2 imply that the ap-
proximability of D OMINATING S ET problem has the same threshold of (1 − o(1)) ln n
even for split graphs. The above discussion results in the following theorem.

Theorem 21 D OMINATING S ET problem can not be approximated efficiently below

(1 − o(1)) ln n in bipartite and split graphs unless NP ⊂ DTIME(nO(log log n) ).

An approximation algorithm of factor O(log n) is known for the D OMINATING

S ET problem using the reduction to the S ET C OVER problem (see discussion before
Theorem 8 in Sect. 3) and the following proposition.

Proposition 1 ([17, 21]) Let (U, S) be a set cover instance such that |U
 | = n. Then
we can find a set cover S  ⊆ S of size at most Hn · (OPT) where Hn = ni=1 1/i and
OPT is the size of the optimum solution of the set cover instance Hn ≤ ln n + 1.

Here we outline a slightly improved approximation algorithm for D OMINATING

S ET problem in G5 graphs. This approximation algorithm has a factor O(log l) where
l is the size of the optimum dominating set. The idea of the algorithm is to use the
reduction rules developed in Sect. 2.2 and obtain an instance of size O(l 3 ) with the
property that maximum degree of the graph is bounded by l and then use the follow-
ing proposition on the corresponding set cover instance of the problem.

Proposition 2 ([10]) Let (U, S) be a set cover instance such that |U | = n and the
size of each set Si ∈ S is bounded by q, that is |Si | ≤ q. Then
qwe can find a set cover
S  ⊆ S of size at most (Hq − 1/2) · (OPT) where Hq = i=1 1/i and OPT is the
size of the optimum solution of the set cover instance.

Observe that the reduction rules (R1)–(R4) depend on k whereas here we have an
optimization problem. Hence apply reduction rules for all values for k between 1 and
n and if the reduced instance as viewed as the S ET C OVER problem instance satisfies
the hypothesis of Proposition 2 then we obtain a dominating set for G by applying
Proposition 2. Finally we return the dominating set of smallest size among the ones
obtained for different k. Our detailed algorithm is described below. We outline our
algorithm in terms of rwb-graphs described in Sect. 2.2.
Algorithmica (2008) 52: 203–225 223

Algo-Dom-SET(G = (V , E))
(Input: A G5 graph. Output: A dominating set of G.)
Step 1: Given an undirected graph G = (V , E). Make it a rwb-graph by coloring all
vertices of V black; that is R = ∅, W = ∅ and B = V . I = ∅.
Step 2: For (j = 1 to n) do as follows:
Step 2a: Apply reduction rules (R1)–(R4) on (G = (R ∪ W ∪ B, E), j ) until no
longer possible and obtain an instance (Gj = (R j ∪ W j ∪ B j , E j ), j − |R j |).
Step 2b: If (|W j | + |B j | ≤ 2j 3 ) and the maximum degree of Gj is at most j then

I = I ∪ {(Gj = (R j ∪ W j ∪ B j , E j ), j − |R j |)}.

(In this step we obtain a set of instances which could possibly lead to an optimum
dominating set. So we have

I = {(Gk = (R k ∪ W k ∪ B k , E k ), k − |R k |) | |W k | + |B k | ≤ 2k 3
and maximum degree of Gk is at most k}.)

Step 3: We obtain a set cover instance (Uk , Sk ) from the reduced graph Gk by taking
U = B k and having sets Su for u ∈ (W k ∪ B k ). Su = N (u) ∩ B k if u ∈ W k and
Su = N[u] ∩ B k if u ∈ B k . Obtain P, the set of instances for the set cover problem,
by changing every instance in I to the set cover instance. That is:

P = {(Uk , Sk ) | (Gk = (R k ∪ W k ∪ B k , E k ), k − |R k |) ∈ I}.

Step 4: Apply Proposition 2 to every instance of the set cover problem in P and
obtain the following set of solutions

SOL = {Sk | Sk ⊆ Sk , (Uk , Sk ) ∈ P}.

Let V(Sk ) represent the set of vertices in Gk corresponding to the sets in the collec-
tion Sk . Obtain the following set

DOM = {V(Sk ) ∪ Rk | Sk ∈ SOL & R k the red vertices of Gk }

of possible dominating sets for G and return the one with the minimum size in
DOM as a dominating set for G.

Theorem 22 Let G = (V , E) be a G5 graph on n vertices. Then the algorithm

Algo-Dom-SET outputs  a dominating set of size at most (Hp+1 − 1/2) · p in poly-
p
nomial time where Hp = i=1 1/i and p is the size of the optimum solution of a
dominating set of G. That is, Algo-Dom-SET is an approximation algorithm with
performance ratio of ln(p + 2) + 1/2 for the dominating set problem for G5 graphs.

Proof It is clear that the algorithm Algo-Dom-SET takes polynomial time. Propo-
sition 2 ensures that the algorithm returns a dominating set for G. Now we show that
the algorithm is a factor of Hp+1 − 1/2 approximation algorithm for the dominating
set problem for G5 graphs which will complete the proof of the theorem.
224 Algorithmica (2008) 52: 203–225

Let l be the smallest positive integer in Step 2 of the algorithm such that (Gl =
(R l ∪ W l ∪ B l , E l ), l − |R l |) ∈ I. The reduction rules ensures that (G = (R ∪ W ∪
B, E), k) is a no instance for 1 ≤ k ≤ l − 1 and hence we have p ≥ l.
Consider the instance (Gp = (R p ∪ W p ∪ B p , E p ), p − |R p |) ∈ I. Observe that
the instance Gp has an optimum dominating set of size p − |R p | and the maximum
degree of the graph is bounded by p. When we apply the factor (Hq − 1/2) set cover
approximation algorithm in Step 4 on the instance (Up , Sp ), where each set in Sp
is bounded by p + 1, we obtain Sp ⊆ Sp of size at most |Sp | ≤ (Hp+1 − 1/2) ×
(p − |R p |). Now the size of the dominating set Rp ∪ V(Sp ) corresponding to this
instance for G is :

|Rp | + |V(Sp )| = |Rp | + |Sp |

≤ |Rp | + (Hp+1 − 1/2)(p − |R p |)
≤ |Rp |(Hp+1 − 1/2) + (Hp+1 − 1/2)(p − |R p |)
= (Hp+1 − 1/2)p.

Since we return a dominating set of minimum size among the sets in DOM as a
dominating set for G it is clear that its size is also bounded by (Hp+1 − 1/2)p. This
completes the proof. 

8 Conclusion and Discussions

In this paper we showed that if the input graphs do not possess short cycles then the
neighborhood problems such as D OMINATING S ET, I NDEPENDENT S ET and several
of their variants are fixed parameter tractable. We have also shown that the restriction
on girth is optimal if we do not put further restriction on the graph classes. This is the
first time, to our knowledge, that the parameterized complexity of graph problems are
classified by girth.
Most of the algorithms given here are just parameterized complexity classification
algorithms. We believe that more efficient FPT algorithms should be possible. Ob-
taining a O(ck nO(1) ), c a constant, algorithm for all these problems remains an open
problem.
We also gave an improved approximation algorithm for D OMINATING S ET prob-
lem in graphs with girth at least 5. It would be interesting to explore the possibility
of improved approximation algorithms for other problems on graphs with no small
cycles.
Furthermore, it is worth exploring excluding structures as subgraphs other than
cycles to see whether some W -hard problems become FPT.

Acknowledgements We thank the referees for several useful comments. We would also like to thank
T. Erlebach and R.E. Tarjan for suggesting an investigation of approximation algorithms for the D OMI -
NATING S ET problem for graphs with no small cycles.
Algorithmica (2008) 52: 203–225 225

References

1. Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial time data reduction for dominating set. J. ACM
51(3), 363–384 (2004)
2. Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: A refined
search tree technique for dominating set on planar graphs. J. Comput. Syst. Sci. 71, 385–405 (2005)
3. Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set
problem. Discrete Appl. Math. 132(1–3), 17–26 (2003)
4. Alekseev, V.E., Korobitsyn, D.V., Lozin, V.V.: Boundary classes of graphs for the dominating set
problem. Discrete Math. 285(1–3), 1–6 (2004)
5. Bläser, M.: Computing small partial coverings. Inf. Process. Lett. 85(6), 327–331 (2003)
6. Downey, R.G., Fellows, M.R.: Threshold dominating sets and an improved characterization of W [2].
Theor. Comput. Sci. 209(1–2), 123–140 (1998)
7. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
8. Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parametrized complexity of some funda-
mental problems in coding theory. SIAM J. Comput. 29(2), 545–570 (1999)
9. Downey, R.G., Fellows, M.R., Raman, V.: The complexity of irredundant sets parameterized by size.
Discrete Appl. Math. 100(3), 155–167 (2000)
10. Duh, R., Fürer, M.: Approximation of k-set cover by semi-local optimization. In: Proceedings of the
29th Annual ACM Symposium on Theory of Computing (STOC), pp. 256–264 (1997)
11. Edmonds, J.: Paths, trees and flowers. Can. J. Math. 17, 449–467 (1965)
12. Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)
13. Fernau, H.: Parameterized algorithms: a graph-theoretic approach. Habilitationsschrift, Universität
Tübingen, Tübingen, Germany (2005)
14. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
15. Fomin, F.V., Gaspers, S., Pyatkin, A.V.: Finding a minimum feedback vertex set in time O(1.7548n ).
In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IW-
PEC). Lecture Notes in Computer Science, vol. 4169, pp. 184–191. Springer, Berlin (2006)
16. Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of generalized vertex cover prob-
lems. In: Proceeding of the 9th International Workshop Algorithms and Data Structures (WADS).
Lecture Notes in Computer Science, vol. 3608, pp. 36–48. Springer, Berlin (2005)
17. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3),
256–278 (1974)
18. Jukna, S.: Extremal Combinatorics. Springer, Berlin (2001)
19. Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theor.
Comput. Sci. 289(2), 997–1008 (2002)
20. Kortsarz, G., Peleg, D.: On choosing a dense subgraph. In: Proceeding of the 34th Annual Symposium
on Foundations of Computer Science (FOCS), pp. 692–701 (1993)
21. Lovàsz, L.: On the ratio of optimal fractional and integral covers. Discrete Math. 13, 383–390 (1975)
22. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics
and Its Applications. Oxford University Press, London (2006)
23. Raman, V., Saurabh, S.: Triangles, 4-cycles and parameterized (in-)tractability. In: Proceeding of the
10th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol.
4059, pp. 304–315. Springer, Berlin (2006)
24. Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)