A11 Philip PDF

11
Polynomial Kernels for Dominating Set in Graphs of

Bounded Degeneracy and Beyond
GEEVARGHESE PHILIP and VENKATESH RAMAN, The Institute of Mathematical Sciences,
Chennai, India
SOMNATH SIKDAR, RWTH Aachen University, Aachen, Germany
We show that for every fixed j ≥ i ≥ 1, the k-DOMINATING SET problem restricted to graphs that do not have
Ki, j (the complete bipartite graph on (i + j) vertices, where the two parts have i and j vertices, respectively)
as a subgraph is fixed parameter tractable (FPT) and has a polynomial kernel. We describe a polynomial-time
algorithm that, given a Ki, j -free graph G and a nonnegative integer k, constructs a graph H (the “kernel”)
and an integer k′ such that (1) G has a dominating set of size at most k if and only if H has a dominating set
2 2
of size at most k′ , (2) H has O(( j + 1)i+1 ki ) vertices, and (3) k′ = O(( j + 1)i+1 ki ).
Since d-degenerate graphs do not have Kd+1,d+1 as a subgraph, this immediately yields a polynomial
2
kernel on O((d + 2)d+2 k(d+1) ) vertices for the k-DOMINATING SET problem on d-degenerate graphs, solving an
open problem posed by Alon and Gutner [Alon and Gutner 2008; Gutner 2009].
The most general class of graphs for which a polynomial kernel was previously known for k-DOMINATING SET
is the class of Kh-topological-minor-free graphs [Gutner 2009]. Graphs of bounded degeneracy are the most
general class of graphs for which an FPT algorithm was previously known for this problem. Kh-topological-
minor-free graphs are Ki, j -free for suitable values of i, j (but not vice-versa), and so our results show that
k-DOMINATING SET has both FPT algorithms and polynomial ! " kernels in strictly more general classes of graphs.
Using the same techniques, we also obtain an O jki vertex-kernel for the k-INDEPENDENT DOMINATING SET
problem on Ki, j -free graphs.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnu-
merical Algorithms and Problems—Computations on discrete structures; G.2.1 [Discrete Mathematics]:
Combinatorics—Combinatorial algorithms; G.2.2 [Discrete Mathematics]: Graph Theory—Graph algo-
rithms
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Degenerate graphs, dominating set, fixed parameter tractability,
kernelization
A preliminary version of this article appeared as “Solving dominating set in larger classes of graphs: FPT
algorithms and polnominal kernels” in Proceedings of the 17th Annual Eueopean Symposium on Algorithms
(ESA 2009), Lecture Notes in Computer Science, vol. 5757, Springer, 694–705.
c
⃝2012 Association for Computing Machinery, ACM acknowledges that this contribution was co-authored
by an affiliate of The Institute of Mathematical Sciences, Chennai, India. As such, the Government of India
retains an equal interest in the copyright. Reprint requests should be forwarded to ACM, and reprints must
include clear attribution to ACM and The Institute of Mathematical Sciences, Chennai, India.
Authors’ present addresses: G. Philip and V. Raman, The Institute of Mathematical Sciences, C I T Cam-
pus, Taramani, Chennai 600 113, India; email: {gphilip, vraman}@imsc.res.in; S. Sikdar, Theoretical Com-
puter Science, Department of Computer Science, RWTH Aachen University, 52056 Aachen, Germany; email:
[email protected].
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted
without fee provided that copies are not made or distributed for profit or commercial advantage and that
copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for
components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.
To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this
work in other works requires prior specific permission and/or a fee. Permissions may be requested from
Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212)
869-0481, or [email protected].
⃝c 2012 ACM 1549-6325/2012/12-ART11 $15.00
DOI 10.1145/2390176.2390187 http://doi.acm.org/10.1145/2390176.2390187
ACM Transactions on Algorithms, Vol. 9, No. 1, Article 11, Publication date: December 2012.
11:2 G. Philip et al.
ACM Reference Format:

Philip, G., Raman, V., and Sikdar, S. 2012. Polynomial kernels for dominating set in graphs of bounded
degeneracy and beyond. ACM Trans. Algor. 9, 1, Article 11 (December 2012), 23 pages.
DOI = 10.1145/2390176.2390187 http://doi.acm.org/10.1145/2390176.2390187
1. INTRODUCTION
A dominating set of a graph G = (V, E) is a set S ⊆ V of vertices of G such that every
vertex in V \ S is adjacent to some vertex in S. The DOMINATING SET problem is defined
as follows.
DOMINATING SET
Input: A graph G = (V, E) and a nonnegative integer k.
Question: Does G have a dominating set with at most k vertices?
The DOMINATING SET problem is NP-hard, even in very restricted graph classes such as
the class of planar graphs with maximum degree 3 [Garey and Johnson 1979]. Hence,
unless P = NP, there is no polynomial-time algorithm that solves the problem even in
such restricted graph classes.
Parameterized algorithms [Downey and Fellows 1999; Flum and Grohe 2006;
Niedermeier 2006] constitute one approach towards solving NP-hard problems in “fea-
sible” time. Each parameterized problem comes with an associated parameter, which is
usually a nonnegative integer, and the goal is to find algorithms that solve the problem
in polynomial time when the parameter is fixed, where the degree of the polynomial is
independent of the parameter. More precisely, if k is the parameter and n the size of the
input, then the goal is to obtain an algorithm that solves the problem in time f (k) · nc
where f is some computable function and c is a constant independent of k. Such an
algorithm is called a fixed-parameter-tractable (FPT) algorithm, and the class of all
parameterized problems that have FPT algorithms is called FPT; a parameterized
problem that has a fixed-parameter-tractable algorithm is said to be (in) FPT.
Together with this revised notion of tractability, parameterized complexity theory
offers a corresponding notion of intractability as well, captured by the concept of W-
hardness. In brief, the theory defines a hierarchy of complexity classes FPT ⊂ W[1] ⊂
W[2] ⊂ · · · ⊂ XP, where each inclusion is believed to be strict—on the basis of evidence
similar in spirit to the evidence for believing that P ̸= NP—and XP is the class of
all parameterized problems that can be solved in O(n f (k) ) time where n is the input
size, k the parameter, and f is some computable function [Downey and Fellows 1999;
Niedermeier 2006].
One natural parameter for the DOMINATING SET problem is k, the size of the solution
being sought. A natural parameterized version of the DOMINATING SET problem is thus
the k-DOMINATING SET problem, defined as follows.
k-DOMINATING SET
Input: A graph G = (V, E), and a non-negative integer k.
Parameter: k
Question: Does G have a dominating set with at most k vertices?
It turns out that the DOMINATING SET problem, with this parameterization, is still hard
to solve. More precisely, k-DOMINATING SET is the canonical W[2]-hard problem [Downey
and Fellows 1999], and the problem remains W[2]-hard even in many restricted classes
of graphs—for example, it is W[2]-hard in classes of graphs with bounded average
degree [Golovach and Villanger 2008]. Thus there is no FPT algorithm that solves the
Polynomial Kernels for Dominating Set in Graphs of Bounded Degeneracy and Beyond 11:3
problem, even when restricted to graphs of bounded average degree, unless FPT =
W[2], which is considered unlikely.
The problem does have FPT algorithms in certain restricted families of graphs, such
as in planar graphs [Fomin and Thilikos 2006], graphs of bounded genus [Ellis et al.
2004], nowhere-dense classes of graphs [Dawar and Kreutzer 2009], Kh-topological-
minor-free graphs, and graphs of bounded degeneracy [Alon and Gutner 2009]. Further,
the problem √
has a subexponential FPT algorithm—which has a running time of the
form O(2 O( k) · nc )—in H-minor-free graphs [Demaine et al. 2005]. To the best of our
knowledge, graphs of bounded degeneracy are the most general graph class previously
known to have an FPT algorithm for this problem. In this article, we show that the
problem has an FPT algorithm in a class of graphs that encompasses, and is strictly
larger than, all the aforementioned classes—namely, the class of Ki, j -free graphs.
Closely related to the notion of an FPT algorithm is the concept of a kernel for a
parameterized problem. We say that two instances of a decision problem are equivalent
if and only if they are either both yes-instances or both no-instances. A kernelization
algorithm for a parameterized problem is a polynomial-time algorithm that converts
an instance (x, k) of the problem to an equivalent instance (y, k′ ) whose size |y| and
parameter k′ are both bounded by functions of the original parameter k. The instance y
output by the algorithm is said to be a kernel for the problem. It is not difficult to see that
if a problem has a kernelization algorithm, then the problem is FPT. Somewhat more
surprisingly, the converse is also true: A folklore theorem of parameterized complexity
states that a parameterized problem has a kernelization algorithm if and only if it has
an FPT algorithm [Downey and Fellows 1999].
For the k-DOMINATING SET problem, a kernelization algorithm is thus an algorithm
that takes (G, k) as input, runs in polynomial time, and outputs an equivalent instance
(H, k′ ), where k′ ≤ g(k) and H is a graph with at most h(k) vertices for some computable
functions g and h. H is the kernel output by this algorithm. From the equivalence of
FPT and kernelization mentioned previously it follows that, unless FPT = W[2], there
is no kernelization algorithm for k-DOMINATING SET on general graphs or on graphs with
a bounded average degree. For the same reason, the problem admits kernelization
algorithms when the input is restricted to planar graphs, graphs of bounded genus,
Kh-topological-minor-free graphs, and graphs of bounded degeneracy. However, the size
of the kernel implied by the proof of the folklore theorem is equal to the factor f (k) in
the running time of the corresponding FPT algorithm, and hence is exponential in k.
The interesting problem is, therefore, to find if the kernel size can be made smaller—in
particular, whether it can be made polynomial in k.
Proving polynomial bounds on the size of the kernel for different parameterized
problems has been a significant practical aspect in the study of the parameterized
complexity of NP-hard problems, and many positive results are known; see the survey
on kernelization results by Guo and Niedermeier [2007].
For the k-DOMINATING SET problem, the first polynomial kernel result was obtained
by Alber et al. [2004]: they showed that in planar graphs, the problem has a linear
kernel on at most 335k vertices. A linear kernel for a parameterized problem is one
whose size is a linear function of the parameter k. This bound for planar graphs was
later improved to 67k by Chen et al. [2007]. Fomin and Thilikos [2004] showed that
the same reduction rules as used by Alber et al. [2004] give a linear kernel (linear
in k + g) for k-DOMINATING SET restricted to graphs of genus g. The next advances in
kernelizing this problem were made by Alon and Gutner [2008] and Gutner [2009].
They showed that the problem has a linear kernel in K3,h-topological-minor-free graph
classes (which include, e.g., planar graphs), and a polynomial kernel in Kh-topological-
minor-free graph classes. Here Kh denotes the complete graph on h vertices, and K3,h
is the complete bipartite graph on h + 3 vertices where one piece of the partition has 3
Table I. Some FPT and kernelization results for k-DOMINATING SET

