Simpler Linear-Time Kernelization
for Planar Dominating Set
Torben Hagerup
Institut f¨ur Informatik, Universit¨at Augsburg, 86135 Augsburg, Germany
hagerup@informatik.uni-augsburg.de
Abstract. We describe a linear-time algorithm that inputs a planar
graph G and outputs a planar graph of size O(k) and with domination
number k, where k is the domination number of G, i.e., the size
of a smallest dominating set in G. In the language of parameterized
computation, the new algorithm is a linear-time kernelization for the
NP-complete Planar Dominating Set problem that produces a kernel
of linear size. Such an algorithm was previously known (van Bevern
et al., these proceedings), but the new algorithm and its analysis are
considerably simpler.
1 Introduction
A current trend in the area of parameterized computation is the quest for kernelization
algorithms for hard computational problems. Briefly stated, a kernelization
algorithm is a polynomial-time procedure that transforms an instance of
the problem under consideration into an equivalent instance whose size depends
only on the value of the chosen parameter. More formally, a kernelization for a
parameterized problem L ⊆ Σ∗
×N, where Σ is an alphabet and N = {1, 2, . . .},
is an algorithm A for which there exists a polynomial p : N → N and a function
f : N → N such that, applied to an instance I = (G, k) ∈ Σ∗
× N, A computes,
within p(|I|) steps, an instance I = (G , k ) ∈ Σ∗
×N with |I | ≤ f(k) and k ≤ k
such that I ∈ L ⇔ I ∈ L. Here |I| and |I | denote the number of symbols in
the representation of I and I , respectively, according to some suitable encoding
scheme.
A kernelization can be valuable in the solution of a hard parameterized problem
because, used as a preprocessing routine, it allows the instance size to be
reduced, perhaps significantly, before an exponential-time algorithm is applied
to the remaining, reduced instance. From the outset, much importance was attached
to the kernel size, f(k), and for some problems a series of results successively
lowered the smallest upper bound on the size of a kernel known to be
computable in polynomial time. This was the case for the problem of interest
in this paper, the NP-complete Planar Dominating Set problem, formally
defined as the language
{(G, k) : G is an undirected planar graph, k ∈ N and Dom(G) ≤ k} ,
D. Marx and P. Rossmanith (Eds.): IPEC 2011, LNCS 7112, pp. 181–193, 2012.
c Springer-Verlag Berlin Heidelberg 2012
182 T. Hagerup
where Dom(G) is the domination number of G, i.e., the size of a smallest dominating
set in G, a smallest subset D of the vertex set V of G such that every
vertex in V \ D is adjacent in G to a vertex in D. Alber et al. [1] described
a first kernelization for Planar Dominating Set, whose kernel is of size at
most 335k, where k is the domination number of the input graph. The bound
was subsequently lowered to 67k by Chen et al. [4], who also proved that no kernelization
can yield a kernel of size bounded by (2− )k, for arbitrary fixed > 0,
unless P = NP. Other, more general, approaches [3,5] yield kernels of linear size
for several problems defined on planar graphs, including Planar Dominating
Set.
Only more recently has the kernelization time, p(|I|), come into focus. The
kernelizations for the Planar Dominating Set problem mentioned above both
operate in cubic time, and so are rather slow. Traditionally, this has been largely
ignored, the reasoning being that since the polynomial-time preprocessing is followed
by an exponential-time computation anyway, there is little point in worrying
about the degree of the polynomial. Whereas there is much truth in this
argument, it is hardly advisable to be dogmatic about the issue. From the standpoint
of theory, one might object that the polynomial is applied to the original
instance size, n, whereas exponential means exponential in the kernel size, which
may be substantially smaller than n. In practice, one can observe that the running
time of a polynomial-time procedure is not always a negligible fraction of
the time consumed by an exponential-time computation. In summary, it seems a
worthwhile goal to try to reduce both the kernel size and the kernelization time.
At present, linear-time kernelizations are known for only few problems. Vertex
Cover is a case in point: The classic Buss’ kernelization that yields a
kernel of size O(k2
) works in linear time (more powerful kernelizations for Vertex
Cover that produce kernels with O(k) vertices are known [9, Section 7.4],
but none of these runs in linear time). Other problems for which linear-time kernelizations
were described in the literature include certain problems on planar
graphs [8], Cluster Editing [11] and Rooted Leaf Outbranching [7]; as
in the case of Vertex Cover, kernels of linear size are not obtained in linear
time. An exception concerns the Weighted Max Leaf problem investigated
by Jansen [6], who states without giving all details that a linear-sized kernel
can be obtained in linear time. For the Planar Dominating Set problem, a
first kernelization algorithm that yields a kernel of linear size in linear time was
described by van Bevern et al. [2]. It is based on the region decomposition of
the earlier cubic-time kernelization algorithm of [1] and can be viewed to some
extent as a more efficient implementation of that algorithm. Here we take a fresh
look at the problem and develop a second linear-time kernelization for Planar
Dominating Set that yields a kernel of linear size. Compared with the result
of van Bevern et al., the advantage of the new result is that the algorithm and
its analysis, while not trivial, are considerably simpler. On the other hand, the
approach based on region decomposition may have applications to other problems
defined on planar graphs, while the techniques described here are more
problem-specific.
Simpler Linear-Time Kernelization for Planar Dominating Set 183
In terms of kernel size, the new algorithm, at least with its present analysis,
is not competitive with the earlier algorithms mentioned above. Moreover, there
is a certain trade-off between simplicity and small kernel size. For these reasons,
we refrain from calculating the exact kernel size and demonstrate only as simply
as we can that it is O(k). Of course, if the algorithm of [4] is applied after the
new algorithm, a kernel of size at most 67k is obtained in O(n + k3
) time.
Our result is slightly more than a kernelization. As is a standard requirement
for kernelizations although usually not considered part of the formal definition,
our arguments imply an efficient and in fact linear-time procedure for obtaining
from an arbitrary dominating set in the kernel a dominating set of the same size
in the original input graph. Moreover, similarly as the algorithm of van Bevern
et al. [2], our algorithm actually does not need to know the parameter k. Rather,
it inputs a graph G and computes a graph G with Dom(G ) = Dom(G), so that
(G, k) ∈ Planar Dominating Set ⇔ (G , k) ∈ Planar Dominating Set
for every k ∈ N. Correspondingly, a step in the kernelization that inputs a graph
G and outputs another graph G will be called correct if Dom(G) = Dom(G ).
Subsequently to the work described here, it was demonstrated that the same
techniques can be employed to obtain linear-time kernelizations with linear kernel
size for more general domination problems in planar graphs. These include
Planar Annotated Dominating Set, i.e., given an undirected planar graph
G = (V, E), a set B ⊆ V and an integer k ∈ N, decide whether there is a set
D ⊆ V with |D| ≤ k such that every vertex in B \ D is adjacent in G to a vertex
in D. A few of the ideas in this paper suffice to give a linear-time kernelization
with linear kernel size for the Planar Edge Dominating Set problem,
i.e., given an undirected planar graph G = (V, E) and an integer k ∈ N, decide
whether there is a subset D ⊆ E with |D| ≤ k such that every edge in E shares
an endpoint with an edge in D. This ongoing work will be reported elsewhere.
1.1 Overview of the New Algorithm
The starting point for the kernelization described here was the observation that
if two vertices x and y in an n-vertex planar graph G with small domination
number k have many joint neighbors, then most of these neighbors have no
neighbors other than x and y that are not also neighbors of x or y. Then an
optimal dominating set contains x or y, and most joint neighbors of x and y are
without influence on the domination number and can be removed. It therefore
makes sense to search for a small vertex set A such that many vertices have two
neighbors in A. A good candidate for A is a smallest set P of vertices in G with
total degree at least n − |P|.
It may not be the case that there are many vertices with two neighbors in
P. Then, however, most vertices have exactly one neighbor in P, and the union
Q of P with the set of vertices without neighbors in P is still small. Think of
the vertices in Q as the centers of stars that include all vertices in G. If it is
not optimal to dominate a star from its center, every vertex in the star must be
dominated by a vertex that also dominates at least one vertex in a different star.
By planarity, only few vertices dominate parts of three or more stars. As for
184 T. Hagerup
vertices that dominate parts of exactly two stars, at most two such dominating
vertices are needed for each pair of stars, since otherwise the two stars in question
could be dominated more cheaply from their centers. We cannot know which two
vertices are present in an optimal solution, but for each of the two stars we can
pick a single vertex that dominates a maximum number of vertices in that star
and at least one vertex in the other star. By planarity, adding the vertices that
were picked and those that dominate parts of more than two stars to Q still
results in a small set R.
Let S be the set of centers x of stars for which the vertices in R \ {x} do not
have enough edges to the star of x to dominate it completely. A dominating set
can be assumed to be a superset of S, and therefore every vertex in the set T
of vertices at distance 1 from S can be removed unless it is needed to dominate
vertices outside of S ∪ T . This is the case only if it has two or more neighbors
outside of S ∪ T , a condition that, by planarity, holds for only few vertices in T .
If most vertices belong to stars whose centers are not in S, there may not be
many vertices in T to remove. In that case, however, R is a small set such that
many vertices have two neighbors in R, and we can pick A = R and remove many
vertices outside of R as described above. In every situation, if G contains more
than Ck vertices for a suitable constant C, a constant fraction of the vertices in
G can be removed in linear time, and all that remains is to repeat the process
until the number of vertices no longer drops as fast as established for graphs
with more than Ck vertices.
2 Preliminaries
2.1 Definitions and Notation
Throughout this subsection, let G = (V, E) be an undirected graph.
When U ⊆ V , G[U] denotes, as usual, the subgraph of G induced by U, i.e.,
(U, {{u, v} ∈ E : u, v ∈ U}).
For u ∈ V , we denote by NG(u) the set {v ∈ V : {u, v} ∈ E} of neighbors
of u in G and write NG[u] for NG(u) ∪ {u}. For U ⊆ V , NG(U) = u∈U NG(u)
and NG[U] = u∈U NG[u]. A vertex u ∈ V dominates the vertices in NG[u] in
G, and a vertex set U ⊆ V dominates the vertices in NG[U] in G and G itself if
NG[U] = V .
For A ⊆ V and i ≥ 0, we denote by Ni
G(A) the set {u ∈ V \A : |NG(u)∩A| =
i} of vertices in V \ A that have precisely i neighbors in A, and N≥i
G (A) =
∞
j=i Nj
G(A).
2.2 Properties of Planar Graphs
The facts stated in Lemma 1 below are well-known. For proofs see, e.g., [10]. The
remaining lemmas in this section are straightforward consequences of Lemma 1.
Simpler Linear-Time Kernelization for Planar Dominating Set 185
Lemma 1. Let G = (V, E) be an undirected planar graph and take n = |V | and
m = |E|. Then
(a) m ≤ 3n.
(b) If G is bipartite, then m ≤ 2n.
(c) No three distinct vertices in G have three common neighbors.
Lemma 2. Let G = (V, E) be an undirected planar graph and let A ⊆ V . Then
(a) For i = 3, 4, . . . , let ni = |Ni
G(A)|. Then
∞
i=3(i − 2)ni ≤ 2|A|.
(b) |N≥3
G (A)| ≤ 2|A|.
(c) Let F be a set of faces in a planar embedding of G, the boundary of each of
which contains 3 or more vertices in N≥2
G (A). Then at most 6|A| vertices in
N≥2
G (A) lie on the boundary of one or more faces in F.
Proof. (a) Applying Lemma 1(b) to the subgraph of G induced by the edges
with one endpoint in A and one endpoint in N≥3
G (A) yields
∞
i=3 ini ≤
2(|A| + ∞
i=3 ni).
(b) Since |N≥3
G (A)| =
∞
i=3 ni ≤
∞
i=3(i − 2)ni, the claim follows from part (a).
(c) Apply part (a) to the graph obtained from G by, for each F ∈ F, adding
a new vertex vF and a new edge from vF to each vertex in N≥2
G (A) on
the boundary of F. If the number of new edges is m, this shows that m ≤
2(|A| + |F|) ≤ 2(|A| + m/3) and therefore that m ≤ 6|A|.
Lemma 3. Let G = (V, E) be an n-vertex undirected planar graph, let A ⊆ V
and assume that x∈A |NG[x]| ≥ n. For i = 0, 1, . . . , let ni = |Ni
G(A)|. Then
n0 ≤ n2 + 10|A|.
Proof. The total degree in G of the vertices in A is at least n − |A| and, by
Lemma 1(a), at most 3|A| edges have both endpoints in A. Therefore
∞
i=0
ini ≥ n − |A| − 2 · 3|A| =
∞
i=0
ni − 6|A|
and
n0 ≤ n2 +
∞
i=3
(i − 1)ni + 6|A| ≤ n2 + 6|A| + 2
∞
i=3
(i − 2)ni .
By Lemma 2(a),
∞
i=3(i − 2)ni ≤ 2|A|. The claim follows.
3 Near-Twin Reduction
A central part of our kernelization is a procedure called near-twin reduction
that is applied to an undirected planar graph G = (V, E) and parameterized by
a vertex set A ⊆ V .
186 T. Hagerup
3.1 Description
With G and A as above, define the A-neighborhood of a vertex u ∈ V as the set
NG(u) ∩ A. For all x, y ∈ A with x = y, call u ∈ V introspective with support
{x, y} if u ∈ A, the A-neighborhood of u is {x, y}, and the A-neighborhood of
every vertex at distance at most 2 from u in G[V \ A] is a nonempty subset
of {x, y}. A near-twin reduction in G with support A returns the graph G =
(V , E ) obtained from G by the following operation: For all {x, y} ⊆ A with
x = y such that the set I{x,y} of introspective vertices with support {x, y} is of
size at least 4, replace the vertices in I{x,y} by two new degree-2 vertices with
neighbors x and y (see Fig. 1). G is clearly planar. In Section 4, we write an
application of the near-twin reduction with support A to G as a function call
NearTwin Reduce(G, A) that returns the graph G resulting from the near-twin
reduction.
x y
⇒
G = (V, E) G = (V , E )
x y
: ∈ A: ∈ I{x,y} ⊆ V \ V : ∈ V \ V
Fig. 1. A near-twin reduction with support A transforms G into G
3.2 Correctness
Suppose that D is a dominating set in G and consider the set D ⊆ V obtained
from D as follows: For all {x, y} ⊆ A with x = y such that |I{x,y}| ≥ 4 and
D ∩ NG[I{x,y}] ⊆ {x, y}, replace the vertices in D ∩ NG[I{x,y}] by x and y. Note
that NG[I{x,y}] ∩ NG[I{x ,y }] = Ø for all {x , y } ⊆ A with x = y and {x, y} =
{x , y }, so that the replacement can actually be carried out as described. Since
NG[NG[I{x,y}]] ⊆ NG[{x, y}] for all {x, y} ⊆ A with x = y, D still dominates
G, and since D ∩ NG[I{x,y}] = Ø, it is easy to see that D dominates G . By
Lemma 1(c), the vertices in a set I{x,y} with |I{x,y}| ≥ 4 cannot be dominated in
G by any single vertex other than x or y. Therefore, if D ∩ NG[I{x,y}] ⊆ {x, y},
then |D ∩ NG[I{x,y}]| ≥ 2. This shows that |D | ≤ |D|.
Suppose, conversely, that D is a dominating set in G and consider the set
D ⊆ V obtained from D by replacing the vertices in D ∩ (V \ V ) by their
neighbors. D clearly dominates G, and |D| ≤ |D | since for every vertex in
D ∩(V \V ) without neighbors in D there is another vertex in D ∩(V \V ) with
Simpler Linear-Time Kernelization for Planar Dominating Set 187
the same two neighbors. Altogether, we have shown that Dom(G) = Dom(G ),
i.e., the near-twin reduction is correct.
3.3 Execution Time
The near-twin reduction with support A can be applied to G in O(|V |) time
as follows: First each vertex u ∈ V \ A computes the set U, where U is the
A-neighborhood of u if the latter is of size 1 or 2 and U = {⊥} for a special
symbol ⊥ otherwise. Then, in each of two successive rounds, each vertex in V \A
broadcasts its set to all its neighbors in V \ A and forms the new value of its
own set as the union of the old value and the sets received, except that every
union that contains ⊥ or is of size 3 or more is replaced by {⊥}. A vertex is
introspective exactly if its stored set is of size 2 throughout this process. The
introspective vertices can be sorted by their supports in O(|V |) time with radix
sort, after which it is a simple matter to construct G .
3.4 Reduction Progress
Lemma 4. Let G = (V, E) be an undirected planar graph, let A ⊆ V and let
G = (V , E ) be the graph obtained by carrying out a near-twin reduction in G
with support A. Then |N2
G (A)| = O(|A| + Dom(G)).
Proof. We first show that in G , no four introspective vertices have a common
support {x, y}. Otherwise some vertex u ∈ (V ∩ V ) \ A with A-neighborhood
{x, y} would be introspective in G , but not in G. This can happen only if the
near-twin reduction in G removes a vertex v at distance at most 2 from u in
G[V \ A] whose A-neighborhood is not {x, y}. But this is impossible since the
A-neighborhood of u is {x, y} and u is within distance 2 of v in G[V \ A]—the
presence of u would prevent v from being introspective, and therefore from being
removed.
Since clearly there is a planar graph on the vertex set A that contains an edge
{x, y} if there is an introspective vertex with support {x, y}, Lemma 1(a) shows
that the number of introspective vertices in U = N2
G (A) is bounded by 3 · 3|A|.
To bound the number of the remaining vertices in U, fix a planar embedding of
G and its restriction φ to the subgraph of G induced by the set of edges with
one endpoint in A and one endpoint in U. Denote by F the set of faces of φ.
We can clearly assume that |U| ≥ 3. Then F = F2 ∪ F≥3, where F2 and F≥3
are the sets of faces in F whose boundary contains exactly 2 and ≥ 3 distinct
vertices in U, respectively. Moreover, every face in F whose boundary contains
three distinct vertices in A belongs to F≥3.
Let x, y ∈ A be distinct and let u be a vertex in U whose A-neighborhood is
{x, y}. If u is not introspective, there is a path π in G[V \ A] of length at most 2
from u to a vertex v whose A-neighborhood is not a nonempty subset of {x, y}.
Choose π as a shortest such path. Then one of the following holds (see Fig. 2):
– v ∈ U, and every face in F whose boundary contains both v and the last
vertex in U that precedes v on π belongs to F≥3, since its boundary includes
the A-neighborhoods of both u and v.
188 T. Hagerup
: ∈ F∗
: ∈ A
: ∈ U∗
: introspective
: ∈ NG (U∗
) ∩ (U \ U∗
)
: ∈ N0
G (A) ∪ N≥3
G (A) : ∈ N1
G (A)
Fig. 2. Vertices in U sufficiently far from the faces in F∗
are introspective
– v ∈ N1
G (A), and the face in F whose interior contains v belongs to F≥3,
since its boundary includes the A-neighborhoods of both u and v.
– v ∈ N0
G (A) ∪ N≥3
G (A).
Let F∗
be the union of F≥3 with the set of faces in F2 whose interior contains
a vertex in N0
G (A) ∪ N≥3
G (A) and let U∗
be the set of vertices in U on the
boundary of a face in F∗
. The considerations above show that every vertex in
U that is not introspective is at distance at most 1 in G from a vertex in U∗
.
Let F be a face in F2 whose interior contains a vertex v ∈ N0
G (A). A vertex
that dominates v must lie in the interior of F or be one of its two boundary
vertices in U, each of which can dominate vertices in at most one face other
than F. This shows the number of vertices in U on the boundaries of faces in F2
whose interiors contain a vertex in N0
G (A) to be at most 3Dom(G ) = 3Dom(G).
By Lemma 2(b), the number of vertices in U on the boundaries of faces in F2
whose interiors contain a vertex in N≥3
G (A) is bounded by 2 · 2|A|. And, finally,
Lemma 2(c) shows the number of vertices in U on the boundaries of faces in
F≥3 to be at most 6|A|. In summary, |U∗
| ≤ 10|A| + 3Dom(G). Each vertex in
U∗
lies on the boundary of at most one face in F \ F∗
⊆ F2 and therefore has at
most one neighbor in U \ U∗
. Altogether, U contains at most 9|A| introspective
vertices and at most 2(10|A|+3Dom(G)) vertices that are not introspective.
Simpler Linear-Time Kernelization for Planar Dominating Set 189
4 Shrinking Iterations
4.1 Description
The main part of the kernelization is the shrinking iteration detailed below. It
takes as input an undirected planar graph G = (V, E), goes through three phases
that successively transform G into G1, G2 and G3, and returns G3. Take n = |V |
and, for i = 1, 2, 3, write Gi = (Vi, Ei).
The first two phases are simply near-twin reductions with different supports.
The support used in Phase 1 is a smallest set P ⊆ V with x∈P |NG[x]| ≥ n.
To describe the support used in Phase 2, we need some additional notation.
First, let Q be the union of P with the set of vertices in V1 without neighbors
in P. Q dominates G1, so we can form a partition {Star(x) : x ∈ Q} of V1 with
x ∈ Star(x) ⊆ NG1 [x] for all x ∈ Q. For all x ∈ Q, we call Star(x) a star and
x its center. For all u ∈ V1, let L(u) = {x ∈ Q : NG1 [u] ∩ Star(x) = Ø} be
the set of centers of stars represented in NG1 [u]. Moreover, for all x, y ∈ Q with
x = y, let wy(x) be the supremum, over all u ∈ V1 \ {x} with L(u) = {x, y},
of |NG1 [u] ∩ Star(x)| (equal to −∞ if there are no such u) and let gy(x) be a
vertex u that realizes the supremum (undefined if wy(x) = −∞). Phase 2 is a
near-twin reduction with support
R = Q ∪ {gy(x) : x, y ∈ Q, x = y and wy(x) > 0} ∪ {u ∈ V1 : |L(u)| ≥ 3} .
Let w(x) = y∈R\{x} |NG1 [y] ∩ Star(x)| for all x ∈ Q, S = {x ∈ Q : w(x) <
|Star(x)|} and T = NG2 (S) \ S. Phase 3 consists in removing every vertex in T
with at most one neighbor outside of S ∪ T and, for each x ∈ S, adding a new
degree-1 vertex with neighbor x. A nonobvious point is that since the definition
of S refers to G1, S is best computed before the near-twin reduction in Phase 2.
The three phases are summarized below in pseudo-code.
// Phase 1
P := a smallest subset of V with x∈P |NG[x]| ≥ n;
G1 := (V1, E1) := NearTwin Reduce(G, P);
// Phase 2
Q := P ∪ N0
G1
(P);
{Star(x) : x ∈ Q} := a partition of V1 with x ∈ Star(x) ⊆ NG1 [x] for all x ∈ Q;
R := Q ∪ {gy(x) : x, y ∈ Q, x = y and wy(x) > 0} ∪ {u ∈ V1 : |L(u)| ≥ 3},
where L(u) = {x ∈ Q : NG1 [u] ∩ Star(x) = Ø} for all u ∈ V1,
wy(x) = sup{|NG1 [u] ∩ Star(x)| : u ∈ V1 \ {x} and L(u) = {x, y}}
for all x, y ∈ Q with x = y and
gy(x) = some u ∈ V1 \ {x} with L(u) = {x, y}
and |NG1 (u) ∩ Star(x)| = wy(x)
for all x, y ∈ Q with x = y and wy(x) > 0;
S := {x ∈ Q : w(x) < |Star(x)|},
where w(x) = y∈R\{x} |NG1 [y] ∩ Star(x)| for all x ∈ Q;
G2 := (V2, E2) := NearTwin Reduce(G1, R);
190 T. Hagerup
// Phase 3
T := NG2 (S) \ S;
V3 := V2 \ {u ∈ T : |NG2 (u) \ (S ∪ T )| ≤ 1};
G3 := (V3, E3) := the graph obtained from G2[V3 ] by adding,
for each x ∈ S, a new degree-1 vertex with neighbor x;
return G3;
4.2 Correctness
It was proved already in Section 3.2 that near-twin reductions preserve the domination
number. Demonstrating the correctness of a shrinking iteration therefore
boils down to showing that Dom(G2) = Dom(G3).
Let D3 be a dominating set in G3. Since NG3 (V3 \ V2) = S and V2 \ V3 ⊆
NG2 (S), D2 = (D3 ∩ V2) ∪ S is a dominating set in G2. And since every vertex
in S has a degree-1 neighbor in G3 that does not belong to V2, |D2| ≤ |D3|.
Conversely, let D1 be a minimum dominating set in G1 (not in G2), chosen
to maximize |D1 ∩ Q| among all such sets. D1 does not contain any vertex
u ∈ V1 \ Q with |L(u)| = 1, since every such vertex could be replaced in D1
by the center of its star to obtain a minimum dominating set with one more
element in Q. Likewise, for all x, y ∈ Q with x = y, D1 contains at most one
vertex u ∈ V1 \{x} with L(u) = {x, y}, since two such vertices could be replaced
by x and y in D1 to obtain a minimum dominating set with at least one more
element in Q. R contains all u ∈ V1 with |L(u)| ≥ 3 and, for all x, y ∈ Q with
x = y such that L(u) = {x, y} for some u ∈ V1 \{x}, one such vertex u for which
|NG1 [u] ∩ Star(x)| is maximal. Because of this, it is not difficult to see that for
all x ∈ Q, w(x) = y∈R\{x} |NG1 [y]∩Star(x)| is an upper bound on the number
of vertices in Star(x) that are dominated by D1 \ {x}. If w(x) < |Star(x)| for
some x ∈ Q, therefore, x ∈ D1. Hence S ⊆ D1.
The argument in Section 3.2 that shows that Dom(D2) ≤ Dom(D1) also
proves that there is a minimum dominating set D2 in G2 with D1 ∩ R ⊆ D2 ∩ R
and therefore S ⊆ D2. Let D2 be such a set and obtain D3 ⊆ V3 from D2 by
replacing each vertex u ∈ D2 \ V3 by the vertices in NG2 (u) \ (S ∪ T ). In G3, D3
dominates the vertices in V3∩(S∪T ) (because S ⊆ D3), the vertices in V2\(S∪T )
(by the way D3 is obtained from D2), and the vertices in V3 \ V2 (again because
S ⊆ D3). Therefore D3 is a dominating set in G3. Since |NG2 (u) \ (S ∪ T )| ≤ 1
for each u ∈ V2 \ V3, |D3| ≤ |D2|. Thus Dom(G2) = Dom(G3).
4.3 Execution Time
It was proved already in Section 3.3 that a near-twin reduction can be executed
in linear time. To compute P, sort the vertices by their degrees and pick a
suitable suffix of the sorted sequence. To compute Q, let each vertex determine
membership in P for itself and its neighbors to know whether it should enter Q.
The computation of T from S and of V3 from S and T are similar, and the
construction of G3 from G2, V3 and S is easy.
Simpler Linear-Time Kernelization for Planar Dominating Set 191
In order to compute the partition {Star(x) : x ∈ Q}, let each vertex in V1 \ Q
choose a neighbor x ∈ Q and mark itself as belonging to Star(x). Subsequently
each vertex u ∈ V1 can determine the number |L(u)| of stars represented in
NG1 [u] and enter R if |L(u)| ≥ 3. If |L(u)| = 2, instead let u generate the tuples
(x, y, rx, u) (unless u = x) and (y, x, ry, u) (unless u = y), where L(u) = {x, y},
rx = |NG1 [u]∩Star(x)| and ry = |NG1 [u]∩Star(y)|. Sorting the tuples generated
in this way lexicographically with radix sort allows us to compute the final
constituent {gy(x) : x, y ∈ Q, x = y and wy(x) > 0} of R in O(n) time: For all
x, y ∈ Q with x = y and wy(x) > 0, gy(x) is the fourth component of the last
tuple in the sorted sequence with first component x and second component y.
The computation of S, finally, is made easy by the alternative characterization
w(x) = u∈Star(x) |NG1 [u]∩(R\{x})|, for all x ∈ Q, which shows that w(x) can
be obtained for all x ∈ Q by summing over the vertices in Star(x) a quantity that
is computable for all vertices in V1 in O(n) time. The application of a shrinking
iteration to an n-vertex graph therefore takes O(n) time.
4.4 Reduction Progress
Take k = Dom(G) and note that |P| ≤ k. Let z = |V | − |V1| = |N2
G(P)| −
|N2
G1
(P)| ≥ 0 be the decrease in the number of vertices achieved by Phase 1. By
Lemma 4, |N2
G1
(P)| = O(k), so |N2
G(P)| = z + O(k). Lemma 3 now shows that
|N0
G(P)| ≤ |N2
G(P)|+O(k) = z+O(k). And then |Q| = |P|+|N0
G(P)| = z+O(k).
Let R≥3 = {u ∈ V1 \ Q : |L(u)| ≥ 3}. We want to show that |R≥3| = O(|Q|),
which, by Lemma 1(a), will imply that |R| ≤ |Q| + 6|Q| + |R≥3| = O(z + k). To
this end, recall that for t ∈ N, a t-coloring of an undirected graph H = (VH, EH)
is a mapping h : VH → {1, . . . , t} such that for every {u, v} ∈ EH, h(u) = h(v).
Lemma 1(a) can easily be used to show that every undirected planar graph has
a 6-coloring, and the famous four-color theorem (see, e.g., [10]) states that every
undirected planar graph in fact has a 4-coloring. Therefore let h be a t-coloring
of G1 for some t ≤ 6 and fix j ∈ {1, . . ., t}. Consider the graph obtained from G1
by merging each vertex u ∈ V1 \ Q with h(u) = j into the center of its star. In
the resulting graph every vertex u ∈ R≥3 with h(u) = j has at least 3 neighbors
in Q. Therefore, by Lemma 2(b), |{u ∈ R≥3 : h(u) = j}| ≤ 2|Q|, and altogether
|R≥3| ≤ 2t|Q| = O(|Q|).
Let W = x∈Q w(x). Intuitively, W is (approximately) the number of vertices
that, by virtue of having a neighbor in R other than the center of their star, can
be “saved” from entering T . Under the assumption that z is small, so that
Phase 1 removes only few vertices, the following holds: If W is small, T is large,
and Phase 3 succeeds in removing a large number of vertices in T . On the other
hand, if W is large, then many vertices have two neighbors in R, and the neartwin
reduction with support R in Phase 2 removes many vertices. The rest of
this section serves to formalize and prove these claims. First note that
192 T. Hagerup
|NG1 [S]| ≥
x∈Q: w(x)<|Star(x)|
|Star(x)| ≥
x∈Q: w(x)<|Star(x)|
(|Star(x)| − w(x))
≥
x∈Q
(|Star(x)| − w(x)) = |V1| − W .
Thus at most W vertices in G1 do not belong to NG1 [S]. This implies that at
most W vertices in G2 do not belong to NG2 [S] = S ∪T . And this in turn means
that |V2 \ T | ≤ W + |S|. A vertex in T is included in V3 only if it has at least
two neighbors outside of T in addition to the center of its star. By Lemma 2(b),
therefore, |V3 | ≤ |V2 \ T | + 2|V2 \ T | ≤ 3(W + |S|) and |V3| = |V3 | + |S| ≤
3W + O(z + k). This concludes the analysis for small W. Take U = V1 \ R. The
analysis for large W depends on the following characterization of W.
W =
x∈Q y∈R\{x}
|NG1 [y] ∩ Star(x)| =
y∈R x∈Q\{y}
|NG1 [y] ∩ Star(x)|
=
y∈R
|NG1 [y]| −
y∈Q
|Star(y)| =
y∈R
|NG1 (y)| − |U| .
Let H be the bipartite subgraph of G1 induced by the set of edges with one
endpoint in R and one endpoint in U. The total degree y∈R |NG1 (y)| in G1
of the vertices in R overcounts the number of edges in H by twice the number
of edges between vertices in R, i.e., according to Lemma 1(a), by at most 6|R|.
Therefore H has at least |U| + W − 6|R| edges. Every vertex in U has at least
one incident edge in H, namely to the center of its star. With ni = |Ni
G1
(R)|
for i = 1, 2, . . . , this means that
∞
i=1(i − 1)ni ≥ W − 6|R|. But then, by
Lemma 2(a),
∞
i=2
ni ≥ W − 6|R| −
∞
i=3
(i − 2)ni ≥ W − 6|R| − 2|R| = W − O(z + k) .
After Phase 2, by Lemmas 4 and 2(b), the number of vertices with two or more
neighbors in R is O(z+k). Phase 2 therefore reduces the number of vertices with
two or more neighbors in R from W −O(z+k) to O(z+k), i.e., by W −O(z+k).
In summary, for a certain constant c > 0, Phase 1 and Phase 2 reduce the
number of vertices by z and by at least max{W −c(z +k), 0}, respectively, while
the number of vertices left after Phase 3 is bounded by 3W + c(z + k). The
complete shrinking iteration therefore reduces the number of vertices by at least
max{z, W − c(z + k), n − 3W − c(z + k)} .
A simple case analysis shows that if n ≥ 16ck, then one of the three arguments
of the maximum above is Ω(n): Without loss of generality, z ≤ n/(16c) and
therefore c(z + k) ≤ n/16 + n/16 = n/8. If W ≥ n/4, the second term is at least
n/4 − n/8 = n/8, and if not, the third term is at least n − 3n/4 − n/8 = n/8.
A shrinking iteration that starts with at least 16ck vertices therefore reduces
the number of vertices by at least a constant factor.
Simpler Linear-Time Kernelization for Planar Dominating Set 193
5 The Complete Algorithm
The complete kernelization inputs an undirected n-vertex planar graph G and
consists in applying repeated shrinking iterations to G until the number of vertices
no longer drops at least at the rate established in the analysis in the previous
section. Since our upper bound on the running time of successive iterations forms
a geometric series, the total running time is O(n). Every iteration preserves the
domination number, so the final graph has domination number Dom(G), and it
is planar and contains O(Dom(G)) vertices.
References
1. Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for
Dominating Set. J. ACM 51(3), 363–384 (2004)
2. van Bevern, R., Hartung, S., Kammer, F., Niedermeier, R., Weller, M.: Lineartime
computation of a linear problem kernel for Dominating Set on planar graphs.
In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 194–206.
Springer, Heidelberg (2012)
3. Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos,
D.M.: (Meta) kernelization. In: FOCS, pp. 629–638. IEEE Computer Society
(2009)
4. Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization:
Lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077–
1106 (2007)
5. Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar
graphs. In: Arge, L., Cachin, C., Jurdzi´nski, T., Tarlecki, A. (eds.) ICALP 2007.
LNCS, vol. 4596, pp. 375–386. Springer, Heidelberg (2007)
6. Jansen, B.: Kernelization for Maximum Leaf Spanning Tree with positive vertex
weights. In: Calamoneri, T., D´ıaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 192–
203. Springer, Heidelberg (2010)
7. Kammer, F.: A linear-time algorithm to find a kernel for the Rooted Leaf Outbranching
problem (2011) (manuscript)
8. Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex
set, and k-disjoint cycles on plane and planar graphs. In: Kuˇcera, L. (ed.) WG
2002. LNCS, vol. 2573, pp. 282–295. Springer, Heidelberg (2002)
9. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University
Press, Oxford (2006)
10. Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. Dover Publications,
Inc., Mineola (1988)
11. Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized
cluster editing problems. Theory Comput. Syst. 44(1), 91–104 (2009)