Graph Class FPT Algorithm Running Time Kernel Size
√
Planar O(k4 + 215.13 kk + n3 ) O(k)
[Fomin and Thilikos 2006] [Alber et al. 2004; Chen et al. 2007]
Genus-g O((24g2 + 24g + 1)kn2 ) O(k + g)
[Ellis et al. 2004] [Fomin and Thilikos 2004]
√
Kh-minor-free O(n3.5 + 2 O( k) ) O(kc )
[Gutner 2009] [Gutner 2009]
Kh-topological-minor-free (O(h))hk · n O(kc )
[Alon and Gutner 2009] [Gutner 2009]
d-degenerate kO(dk) n kO(dk) [Alon and Gutner 2009],
2
[Alon and Gutner 2009] O(k2(d+1) )†
2i 2 ) 2
Ki, j -free O(ni+O(1) + 2 O(k )† O(k2i )†
Note: Results obtained in this article are marked with a †.
vertices and the other has h. The degree of the polynomial bound on the kernel size for
Kh-topological-minor-free graphs depends on h, and these are the most general class of
graphs for which the problem has been previously shown to have a polynomial kernel.
In the meantime, the same authors had shown [Alon and Gutner 2009] that the problem
is FPT in (the strictly larger class of) graphs of bounded degeneracy, but had left open
the question whether the problem has a polynomial kernel in such graph classes. In
this article, we answer this question in the affirmative, and show that, in fact, even
larger classes of graphs—the Ki, j -free graph classes—admit polynomial kernels for this
problem. More recently, Bodlaender et al. [2009b] and Fomin et al. [2010] have obtained
general results which imply, inter alia, linear kernels for k-DOMINATING SET in graphs of
bounded genus and in apex-minor-free graphs (which are classes of graphs that exclude
special graphs—called apex graphs—as a minor). In Table I, we summarize some FPT
and kernelization results for the k-DOMINATING SET problem on various classes of graphs.
Our Results. Ki, j denotes the complete bipartite graph on i + j vertices where one
piece of the partition has i vertices and the other part has j. A graph is said to be
Ki, j -free if it does not contain Ki, j as a (not necessarily induced) subgraph. We show
that for every fixed i, j ≥ 1, the k-DOMINATING SET problem has a polynomial kernel on
Ki, j -free graphs. For input graph G and parameter k, the size of the kernel is bounded
by kc where c is a constant that depends only on i and j.
A graph G is said to be d-degenerate if every subgraph of G has a vertex of degree
at most d. Since a d-degenerate graph does not have Kd+1,d+1 as a subgraph, it follows
that the k-DOMINATING SET problem has a polynomial kernel on graphs of bounded
degeneracy. This settles a question posed by Alon and Gutner [2008] (see also Gutner
[2009].).
A subset S of the vertex set of a graph is said to be independent if no two vertices in S
have an edge between them in the graph. The k-INDEPENDENT DOMINATING SET problem
asks whether the input graph G has an independent DOMINATING SET of size at most k,
with the parameter being k. We show that the k-INDEPENDENT DOMINATING SET problem
has a polynomial kernel in Ki, j -free graphs.
Note that the first three graph classes in Table I are minor-closed (See, e.g., Diestel
[2005, Chapter 12], for the definition of a minor-closed graph class.). This seems to be
indicative of the state of the art—the only other previous FPT or kernelization result
for the k-DOMINATING SET problem on a non-minor-closed class of graphs that we are
aware of is the O(k3 ) kernel and the resulting FPT algorithm for graphs that exclude
triangles and 4-cycles [Raman and Saurabh 2008]. In fact, this result can be modified
to obtain similar bounds on graphs with no 4-cycles (allowing triangles). Since a 4-cycle
is a K2,2 , this result follows from the main result of this paper by setting i = j = 2.
Since, for a constant h, a Kh-topological-minor-free graph has bounded degener-
acy [Bollobás and Thomason 1998; Gutner 2009; Komlós and Szemerédi 1996], the class
of Ki, j -free graphs is more general than the class of Kh-topological-minor-free graphs.
Thus, we extend the class of graphs for which the k-DOMINATING SET problem is known
to have (1) FPT algorithms and (2) polynomial kernels, to the class of Ki, j -free graphs.
It is interesting to note that except for Ki, j -free graphs, all the other graph classes in
Table I are of bounded degeneracy, and are hence sparse: any d-degenerate graph on
n vertices has at most dn edges. In contrast, Ki, j -free graphs can, in general, have a
superlinear number of edges; for example, Alon et al. [1999] show that for sufficiently
large i and j > (i − 1)!, there exist Ki, j -free graphs on n vertices with !(n2−1/i ) edges.
Organization of the Rest of the Article. In Section 2, we present our main kerneliza-
tion algorithm that, for fixed j ≥ i ≥ 2, runs in O(ni ) time1 and constructs a kernel
2
on O(( j + 1)i+1 ki ) vertices for k-DOMINATING SET on Ki, j -free graphs. As a corollary we
obtain, in Section 3, a polynomial kernel for the problem restricted to d-degenerate
graphs, where the kernelization algorithm runs in time O(nd+1 ) and outputs a kernel
2
of size O((d+ 2)d+3 k(d+1) ). In Section 3.1, we describe an improvement to this algorithm
that applies to d-degenerate input graphs, yields a kernel of the same size as above,
and runs in time O(2ddn2 ). In Section 4, we describe a modification of the algorithm
in Section 2 that constructs a polynomial kernel for the k-INDEPENDENT DOMINATING SET
problem on Ki, j -free graphs. This kernel has O( jki ) vertices, and so implies a kernel of
size O((d + 1)2 kd+1 ) for this problem on d-degenerate graphs. In Section 5, we state our
conclusions and list some open problems.
Notation. All the graphs in this article are finite, undirected and simple. In general,
we follow the graph terminology of Diestel [2005]. We let V (G) and E(G) denote, re-
spectively, the vertex and edge sets of a graph G. The open-neighborhood of a vertex
v in a graph G, denoted N(v), is the set of all vertices that are adjacent to v in G.
A k-DOMINATING SET of graph G is a vertex-subset S of size at most k such that for
each u ∈ V (G) \ S there exists v ∈ S such that {u, v} ∈ E(G). Given a graph G and
A, B ⊆ V (G), we say that A dominates B if every vertex in B \ A is adjacent in G to
some vertex in A.
Let H be a graph obtained from a copy of a graph G by applying some changes, and
let S be a vertex subset of G whose copy survives in H. For ease of presentation, we
sometimes abuse notation and use S to denote the copy of S in H as well.
2. A POLYNOMIAL KERNEL FOR K I ,J -FREE GRAPHS
In this section, we consider the k-DOMINATING SET problem on graphs that do not have
Ki, j as a subgraph, for fixed j ≥ i ≥ 1. If k = 1, then the problem can be solved in
linear time by checking if there is a vertex which is adjacent to all other vertices in the
graph. For i = 1, j ≥ i, a graph that does not have Ki, j as a subgraph has degree at
most j − 1. Any set of k vertices in such a graph G can dominate at most ( j − 1)k other
vertices, and so G is a YES instance of k-DOMINATING SET only if G contains at most jk
vertices. Thus, the problem is (1) polynomial-time solvable when k = 1, and (2) has a
linear vertex kernel when i = 1, j ≥ i, and so in the rest of the article we restrict our
attention to the cases k > 1, j ≥ i ≥ 2.
We derive a polynomial kernel for a slightly more general, colored version of the
k-DOMINATING SET problem. We define an rwb-graph (a red-white-blue graph) to be a
1 Throughout this paragraph, n denotes the number of vertices in the input graph.
graph whose vertices are (arbitrarily) colored with the three colors red, white, and
blue. More precisely, an rwb-graph is a graph G = (V, E) where V is partitioned into
RG , WG , and BG (colored red, white, and blue, respectively). An rwb-dominating set of
an rwb-graph G is a vertex subset S ⊆ V of G such that RG ⊆ S and S dominates BG .
The k-RWB-DOMINATING SET problem is defined as follows.
k-RWB-DOMINATING SET
Input: An rwb-graph G = (V, E) and a non-negative integer k.
Parameter: k
Question: Does G have an rwb-dominating set with at most k vertices?
The following simple claim shows that the colored version of the problem is more
general.
CLAIM 2.1. Let G be a graph and H the rwb-graph obtained from G by coloring all
the vertices blue. Then, G has a dominating set of size at most k if and only if H has an
rwb-dominating set of size at most k.
PROOF. Note that H is a copy of G with colored vertices. Let S be a dominating
set of G of size at most k. Since the set RH of red vertices of H is empty, RH ⊆ S.
Since H is isomorphic to G as a graph, S dominates all vertices in H. Hence, S is an
rwb-dominating set of H of size at most k.
Conversely, if S is an rwb-dominating set of H of size at most k, then since all vertices
in H are blue, S dominates all vertices in H. Thus, S is a dominating set of G of size
at most k.
In our kernelization algorithm for k-DOMINATING SET, we first color all the vertices of
the input graph G blue to obtain an rwb-graph H. Then we apply certain reduction
rules to H. Roughly speaking, the reduction rules try to identify (1) vertices that must
necessarily be in every rwb-dominating set of H of size at most k, and (2) vertices whose
deletion from H does not affect the size of a minimal rwb-dominating set of H of size
at most k.
The reduction rules also color various vertices red or white. Intuitively, the vertices
colored red are those that will be picked up by the reduction rules in the rwb-dominating
set D of size at most k that we are trying to construct. In particular, if there is a k-
dominating set in the graph, the rules ensure that there will be one that contains all the
red vertices. Vertices that are known to have been already dominated by D are colored
white. Clearly, all neighbors of red vertices are white, but our reduction rules color some
vertices white even if they have no red neighbors (at that point). These are vertices
that will be dominated by one of some constant number of vertices identified by the
reduction rules.2 The vertices that remain blue are those that are yet to be dominated.
We first describe an algorithm that takes as input an rwb-graph G on n vertices and
a positive number k, and runs in O(ni ) time. The algorithm either finds that G does not
have any rwb-dominating set of size at most k, or it constructs an instance (H, k) on
2
O(( j + 1)i+1 ki ) vertices such that G has an rwb-dominating set of size at most k if and
only if H has an rwb-dominating set of size at most k. To complete the kernelization
procedure, we show that this instance (H, k) of k-RWB-DOMINATING SET can be converted
into an equivalent instance of k-DOMINATING SET with a polynomially bounded increase
in both the number of vertices and the parameter value.
2 See reduction rule 2 for more details.
The algorithm applies a sequence of reduction rules in a specified order. The input
and output of each reduction rule are rwb-graphs.
Definition 2.2. A graph G is said to be reduced with respect to a reduction rule if
an application of the rule to G does not change G.
The correctness of the kernelization algorithm depends on the fact that each re-
duction rule satisfies the following correctness condition and preserves the invariants
stated here.
Definition 2.3 (Correctness). A reduction rule R is said to be correct if the following
condition holds: Let (G, k) be an instance of k-RWB-DOMINATING SET, and let (H, k′ ) be
the instance of k-RWB-DOMINATING SET obtained from (G, k) by one application of rule
R. Then H has an rwb-dominating set D′ of size at most k′ if and only if G has an
rwb-dominating set D of size at most k.3
Invariants.
(1) None of the reduction rules introduces a Ki, j into a graph.
(2) In the rwb-graphs constructed by the algorithm, no red vertex has a blue neigh-
bor.
(3) Let R1 and R2 be two reduction rules such that R1 precedes R2 in the order in
which the rules are presented below. Suppose (G1 , k1 ) is reduced with respect to R1 and
(G2 , k2 ) is obtained by an application of rule R2 to (G1 , k1 ). Then, (G2 , k2 ) is reduced
with respect to R1 .
2.1. The Reduction Rules and the Kernelization Algorithm
The kernelization algorithm assumes that the input graph is an rwb-graph. It applies
the following rules exhaustively in the given order. Each rule is repeatedly applied till
it causes no changes to the graph and then the next rule is applied.
We use some notational conventions in this section. For each rule in thia section, (G, k)
denotes the instance on which the rule is applied, and (H, k′ ) the instance that is ob-
tained when the rule is applied to (G, k). Further, D, D′ , k and k′ are as in Definition 2.3:
D is an rwb-dominating set of size k of G, and D′ an rwb-dominating set of H of size k′ .
Rule 1. Let B be the set of all isolated blue vertices in G.
(1) Color all vertices in B red.
(2) Set k′ := k.
LEMMA 2.4. Rule 1 is correct and preserves the invariants.
PROOF. Let (G, k) be the instance on which the rule is applied, and (H, k) the resulting
instance. Let I be the set of isolated blue vertices in G.
Let D be an rwb-dominating set of G of size at most k. From the definition of an
rwb-dominating set, RG ⊆ D. Since an isolated vertex can only be dominated by itself,
I ⊆ D. Since the only thing that the rule does is to color isolated blue vertices of G red,
RH = RG ∪ I, and so RH ⊆ D. Set D′ = D in H. Then, D′ dominates every vertex in H,
RH ⊆ D′ , and |D′ | ≤ k. Thus, D′ is an rwb-dominating set of H of size at most k.
Conversely, let D′ be an rwb-dominating set of H of size at most k. Set D = D′ in
G. Since the only thing that the rule does is to color isolated blue vertices of G red,
RG ⊆ RH ⊆ D′ = D, and so D is an rwb-dominating set of G of size at most k. Thus,
Rule 1 is correct.
3 Note, however, that none of our reduction rules changes the value of k, and so k′ = k for every one of these
rules.
Fig. 1. Rule 2.p. U is a set of i − p white or blue vertices which have a sufficiently large set B of common
blue neighbors. The rule adds a set X of i − p blue neighbors adjacent to all the vertices in U and colors all
the vertices in B white.
The rule trivially preserves the first two invariants, and vacuously preserves the
third.
Rule 2. This is a sequence of i −2 rules, named Rule 2.1, Rule 2.2, . . . , Rule 2.(i −2).
The kernelization algorithm first applies Rule 2.1 exhaustively, till it causes no more
changes in the graph. Then it applies the next rule in the sequence exhaustively, and
so on. The first rule in this sequence is as follows:
Rule 2.1. Let U = {u1 , u2 , . . . , ui−1 } be a set of (i − 1) vertices in G, none of which is
red. Let B be the set of common blue neighbors of the vertices in U . If |B| > b = jk,
then:
(1) Add (i − 1) new (gadget) vertices X = {x1 , x2 , . . . , xi−1 } and all the edges {u, x}; u ∈
U, x ∈ X to G, as in Figure 1.
(2) Color all the vertices in B white.
(3) Color all the vertices in X blue.
(4) Set k′ := k.
For p ∈ {2, 3, . . . , i − 2}, Rule 2. p is defined as follows:
Rule 2. p. Let b = jk p + kp−1 + kp−2 + · · · + k. Let U = {u1 , u2 , . . . , ui− p} be a set of
(i − p) vertices in G, none of which is red. Let B be the set of common blue neighbors of
the vertices in U . If |B| > b, then:
(1) Add (i − p) new (gadget) vertices X = {x1 , x2 , . . . , xi− p} and all the edges {u, x}; u ∈
U, x ∈ X to G, as in Figure 1.
(2) Color all the vertices in B white.
(3) Color all the vertices in X blue.
(4) Set k′ := k.
CLAIM 2.5. Consider an application of Rule 2. p, 1 ≤ p ≤ i − 2. If U is a set of vertices

of G that satisfies the condition in Rule 2. p, then in every subset of V (G) of size at most
k that dominates B, there must be at least one vertex that is in U .
PROOF. Let p = 1. Suppose there is a vertex set S ⊆ V (G) of size at most k such
that (1) S dominates B, and (2) S does not contain any vertex of U . Since |B| > jk,
there is a vertex v in S that dominates at least j + 1 vertices in B. Let T = N(v) ∩ B.
Then |T | ≥ j, and the vertex sets {U ∪ {v}, T } form the two parts of a Ki, j in G. This
contradicts the Ki, j -free property of the input graph or the first invariant.
Now let 2 ≤ p ≤ (i − 2). Let S ⊆ V (G) be a set of size at most k that dominates
B and does not contain any vertex of U . Since |B| > b, there is a vertex v ∈ S that
dominates at least (b/k) + 1 vertices in B. Because of the second invariant, v is not red.
Let T = N(v) ∩ B. Then, |T | ≥ (b/k), and T is in the common neighborhood of (U ∪ {v}).
Thus, (U ∪ {v}) is a set of (i − ( p − 1)) vertices in G, none of which is red, and which
have at least b/k > jk p−1 + kp−2 + · · · + k common blue neighbors. This contradicts the
fact that G is reduced with respect to Rule 2.( p − 1).
PROPOSITION 2.6. Rule 2. p is correct for 1 ≤ p ≤ (i − 2).
PROOF. Let D be an rwb-dominating set of G of size at most k, and let U be as in the
statement of Rule 2. p. Set D′ := D. Since D is an rwb-dominating set of G, RG ⊆ D.
Since the rule does not add any new red vertices in H, it follows that RH ⊆ D′ . Since
(1) D dominates all blue vertices of G, and (2) the rule removes no edges from G, it
follows that D′ = D dominates all blue vertices in H that are copies of blue vertices in
G. By Claim 2.5, D ∩ U ̸= ∅, and so D′ ∩ U ̸= ∅. Since all the new blue vertices added
to H—namely, those which constitute the set X—are adjacent to every vertex in U by
construction, D′ dominates all blue vertices in H. Thus, D′ is an rwb-dominating set of
H of size at most k.
Conversely, let D′ be an rwb-dominating set of H of size at most k. We consider three
cases.
D′ ∩ U = ∅. In this case, since D′ dominates X and X is an independent set, X ⊆ D′ .
Set D := (D′ \ X) ∪U . Since X and U are disjoint sets of equal cardinality, |D| ≤ |D′ | ≤ k.
Since D′ is an rwb-dominating set of H, RH ⊆ D′ . Since all vertices in X are blue and
since the reduction rule does not delete any red vertex from G to obtain H, it follows
that RG ⊆ D. Now, all the blue vertices dominated by X in H are contained in U and
U ⊆ D. Further, the set of vertices that are blue in G and white in H is exactly the set
B, and each vertex in U dominates all vertices in B. Therefore D dominates all blue
vertices in G, and thus D is an rwb-dominating set of G of size at most k.
D′ ∩ X = ∅. In this case, since D′ dominates X, it follows that D′ ∩ U ̸= ∅. Set D := D′ .
Then |D| = |D′ | ≤ k. For the same reasons as before, RG ⊆ D, and D dominates all
vertices (namely, the set B) which are blue in G and white in H. Since D′ dominates all
blue vertices in H, and since G can be obtained from H by deleting a set (namely, X)
of blue vertices and making the set B of white vertices blue, D = D′ dominates all blue
vertices in G. Thus, D is an rwb-dominating set of G of size at most k.
D′ ∩ U ̸= ∅, D′ ∩ X ̸= ∅. In this case, pick an arbitrary vertex v ∈ B and set D :=
(D′ \ X) ∪ {v}. Since D′ ∩ X ̸= ∅, it follows that |D| ≤ |D′ | ≤ k. For the same reasons as
previously stated, RG ⊆ D, and D dominates all vertices (namely, the set B) which are
blue in G and white in H. Since D′ dominates all blue vertices in H, D′ \ X dominates
all blue vertices in H \ X, except possibly for some blue vertices in U whose only
neighbors in D′ belong to X. But the vertex v dominates all vertices in U , and so D is
an rwb-dominating set of G of size at most k.
These three cases are exhaustive, and so it follows that for 1 ≤ p ≤ (i − 2), Rule 2. p
is correct.
PROPOSITION 2.7. For 1 ≤ p ≤ (i − 2), Rule 2. p preserves all the three invariants.
PROOF. Since we have shown that Rule 1 preserves all the invariants, we can assume
inductively that all the rules that are applied before Rule 2. p preserve all the three
invariants. We now consider the behavior of Rule 2. p for each of the invariants:
Invariant 1. From the inductive assumption, and from the fact that the input graph
is Ki, j -free, it follows that the graph G on which Rule 2. p is applied is Ki, j -free. Suppose
the graph H resulting from the application of the rule contains a Ki, j , say K, that is
Fig. 2. Rule 3. u is a white or blue vertex which has a sufficiently large set B of blue neighbors. The rule
colors u red, and colors all vertices in B white.
introduced by the rule. Then, K must necessarily contain at least one of the newly
added vertices in X, or else G = H \ X would also contain K. Since each vertex in X has
degree exactly (i − p) < i in H, no vertex in X can be part of a Ki, j in H, and it follows
that there is no Ki, j in H.
Invariant 2. From the inductive assumption, the invariant holds for the graph G on
which Rule 2. p is applied. The rule does not introduce new red vertices or color existing
non-red vertices red. Further, it does not add new vertices as neighbors to any existing
red vertex—observe that all vertices in U are non-red. Hence, it follows that the rule
preserves this invariant.
Invariant 3. Rule 2.1 preserves the invariant since it does not introduce isolated blue
vertices into the graph. Assume inductively that for 2 ≤ p ≤ i−2, Rules 2.1, . . . , 2.( p−1)
preserve the invariant. So the graph G on which Rule 2. p is applied is reduced with
respect to Rules 1, 2.1, . . . , 2.( p − 1). Let H be the graph that results when Rule 2. p is
applied to G. Then H is reduced with respect to Rule 1, since Rule 2. p does not introduce
isolated blue vertices in H. Suppose H is not reduced with respect to Rule 2.q for some
1 ≤ q ≤ ( p − 1). Then, H contains a set U = {u1 , u2 , . . . , ui−q } of (i − q) non-red vertices
such that U has more than b common blue neighbors B, where b = jk if q = 1 and
b = jkq + kq−1 + kq−2 + · · · + k otherwise. Either U or B (or both) must necessarily
contain at least one of the newly added vertices in X, or else G = H \ X would also be
not reduced with respect to Rule 2.q. Note that each vertex in X has degree exactly
(i − p) in H. Each vertex in U has degree at least b, and every vertex in B has degree
at least (i − q). Since p > q, we have (i − p) < (i − q). Since i ≤ j and k ≥ 1, it follows
that (i − p) < b. Thus, no vertex in X can be part of either U or B in H. It follows that
H is reduced with respect to Rule 2.q, and hence Rule 2. p preserves this invariant.
Thus, the rule preserves all the three invariants.
Putting together Propositions 2.6 and 2.7, we obtain the following lemma.
LEMMA 2.8. For 1 ≤ p ≤ (i − 2), Rule 2. p is correct and preserves all the three
invariants.
Rule 3. Let u be a blue or white vertex in G, and let B be the set of blue neighbors
of u. If |B| > h = jki−1 + ki−2 + · · · + k2 + k, then (See Figure 2):
(1) Color u red.
(2) Color all vertices in B white.
(3) Set k′ := k.
CLAIM 2.9. Consider an instance of applying Rule 3. If u is a vertex of G that satisfies

the condition in the rule, then u must be in every subset of V (G) of size at most k that
dominates B.
PROOF. Let S ⊆ V (G) be a set of size at most k that dominates B. If S does not contain
u, then there is a v ∈ S that dominates at least (h/k) + 1 of the vertices in B. The vertex
v is not red (because of the second invariant), and u, v have h/k > jki−2 + ki−3 + · · · + 1
common blue neighbors, a contradiction to the fact that G is reduced with respect to
Rule 2.(i − 2).
LEMMA 2.10. Rule 3 is correct and preserves all the three invariants.
PROOF. Let D be an rwb-dominating set of G of size at most k, and let u be as in the
statement of Rule 3. Set D′ := D. Since D is an rwb-dominating set of G, RG ⊆ D. From
Claim 2.9, u ∈ D. The rule does not add any new vertex to G to obtain H. Since u is
the only vertex that is red in H and not red in G, RH = (RG ∪ {u}) ⊆ D′ . Since (1) D
dominates all blue vertices of G, (2) the rule does not add new blue vertices or make
non-blue vertices blue, and (3) the rule removes no edges from the graph, it follows
that D′ = D dominates all blue vertices in H. Thus, D′ is an rwb-dominating set of H
of size at most k.
Conversely, let D′ be an rwb-dominating set of H of size at most k. Then from
Claim 2.9, u ∈ D′ . Set D := D′ . Since D′ is an rwb-dominating set of H, RH ⊆ D′ . Since
RG = RH \ {u}, RG ⊆ D. Since (1) D′ dominates all blue vertices in H, (2) the only blue
vertices in G that are not blue in H are in B ∪ {u}, and (3) u ∈ D dominates B ∪ {u}, it
follows that D = D′ dominates all blue vertices in G. Thus, D is an rwb-dominating set
of G of size at most k.
As for the invariants, Rule 3 does not change the structure of the graph. Further, it
gives the color white to all blue neighbors of the only vertex—namely, u—whose color
it changes to red. It follows that Rule 3 preserves all the three invariants.
Rule 4. If a white vertex u is adjacent to at most one blue vertex in G, then
(1) Delete u from G,
(2) Set k′ := k, and
(3) Apply Rule 1.
PROOF. Since we have already proved that Rule 1 is correct and preserves the three
invariants, it suffices to show that the first two steps of Rule 4 have the stated prop-
erties.4 We now proceed to do this; in the following, whenever we refer to Rule 4, we
mean the first two steps of this rule.
Let D be an rwb-dominating set of G of size at most k, and let u be as in the statement
of Rule 4. We consider two cases.
u∈/ D. In this case, set D′ := D. Since D is an rwb-dominating set of G, and since
the rule only deletes a white vertex u ∈ / D to obtain H, it follows that D′ is an rwb-
dominating set of H of size at most k.
u ∈ D. In this case, let A = (N(u) ∩ BG ) be the set of blue neighbors of u in G. Note
that | A| ≤ 1. Set D′ := (D \ {u}) ∪ A. Since |A| ≤ 1, |D′ | ≤ |D| ≤ k. Since D is an
rwb-dominating set of G, RG ⊆ D. Since the rule only deletes a white vertex u to obtain
H, it follows that RH = RG ⊆ D′ . Since (1) D dominates all blue vertices of G, (2) D′
contains A, the set of all blue vertices of G dominated by the vertex u that the rule
4 Except for arguing that the rule preserves the invariants: see the rest of the proof.
Fig. 3. Rule 5. u is a white vertex whose set of blue neighbors is identical to the blue neighborhood of a
white or blue vertex v. The rule deletes u.
deletes, and (3) the rule removes no edges from the graph other than those adjacent to
the removed white vertex u, it follows that D′ = D dominates all blue vertices in H.
Thus, D′ is an rwb-dominating set of H of size at most k.
Conversely, let D′ be an rwb-dominating set of H of size at most k. Set D := D′ . Since
D is an rwb-dominating set of H, and since G can be obtained from H by adding a
′
white vertex u and some edges incident on u to H, D = D′ is an rwb-dominating set of

G of size at most k.
As for the invariants, since Rule 4 only deletes a vertex, its application cannot
introduce any of the subgraphs that make it possible to apply Rules 2 or 3 to H.
It is possible that new isolated blue vertices may be introduced in H, but then the
application of Rule 1 ensures that such vertices do not survive once Rule 4 is completely
applied. It follows that Rule 4 preserves all the three invariants.
Rule 5. Let u be a white vertex in G, and let v be a white or blue vertex. If these two
vertices have identical sets of blue neighbors—that is, if N[u] ∩ BG = N[v] ∩ BG —then
(see Figure 3):
(1) Delete u from G
(2) Set k′ := k
PROOF. Let D be an rwb-dominating set of G of size at most k, and let u, v be as in
the statement of Rule 5. We consider two cases.
u∈/ D. In this case, set D′ := D. Since D is an rwb-dominating set of G, and since
the rule only deletes a white vertex u ∈ / D to obtain H, it follows that D′ is an rwb-
dominating set of H of size at most k.
u ∈ D. In this case, set D′ := (D \ {u}) ∪ {v}. Then |D′ | ≤ |D| ≤ k. Since D is an rwb-
dominating set of G, RG ⊆ D. Since the rule only deletes a white vertex u to obtain H, it
follows that RH = RG ⊆ D′ . Since (1) D dominates all blue vertices of G, (2) D′ contains
a vertex—namely, v—that dominates all blue vertices dominated by the vertex u that
the rule deletes, and (3) the rule removes no edges from the graph other than those
adjacent to the removed white vertex u, it follows that D′ dominates all blue vertices
in H. Thus, D′ is an rwb-dominating set of H of size at most k.
Conversely, let D′ be an rwb-dominating set of H of size at most k. Set D := D′ . Since
D is an rwb-dominating set of H, and since G can be obtained from H by adding a
′
white vertex u and some edges incident on u to H, D = D′ is an rwb-dominating set of

G of size at most k.
Since Rule 5 only deletes a vertex, its application cannot introduce any of the sub-
graphs that make it possible to apply Rules 2, 3, or 4 to H. No new isolated blue vertex
is introduced in H, since u is the only deleted vertex, and all blue neighbors of u have at
least one other neighbor that survives in H, namely the vertex v. It follows that Rule 5
preserves all the three invariants.
A simple example of a trivial NO-instance of the k-RWB-DOMINATING SET problem would
be the pair (I, ℓ) where I is a graph on two blue vertices and has no edges, and ℓ = 1.
We return such an instance if the current graph contains too many red or blue vertices.
Rule 6. If the graph G contains more than k red vertices or more than jki + ki−1 +
k + · · · + k2 blue vertices, then set (H, k′ ) to be a trivial NO-instance of the problem.
i−2
If neither of these conditions hold, then set H := G, k′ := k.

PROOF. Note that if the instance (G, k) satisfies neither of the two conditions, then
the rule returns the instance unchanged. Therefore, to show that the rule is correct, it
is sufficient to show that an instance (G, k) that satisfies either of the two conditions is
a NO-instance.
If |RG | > k, then since every rwb-dominating set of G must contain all of RG , G has
no rwb-dominating set of size at most k.
From the second invariant, no blue vertex of G has a red neighbor. Since G is reduced
with respect to Rules 1 to 5, no white or blue vertex in G has more than jki−1 +ki−2 +· · ·+
k blue neighbors, or else Rule 3 would have applied, contradicting the third invariant.
So k white or blue vertices in G can dominate at most jki + ki−1 + ki−2 + · · · + k2 blue
vertices. Hence, if |BG | > jki + ki−1 + ki−2 + · · · + k2 , then no set of k vertices in G can
dominate all of BG , and so in this case G has no rwb-dominating set of size at most k.
The reduction rule either returns the instance unchanged or returns a simple NO-
instance. In both cases, it trivially satisfies all the three invariants.
2.2. Algorithm Correctness, Running Time, and Kernel Size
Recall that the input to the kernelization algorithm is a pair (G, k) where G is an rwb-
graph and k is a non-negative integer. The algorithm applies reduction rules 1 to 6, in
this order, to (G, k), exhaustively applying each rule before applying the next. From the
correctness of rules 1 to 6 (see Lemma 2.4 to Lemma 2.13), we obtain the follwoing.
LEMMA 2.14. The kernelization algorithm is correct: Let (G, k) be the input to the
algorithm. If the algorithm says NO, then, G does not have an rwb-dominating set of
size at most k. Otherwise, let H be the rwb-graph output by the algorithm. Then, G has
an rwb-dominating set of size at most k if and only if H has an rwb-dominating set of
size at most k.
We now show that the kernelization algorithm runs in polynomial time. To do so, we
first show that the algorithm does not add too many gadget vertices to the input graph.
CLAIM 2.15. Let (G, k) be the input to the kernelization algorithm, where G is a Ki, j -
free rwb-graph on n vertices. The total number of gadget vertices that the algorithm
adds to the graph, over all applications of Rules 2.1 to 2.(i − 2), is less than n.
PROOF. We reuse the notation used to describe Rules 2.1 to 2.(i − 2). Rule 2.1 colors
all vertices in B white, and adds the new all-blue gadget vertex set X to the graph.
The set B contains at least ( jk + 1) blue vertices, and the set X has exactly (i − 1)
blue vertices. Thus, one application of Rule 2.1 reduces the count of blue vertices
in the graph by at least ( jk − i + 2). By a similar argument, we can see that for
2 ≤ p ≤ i − 2, each application of Rule 2. p reduces the count of blue vertices by at least
( jk p + kp−1 + · · · + k− i + p+ 1). Since, by assumption, j ≥ i ≥ 2 and k ≥ 2, it follows that
( jk − i + 2) ≤ ( jkp + kp−1 + · · · + k − i + p + 1) for 2 ≤ p ≤ i − 2. Thus each application
of one of Rules 2.1 to 2.(i − 2) reduces the total number of blue vertices in the graph
by at least ( jk − i + 2). Also, observe that the number of gadget vertices added to the
graph in each application of one of Rules 2.1 to 2.(i − 2) is at most (i − 1), where this
maximum is attained for Rule 2.1.
Consider an application of Rule 2. p for some 1 ≤ p ≤ i − 2. A blue or white vertex can
be part of a set U as mentioned in the rule only if it has at least jk p +kp−1 +kp−2 +· · ·+k
blue neighbors. Since the maximum number of blue neighbors that a gadget vertex
can have is i − 1, it follows that no gadget vertex will ever be part of the set U in
any application of Rule 2. p. Since the rwb-graph given as input to the kernelization
algorithm has exactly n blue vertices, Rules 2.1 to 2.(i − 2) can thus be applied at most
n/( jk − i + 2) times in total, over the full course of the algorithm. So the total number
of gadget vertices added to the graph over all applications of Rules 2.1 to 2.(i − 2)
is n(i − 1)/( jk + 2 − i), and this number is less than n since we assume that k is at
least 2.
This bound on the number of gadget vertices helps in showing that the algorithm
runs in polynomial time.
LEMMA !2.16. The kernelization
" algorithm can be implemented in such a way as to
run in O max(n2 , ini ) time when the input instance is a Ki, j -free rwb-graph G on n
vertices and m edges.
PROOF. We assume that the input rwb-graph is given in the form of a modified adja-
cency list. This representation differs from the standard adjacency list representation
in two ways:
(1) There is a provision for coloring each vertex red, white, or blue.
(2) Let u, v be two vertices such that {u, v} is an edge in the graph. Let vu be the node
for v in the adjacency list of u, and uv the node for u in the adjacency list of v. Then vu
contains a pointer to uv , and uv contains a pointer to vu.
This is not a costly assumption. Observe that we can add a new vertex x to such a
modified adjacency list L in time linear in the number of edges from x to the vertices
which are already present in L. It follows that one can convert an adjacency matrix
or adjacency list representation of the input rwb-graph to the modified form in time
linear in the size of the original representation.
Observe that Claim 2.15 implies that the total number of vertices in the graph at
any point during the execution of the algorithm does not exceed 2n. We now analyze
the time taken to exhaustively apply each rule.
Rule 1, Rule 3. Each application of one of these two rules colors at least one blue
vertex red. No reduction rule changes the color of a red vertex. From the bound on the
total number of vertices in the graph, it follows that Rule 1 and Rule 3 can be applied
at most 2n times each. One application of each of these two rules can be done in O(n)
time by a constant number of scans of the vertex list in the input graph, and so both
these rules can be applied exhaustively in O(n2 ) time.
Rule 2. As argued in the proof of Claim 2.15, no gadget vertex need ever be considered
for inclusion in the set U in any application of Rule 2. p. For applying Rule 2. p for a
fixed 1 ≤ p ≤ i − 2, therefore, the algorithm iterates over all (i − p)-subsets of the set
of all original
! (not
" gadget) vertices which are blue or white (at this point). This can be
done in O( i−np ) time, as was first shown by Ehrlich [1973]. For each such subset S,
ALGORITHM 1: Rule 2. p: Finding the set of common blue neighbors of a vertex

subset S.
1: A ← A binary array with indices ranging from 1 to |V (G)|, initialized to all 0s.
2: x ← A vertex in S.
3: for Each vertex y in the adjacency list of x do
4: if y is blue then
5: A[y] ← 1
6: end if
7: end for
8: for Each vertex z ∈ S \ {x} do
9: for Each vertex y in the adjacency list of z do
10: if y is not blue then
11: A[y] ← 0
12: end if
13: end for
14: end for
15: return {v ∈ V (G); A[v] = 1}
the algorithm finds the set of common blue neighbors of S as in Algorithm 1. Since the
total number of possible blue vertices—including gadget vertices—is at most 2n (see
Claim 2.15), this can be done in time O((i − p)n). A straightforward implementation of
2
the remaining part of Rule 2. p runs in O(n+(i−
! n " p) ) = O(n) time (since i− p! = O(1)),
" and
so Rule 2. p can be exhaustively applied in i− p · (O((i − p)n) + O(n)) = i−np i−n−1
p−1
· O((i −
p)n) = O(ni− p+1 ) time. All the rules 2. p; 1 ≤ p ≤ i − 2 can therefore be exhaustively
applied in O(ini ) time.
Observe that each application of Rule 2. p essentially consists of solving an instance
of the NP-hard Non-Induced (k1 , k2 ) Biclique problem [Binkele-Raible et al. 2010], and
hence cannot be done in O(nc ) time for some constant c that is independent of i, j and
k unless P = NP.
Rule 4. Each application of this rule deletes at least one white vertex. From the bound
on the total number of vertices in the graph, it follows that the rule can be applied at
most 2n times. Each application of the rule essentially consists of the deletion of one
vertex from the graph. This can be done in time linear in the degree of this vertex, by
making use of the pointers present in the data structure.
From Claim 2.15, less than n new (gadget) vertices are added to the graph by the
kernelization algorithm. As argued in the proof of Claim 2.15, no gadget vertex need
ever be considered for inclusion in the set U in any application of Rule 2. p. Thus,
the only edges at a gadget vertex a, at any point during the algorithm, are the ones
added by the particular application of Rule 2. p which introduced the vertex a in the
graph. Therefore, each new vertex has degree at most i − 1—this bound is attained
for vertices added by Rule 2.1. Thus, the total number of edges added to the graph
is at most (n − 1)(i − 1), and so the total number of edges in the graph is at most
m + (i − 1)(n − 1)) = O(m + in). It follows that the rule can be applied exhaustively in
O(m + in) = O(n2 ) time.
Rule 5. This rule can be exhaustively applied in O(|G|) = O(n2 ) time, as follows.
Two vertices in a graph are said to be twins if they have identical neighborhoods in
the graph. Observe that this defines an equivalence relation on the set of vertices.
Habib et al. [1998] show how to find the equivalence classes of this relation in a
graph G—that is, how to partition the vertex set of G into classes of twins—in O(|G|)
time. A small modification of their algorithm yields a partition of the vertex set of
the rwb-graph G, where each class consists of all white or blue vertices which have
identical blue neighborhoods. More specifically, we set the pivots—as defined in their
algorithm—to be the set of blue vertices, and the pivot set of each blue vertex to be its
closed neighborhood. It is straightforward to verify that with this modification, their
algorithm yields a partition of V (G) of the desired kind in O(|G|) time. We now go
through each equivalence class, and if a class contains a white vertex u and at least
one other vertex, then we delete u. By making use of the pointers present in the data
structure that represents the graph G, all these deletions can be effected in O(|G|) time.
Putting
! all these
" together, the kernelization algorithm can be implemented to run in
O max(n2 , ini ) time.
Now we prove a polynomial bound on the size of the reduced instance.
LEMMA 2.17. Let (G, k) be the input to the kernelization algorithm. If the algorithm
2
outputs the instance (H, k), then |V (H)| = O(( j + 1)i+1 ki ).
PROOF. From Rule 6, we get |RH | ≤ k and b = |BH | ≤ jki + ki−1 + · · · + k ≤ ( j + 1)ki .
Now we bound |WH |. Note that no two white vertices in H can have identical blue
neighborhoods, or else Rule 5 would have applied. Also, each white vertex has at least
two blue neighbors, or else Rule 4 would have applied. Hence, ! " ! the
" number! b " of white
vertices in H that have less than i blue neighbors is at most 2b + 3b +· · ·+ i−1 ≤ 2bi−1 .
No set of i blue vertices in H has more than ( j−1) common white neighbors, or else these
form a Ki, j . Hence, the number of white vertices that have i or more blue neighbors in
!"
H is at most bi ( j − 1) ≤ ( j − 1)bi . So the total number of white vertices in H,
|WH | ≤ 2bi−1 + ( j − 1)bi

= (2 + ( j − 1)b)bi−1
≤ ( j + 1)bi
≤ ( j + 1)(( j + 1)ki )i
2
= ( j + 1)i+1 ki
The bound in the lemma follows.
From Lemmas 2.16 and 2.17, we obtain the following.
COROLLARY 2.18. For every fixed j ≥ i ≥ 1, the k-RWB-DOMINATING SET problem on
2
Ki, j -free graphs has a polynomial kernel with O(( j + 1)i+1 ki ) vertices.
2.3. Removing the Colors

By Claim 2.1, the k-RWB-DOMINATING SET problem is a more general version of the k-
DOMINATING SET problem. By Corollary 2.18, k-RWB-DOMINATING SET has a polynomial
kernel in Ki, j -free graphs, and therefore, intuitively, so should k-DOMINATING SET. This
intuition is in fact justified, because the notion of k-RWB-DOMINATING SET being “more
general” than k-DOMINATING SET captures the fact that there is a “nice” polynomial-time
many-to-one reduction from k-DOMINATING SET to k-RWB-DOMINATING SET. To be more
precise:
—by Claim 2.1, k-DOMINATING SET polynomial-time reduces to k-RWB-DOMINATING SET,
and the reduction preserves the parameter – k goes to k;
—k-RWB-DOMINATING SET is in NP—a solution by itself is a certificate which is verifiable
in polynomial time;
Fig. 4. Removing the colors. W1 is the set of white vertices which are adjacent to red vertices, and W2 are
the other white vertices. The rule attaches a pendant to each red vertex, a pendant path of length two to
each vertex in W2 , and removes all the colors.
—k-DOMINATING SET is NP-hard in Ki, j -free graphs, since it is NP-hard in K2,2 -free
graphs; see, for example, the reduction from the 3-SAT problem attributed to David
Johnson [Haynes et al. 1998b, Theorem 1.7].
Therefore, to obtain a polynomial kernel for k-DOMINATING SET in Ki, j -free graphs, one
can do the following.
—Use Claim 2.1 to reduce k-DOMINATING SET to k-RWB-DOMINATING SET in polynomial

time, preserving the parameter.
—Use Corollary 2.18 to obtain a polynomial kernel for the k-RWB-DOMINATING SET in-
stance obtained in the previous step.
—Apply the polynomial-time many-to-one reduction from k-RWB-DOMINATING SET to k-
DOMINATING SET in Ki, j -free graphs, to the k-RWB-DOMINATING SET kernel obtained in
the previous step.
Since the k-RWB-DOMINATING SET kernel is of polynomial size in the original parameter
k, and the last reduction runs in polynomial time, the resulting k-DOMINATING SET
instance has size, and hence parameter, polynomial in k. This argument shows that
k-DOMINATING SET has a polynomial kernel when restricted to Ki, j -free graphs, but does
not give an explicit bound on the kernel size. We now describe a specific polynomial-
time many-to-one reduction from k-RWB-DOMINATING SET to k-DOMINATING SET in Ki, j -free
graphs and derive a concrete upper bound on the size of the kernel.
Let (G, k) be an instance of the k-DOMINATING SET problem on Ki, j -free graphs. To
obtain a polynomial kernel for this instance, we first color all the vertices of G blue
to obtain an equivalent instance of the k-RWB-DOMINATING SET problem. Then we apply
Corollary 2.18 on this k-RWB-DOMINATING SET instance to obtain a reduced instance
2
(G′ , k) of the problem, where |V (G′ )| = O(( j + 1)i+1 ki ).
We then apply the following steps (see Figure 4) to transform the reduced colored in-
stance (G′ , k) to an instance (H, k+w) of (uncolored) k-DOMINATING SET, where w = O(( j+
2
1)i+1 ki ) is the number of white vertices in G′ , which have no red neighbors. This in-
volves a significant increase in the value of the parameter, which is somewhat unusual:
for most known kernels the new parameter is upper bounded by the original value of
the parameter, or by a constant additive or multiplicative factor of the original value.
(1) For each white vertex u that has no red neighbor, add two new vertices u1 , u2 and
the edges {u, u1 }, {u1 , u2 }. That is, create a new path with two edges starting at u.
Let M be the set of all “middle” vertices u1 added in this manner.
(2) For each red vertex v, add a new vertex v1 and the edge {v, v1 }. That is, add a new
pendant vertex attached to v.
(3) Remove all colors from the vertices.
Note that this construction does not introduce a Ki, j into the graph, and that it
increases the number of vertices in the graph by at most a factor of 3. We use the
extra vertices to encode the information, which is captured by colors in the colored
instance. More precisely, suppose G′ has an rwb-dominating set S of size at most k.
By definition, the vertex set S contains all the red vertices and dominates all the blue
vertices in G′ . Therefore, in the graph H the same set S dominates the following sets
of vertices: (1) all vertices that were red in G′ , and all their neighbors, including all the
pendant vertices added in Step 2 and, (2) all the vertices which were blue in G′ . The
only vertices in H that are not dominated by S are: (1) white vertices in G′ which had
no red neighbors, and (2) the new vertices added to G′ by Step 1 of this construction.
The set M of “middle” vertices added in Step 1 dominates all these vertices in H, and
so S ∪ M is a dominating set of H of size at most k + w.
Conversely, suppose H has a dominating set of size at most k + w, and let X be an
inclusion-minimal dominating set of H of size at most k+ w. Then, we may assume the
following about X without loss of generality:
(1) X contains all the vertices which were red in G′ : RG′ ⊆ X,

(2) X contains all the “middle” vertices added in Step 1: M ⊆ X, and,
(3) X does not contain any pendant vertex added in Step 1 or Step 2.
To see these, observe first that if X does not contain a vertex v that was red in
G′ , then it must contain the pendant vertex v1 added in Step 2 of the construction,
because X must dominate v1 . The set (X \ {v1 }) ∪ {v} is then a dominating set of H of the
same size as X that contains one more vertex which was red in G′ , which justifies the
first assumption. A similar argument using the pendant vertices added in Step 1 of
the construction shows that we may assume that X contains all the “middle” vertices
added in this step. Finally, if v1 ∈ X is a pendant vertex added in Step 1 or Step 2,
then since X contains—by the first two assumptions—a vertex v adjacent to v ′ , the set
X \ {v ′ } is a smaller dominating set of H, and this contradicts the minimality of X.
Now observe that the vertices in M do not dominate any vertex which was blue in
G′ . Since (1) |RG′ ∪ M| ⊆ X, (2) the set X does not contain any pendant vertex added
by the construction, and (3) |M| = w, it follows that X \ M is a set of at most k vertices
in G′ , which contains all the red vertices and dominates all the blue vertices. Thus,
this reduction from k-RWB-DOMINATING SET to k-DOMINATING SET is sound, and so, from
Corollary 2.18, we have
THEOREM 2.19. For every fixed j ≥ i ≥ 1, the k-DOMINATING SET problem on Ki, j -free
2
graphs has a polynomial kernel with O(( j + 1)i+1 ki ) vertices.
3. A POLYNOMIAL KERNEL FOR d-DEGENERATE GRAPHS

A d-degenerate graph does not contain Kd+1,d+1 as a subgraph, and so the kernelization
algorithm of the previous section can be applied to a d-degenerate graph, setting i =
j = d + 1. The algorithm runs in O(max(n2 , (d + 1)nd+1 )) time and constructs a kernel
2
with O((d+ 2)d+2 · k(d+1) ) vertices. Since a d-degenerate graph on v vertices has at most
dv edges, we have the following.
ALGORITHM 2: A faster implementation of Rule 2. p in d-degenerate graphs.

1: for l ← 1 to n do
2: if vl is blue and its degree in G[vl+1 , . . . , vn] is at least d − p + 1 then
3: Find the neighborhood N of vl in G[vl+1 , . . . , vn]
4: for each (d − p + 1)-subset S of N do
5: if S has more than (d + 1)kp + kp−1 + · · · + k common blue neighbors in G
then
6: Apply the three steps of Rule 2. p, taking S as U
7: end if
8: end for
9: end if
10: end for
COROLLARY 3.1. The k-DOMINATING SET problem on d-degenerate graphs has a kernel
2
on O((d + 2)d+3 · k(d+1) ) vertices and edges.
Corollary 3.1 settles an open problem posed by Alon and Gutner [2008].
3.1. Improving the Running Time

We describe a modification to our algorithm that reduces the running time to O(2d ·d·n2 )
when the input is restricted to d-degenerate graphs; the bound on the kernel size
remains the same. The modified algorithm makes use of the following well-known
property of d-degenerate graphs.
FACT 3.2 [FRANCESCHINI ET AL. 2006, THEOREM 2.10]. Let G be a d-degenerate graph
on n vertices. Then, one can compute, in O(dn) time, an ordering v1 , v2 , . . . , vn of the
vertices of G such that for 1 ≤ i ≤ n, vi has at most d neighbors in the subgraph of G
induced on {vi , . . . , vn}.
The modification to the algorithm pertains to the way Rules 2.1 to 2.(d − 1) are
implemented: the rest of the algorithm remains the same.
The previous implementation of Rule 2. p, 1 ≤ p ≤ (d − 1), checks each (d − p + 1)-
subset of vertices in the graph to see if it satisfies the condition in the rule. When
the graph is degenerate, we instead make use of Fact 3.2 to quickly find such a set of
vertices, if it exists. Let G be the graph instance on n vertices on which Rule 2. p is to be
applied. First we delete, temporarily, all the red vertices in G. We then find an ordering
v1 , v2 , . . . , vn of the kind described in Fact 3.2, of all the remaining vertices in G. Let
U and B be as defined in the rule. Since each vertex in U has degree greater than d,
the first vertex vl in U ∪ B that appears in the ordering has to be from B. The vertex
vl will then have a neighborhood of size d − p + 1 that in turn has B as its common
neighborhood. We use this fact to look for such a pair (U, B) and exhaustively apply
Rule 2. p to G; see Algorithm 2. We then add back the red vertices that we deleted prior
to this step, along with all their edges to the rest of the graph. ! d "
As |N| ≤ d, the inner for loop is executed at most p−1 times for each iteration
of the outer loop. Each of the individual steps # in the! algorithm can be done in O(dn)
n d "
time, and so Rule 2. p can be applied in O(dn l=1 p−1
) time. All the rules 2. p can
#n #d−1 ! d " d 2
therefore be applied in O(dn l=1 p=1 p−1 ) = O(2 · dn ) time. Since the time taken
to apply each of the other rules exhaustively is O(n2 ) (see Lemma 2.16), we have the
following.
THEOREM 3.3. For every fixed d ≥ 1, the k-DOMINATING SET problem on d-degenerate
2
graphs has a kernel on O((d + 2)d+3 · k(d+1) ) vertices and edges, and this kernel can be
found in O(2d · d · n2 ) time for an input graph on n vertices.
4. INDEPENDENT DOMINATING SET IN K I ,J -FREE GRAPHS
The k-INDEPENDENT DOMINATING SET problem asks, for a graph G and a positive integer
k given as inputs, whether G has a dominating set S of size at most k such that
S is an independent set in G(that is, no two vertices in S are adjacent in G). This
problem is known to be NP-hard for general graphs [Garey and Johnson 1979], and
the problem parameterized by k is W[2]-complete [Downey and Fellows 1999]. Using a
modified version of the set of reduction rules in Section 2 we show that k-INDEPENDENT
DOMINATING SET has a polynomial kernel in Ki, j -free graphs for j ≥ i ≥ 1. For i = 1, j ≥ 1
we can easily obtain trivial kernels as before, and for i = 2, j ≥ 2 a simplified version
of the following algorithm gives a kernel of size O( j 3 k4 ).
4.1. The Reduction Rules
Rule 1 is the same as for the k-DOMINATING SET kernel for Ki, j -free graphs (Section 2.1).
Rules 2.1 to 2.(i − 2) and Rule 3 are modified to make use of the fact that we are looking
for a dominating set that is independent. A vertex u that is made white will never
be part of the independent dominating set D that is sought to be constructed by the
algorithm, since u is adjacent to some vertex v ∈ D. So a vertex can be deleted as soon
as it is made white. Also, rules 1, 2.1 . . . 2.(i − 2) and 3 are the only rules. Rules 4 and 5
from that section do not apply, because of the same reason as previously mentioned. The
modified rules ensure that no vertex is colored white, and so they work on rb-graphs:
graphs whose vertex set is partitioned into red and blue vertices. Using these modified
rules, the bounds of |RH | and |BH | in the proof of Lemma 2.17, and the fact that there
are no white vertices, we have the following.
THEOREM 4.1. For every fixed j ≥ i ≥ 1, the k-INDEPENDENT DOMINATING SET problem
on Ki, j -free graphs has a polynomial kernel with O( jki ) vertices.
For d-degenerate graphs, we have i = j = d + 1. Since a d-degenerate graph on v
vertices has at most dv edges, we have the following.
COROLLARY 4.2. For every fixed d ≥ 1, the k-INDEPENDENT DOMINATING SET problem
on d-degenerate graphs has a polynomial kernel with O(d(d + 1)kd+1 ) vertices and
edges.
5. CONCLUSION
We derive a polynomial kernel for the k-DOMINATING SET problem on graphs that do not
have Ki, j as a subgraph, for every fixed j ≥ i ≥ 1. We use this result to show that the k-
2
DOMINATING SET problem has a polynomial kernel of size O((d+2)d+3 ·k(d+1) ) on graphs of
degeneracy at most d, thereby settling an open problem posed by Alon and Gutner [Alon
and Gutner 2008; Gutner 2009]. A modified version of our kernelization algorithm for k-
DOMINATING SET yields a (smaller) kernel for the k-INDEPENDENT DOMINATING SET problem
on Ki, j -free and d-degenerate graphs, as well. All our kernelization algorithms are
based on simple reduction rules that look at the common neighborhoods of sets of
vertices. These results are primarily of theoretical interest in that the kernel sizes are
too large to be of practical use. For example, using the fact that planar graphs are
K3,3 -free, our kernelization algorithm can be used to obtain a polynomial kernel for the
k-DOMINATING SET on planar graphs. The upper bound that we derive on the size of this
kernel is O(k9 ), while the problem is known [Chen et al. 2007] to have a kernel on at
most 67k vertices in planar graphs.
By extending the kernel lower-bound techniques of Bodlaender et al. [2009a], Dom

et al. [2009] have shown that the k-DOMINATING SET problem on d-degenerate graphs
does not have a kernel of size polynomial in both d and k unless the Polynomial Hierar-
chy collapses to the third level. This shows that it is unlikely that the kernel size that
we have obtained for this class of graphs can be significantly improved.
Many interesting classes of graphs are of bounded degeneracy. These include all
nontrivial minor-closed families of graphs such as planar graphs, graphs of bounded
genus, graphs of bounded treewidth, and graphs excluding a fixed minor, and some
non-minor-closed families such as graphs of bounded degree. Graphs of degeneracy d
are Kd+1,d+1 -free. Since every Ki, j ; j ≥ i ≥ 2 contains a 4-cycle, every graph of girth 5
is Ki, j -free. Sachs [1963, Theorem 1] showed that there exist graphs of girth 5 and
arbitrarily large degeneracy (See Chapter III, Theorem 1.1 of Bollobás’ Extremal
Graph Theory [Bollobás 2004] for a short proof). Therefore, Ki, j -free graphs are strictly
more general than graphs of bounded degeneracy. To the best of our knowledge,
Ki, j -free graphs form the largest class of graphs for which FPT algorithms and poly-
nomial kernels are known for the dominating set problem variants discussed in this
article.
One interesting direction of future work is to try to demonstrate (no) kernels of
size f (d) · kc for the k-DOMINATING SET problem on d-degenerate graphs, where c is
independent of d. Note that the result of Dom et al. mentioned above does not suggest
that such kernels are unlikely. A graph property # is a set of graphs. The vertex deletion
problem for # asks, given a graph G and a non-negative integer k as inputs, whether
there exist at most k vertices in G whose deletion from G results in a graph that belongs
to #. A graph property # is said to be (1) nontrivial if neither # nor its complement
is finite, and (2) hereditary if (G ∈ #, H is a subgraph of G) =⇒ H ∈ #. Dell and van
Melkebeek [2010] have recently developed a lower-bound technique which allows them
to show, inter alia, that the vertex deletion problem for any nontrivial hereditary graph
class has no kernel of size O(k2−ϵ ) for any ϵ > 0. It will be interesting to see if this new
machinery can be extended to show that the k-DOMINATING SET problem does not have
kernels of size f (d) · kc on d-degenerate graphs.
Another challenge is to improve the running times of the kernelization algorithms: to
remove the exponential dependence on d of the running time for d-degenerate graphs,
and to obtain a running time of the form O(nc ) for Ki, j -free graphs where c is inde-
pendent of i and j. Also, as noted before, our kernelization algorithm blows up the
value of the parameter by a large factor. It would be interesting to see if one can obtain
kernels for the problem—in these classes of graphs—where the new parameter is up-
per bounded by a small function—say a constant multiple—of the original parameter.
Finally, it would also be interesting to see if other NP-hard variants of k-DOMINATING
SET—of which there are many [Haynes et al. 1998a, 1998b]—have FPT algorithms
and polynomial kernels on Ki, j -free graphs and graphs of bounded degeneracy. Very re-
cently, Cygan et al. [2010] showed that k-CONNECTED DOMINATING SET, where one asks for
a dominating set of size at most k that induces a connected subgraph of the input graph,
has no polynomial kernels in graphs of degeneracy d ≥ 2 unless the Polynomial Hier-
archy collapses to the third level. Note that our kernelization procedure breaks down
(as it should) when we insist that the solution be connected, since Rules 4 and 5 can
no longer be applied: white vertices which are useless in dominating blue vertices may
still be useful in providing connectivity for the dominating set that is being constructed.
ACKNOWLEDGMENTS
We thank Aravind Natarajan for pointing out the connection between Ki, j -free and d-degenerate graphs, and
Shai Gutner for his comments on an early draft of the conference version of this article. We are grateful to
our anonymous reviewers for a number of insightful comments which, among other improvements, helped
in tightening our analysis of the running time of the kernelization algorithm, and of the size of the kernel
obtained.
REFERENCES
ALBER, J., FELLOWS, M. R., AND NIEDERMEIER, R. 2004. Polynomial-time data reduction for dominating set. J.
ACM 51, 3, 363–384.
ALON, N. AND GUTNER, S. 2008. Kernels for the dominating set problem on graphs with an excluded minor.
Tech. Rep. TR08-066, The Electronic Colloquium on Computational Complexity (ECCC).
ALON, N. AND GUTNER, S. 2009. Linear time algorithms for finding a dominating set of fixed size in degenerated
graphs. Algorithmica 54, 4, 544–556.
ALON, N., RÓNYAI, L., AND SZABÓ, T. 1999. Norm-graphs: Variations and applications. J. Combinatorial Theory,
Series B 76, 2, 280–290.
BINKELE-RAIBLE, D., FERNAU, H., GASPERS, S., AND LIEDLOFF, M. 2010. Exact exponential-time algorithms for
finding bicliques. Inf. Proc. Lett. 111, 2, 64–67.
BODLAENDER, H. L., DOWNEY, R. G., FELLOWS, M. R., AND HERMELIN, D. 2009a. On problems without polynomial
kernels. J. Comput. Syst. Sci. 75, 8, 423–434.
BODLAENDER, H. L., FOMIN, F. V., LOKSHTANOV, D., PENNINKX, E., SAURABH, S., AND THILIKOS, D. M. 2009b. (Meta)
Kernelization. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science
(FOCS 2009). IEEE, 629–638.
BOLLOBÁS, B. 2004. Extremal graph theory. Dover Publications.
BOLLOBÁS, B. AND THOMASON, A. 1998. Proof of a conjecture of Mader, Erdös and Hajnal on topological complete
subgraphs. Eur. J. Combinat. 19, 8, 883–887.
CHEN, J., FERNAU, H., KANJ, I. A., AND XIA, G. 2007. Parametric duality and kernelization: Lower bounds and
upper bounds on kernel size. SIAM J. Comput. 37, 4, 1077–1106.
CYGAN, M., PILIPCZUK, M., PILIPCZUK, M., AND WOJTASZCZYK, J. O. 2010. Kernelization hardness of connectivity
problems in d-degenerate graphs. In Graph Theoretic Concepts in Computer Science - 36th International
Workshop (WG 2010). Revised Papers. Lecture Notes in Computer Science Series, vol. 6410, Springer,
147–158.
DAWAR, A. AND KREUTZER, S. 2009. Domination problems in nowhere-dense classes. In Proceedings of the
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2009). R. Kannan and K. N. Kumar, Eds., Leibniz International Proceedings in Informat-
ics (LIPIcs) Series, vol. 4, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany,
157–168.
DELL, H. AND VAN MELKEBEEK, D. 2010. Satisfiability allows no nontrivial sparsification unless the polynomial-
time hierarchy collapses. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC
2010). ACM, 251–260.
DEMAINE, E. D., FOMIN, F. V., HAJIAGHAYI, M., AND THILIKOS, D. M. 2005. Subexponential parameterized algo-
rithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52, 6, 866–893.
DIESTEL, R. 2005. Graph Theory 3rd Ed. Springer-Verlag, Berlin.
DOM, M., LOKSHTANOV, D., AND SAURABH, S. 2009. Incompressibility through Colors and IDs. In Proceedings of
the International Colloquium on Automata, Languges and Programming (ICALP 2009). Lecture Notes
in Computer Science, vol. 5555, Springer, 378–389.
DOWNEY, R. G. AND FELLOWS, M. R. 1999. Parameterized Complexity. Springer.
EHRLICH, G. 1973. Loopless algorithms for generating permutations, combinations, and other combinatorial
configurations. J. ACM 20, 3, 500–513.
ELLIS, J. A., FAN, H., AND FELLOWS, M. R. 2004. The dominating set problem is fixed parameter tractable for
graphs of bounded genus. J. Algor. 52, 2, 152–168.
FLUM, J. AND GROHE, M. 2006. Parameterized Complexity Theory. Springer-Verlag.
FOMIN, F. V., LOKSHTANOV, D., SAURABH, S., AND THILIKOS, D. M. 2010. Bidimensionality and kernels. In
Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). SIAM,
503–510.
FOMIN, F. V. AND THILIKOS, D. M. 2004. Fast parameterized algorithms for graphs on surfaces: Linear kernel
and exponential speed-Up. In Proceedings of the 31st International Colloquium on Automata, Languages
and Programming (ICALP 2004). Lecture Notes in Computer Science Series, vol. 3142, Springer, 581–
592.
FOMIN, F. V. AND THILIKOS, D. M. 2006. Dominating sets in planar graphs: branch-width and exponential
speed-up. SIAM J. Comput. 36, 2, 281–309.
FRANCESCHINI, G., LUCCIO, F., AND PAGLI, L. 2006. Dense trees: A new look at degenerate graphs. J. Disc.
Algor. 4, 455–474.
GAREY, M. R. AND JOHNSON, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP–
Completeness. Freeman, San Francisco.
GOLOVACH, P. A. AND VILLANGER, Y. 2008. Parameterized complexity for domination problems on degenerate
graphs. In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer
Science, WG 2008. Lecture Notes in Computer Science Series, vol. 5344, Springer, 195–205.
GUO, J. AND NIEDERMEIER, R. 2007. Invitation to data reduction and problem kernelization. SIGACT News 38, 1,
31–45.
GUTNER, S. 2009. Polynomial kernels and faster algorithms for the dominating set problem on graphs with
an excluded minor. In Proceedings of the 4th International Workshop on Parameterized and Exact Com-
putation (IWPEC 2009). Springer-Verlag, Berlin, 246–257.
HABIB, M., PAUL, C., AND VIENNOT, L. 1998. A synthesis on partition refinement: A useful routine for strings,
graphs, Boolean matrices and automata. In Proceedings of the 15th Annual Symposium on Theoretical
Aspects of Computer Science (STACS 98). M. Morvan, C. Meinel, and D. Krob, Eds., Lecture Notes in
Computer Science Series, vol. 1373, Springer, 25–38.
HAYNES, T. W., HEDETNIEMI, S. T., AND SLATER, P. J. 1998a. Domination in Graphs: Advanced topics. Pure and
applied mathematics: A series of monographs and textbooks series, vol. 209, Marcel Dekker, Inc.
HAYNES, T. W., HEDETNIEMI, S. T., AND SLATER, P. J. 1998b. Fundamentals of Domination in Graphs. Pure and
applied mathematics: A series of monographs and textbooks series, vol. 208, Marcel Dekker, Inc.
KOMLÓS, J. AND SZEMERÉDI, E. 1996. Topological cliques in graphs II. Combinat. Probab. Comput. 5, 79–90.
NIEDERMEIER, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press.
PHILIP, G., RAMAN, V., AND SIKDAR, S. 2009. Solving dominating set in larger classes of graphs: FPT algorithms
and polynomial kernels. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA
2009). Lecture Notes in Computer Science Series, vol. 5757, Springer, 694–705.
RAMAN, V. AND SAURABH, S. 2008. Short cycles make w-hard problems hard: FPT algorithms for W-hard
problems in graphs with no short cycles. Algorithmica 52, 2, 203–225.
SACHS, H. 1963. Regular graphs with given girth and restricted circuits. J. London Math. Soc. s1-38, 1,
423–429.
Received July 2010; revised January 2011; accepted March 2011

A11 Philip PDF

Uploaded by

Copyright:

Available Formats

A11 Philip PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

A11 Philip PDF

Uploaded by

Copyright:

Available Formats

11

Polynomial Kernels for Dominating Set in Graphs of

ACM Reference Format:

Table I. Some FPT and kernelization results for k-DOMINATING SET

2 See reduction rule 2 for more details.

CLAIM 2.5. Consider an application of Rule 2. p, 1 ≤ p ≤ i − 2. If U is a set of vertices

CLAIM 2.9. Consider an instance of applying Rule 3. If u is a vertex of G that satisfies

white vertex u and some edges incident on u to H, D = D′ is an rwb-dominating set of

white vertex u and some edges incident on u to H, D = D′ is an rwb-dominating set of

If neither of these conditions hold, then set H := G, k′ := k.

ALGORITHM 1: Rule 2. p: Finding the set of common blue neighbors of a vertex

|WH | ≤ 2bi−1 + ( j − 1)bi

2.3. Removing the Colors

—Use Claim 2.1 to reduce k-DOMINATING SET to k-RWB-DOMINATING SET in polynomial

(1) X contains all the vertices which were red in G′ : RG′ ⊆ X,

3. A POLYNOMIAL KERNEL FOR d-DEGENERATE GRAPHS

ALGORITHM 2: A faster implementation of Rule 2. p in d-degenerate graphs.

3.1. Improving the Running Time

By extending the kernel lower-bound techniques of Bodlaender et al. [2009a], Dom

Received July 2010; revised January 2011; accepted March 2011

You might also like