Linear Kernels for Separating a Graph into
Components of Bounded Size∗
Mingyu Xiao1
1

School of Computer Science and Engineering
University of Electronic Science and Technology of China,China
myxiao@gmail.com

arXiv:1608.05816v1 [] 20 Aug 2016

Abstract
Graph separation and partitioning are fundamental problems that have been extensively studied
both in theory and practice. The p-Size Separator problem, closely related to the Balanced
Separator problem, is to check whether we can delete at most k vertices in a given graph G
such that each connected component of the remaining graph has at most p vertices. This problem
is NP-hard for each fixed integer p ≥ 1 and it becomes the famous Vertex Cover problem
when p = 1. It is known that the problem with parameter k is W[1]-hard for unfixed p. In this
paper, we prove a kernel of O(pk) vertices for this problem, i.e., a linear vertex kernel for each
fixed p ≥ 1. In fact, we first obtain an O(p2 k) vertex kernel by using a nontrivial extension
of the expansion lemma. Then we further reduce the kernel size to O(pk) by using some ‘local
adjustment’ techniques. Our proofs are based on extremal combinatorial arguments and the
main result can be regarded as a generalization of the Nemhauser and Trotter’s theorem for the
Vertex Cover problem. These techniques are possible to be used to improve kernel sizes for
more problems, especially problems with kernelization algorithms based on techniques similar to
the expansion lemma or crown decompositions.
1998 ACM Subject Classification Dummy classification – please refer to http://www.acm.org/
about/class/ccs98-html
Keywords and phrases Linear Kernels; Graph Algorithms; FPT; Balanced Separators
Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p

1

Introduction

Finding optimal separators and cuts in graphs is a classical topic in combinatorial optimization.
Different versions of graph separation and graph cut problems have been studied extensively
from the perspective of approximation algorithms and heuristics. In recent years there has
been an increase of interest in parameterized algorithms of such problems [6, 8, 11, 17, 22,
24, 25, 26, 20, 28, 31].
Graph separators play a mysterious and not yet fully understood role in parameterized
algorithms of certain problems. Proving that Bipartization [29], Multicut [6, 26], k-Way
Cut [22], Directed Feedback Vertex Set [8], Almost 2-Sat [28] and Minimum
Bisection [11] are fixed-parameter tractable (FPT) answered longstanding open questions
in parameterized complexity, and in each case the algorithm relies on a non-obvious use of
separators.
Balanced separator is one of the most important topics [15, 16, 17, 24]. The Balanced
Separator problem is to check whether there is a vertex separator of size k that partitions a
∗

Supported by NFSC of China under the Grant 61370071.

© M. Xiao;
licensed under Creative Commons License CC-BY
Conference title on which this volume is based on.
Editors: Billy Editor and Bill Editors; pp. 1–16
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

2

Kernels for Separating a Graph into Components of Bounded Size

given n-vertex graph into connected components of size at most αn (0 < α < 1). This vertex
separator is also called an α-separator. Balanced Separator can be described in another
way, which is called the p-Size Separator problem. A p-size separator of an n-vertex graph
is a vertex separator of size k that partitions the graph into connected components of size at
most p. We can see that a p-size separator is an α-separator and vice versa if p = αn.
Balanced separators are used in applications of designing divide-and-conquer algorithms
and parallel algorithms for a large number of graph problems. Enright and Meeks [14]
addressed some applications of these separators from real life, such as to restrict the size of an
epidemic. Minimum Bisection [11] is also equivalent to finding a balanced edge-separator.
There are several approximation algorithms to find small balanced separators [15, 16, 17, 5]. In
terms of parameterized algorithms, the problem with parameter k is W[1]-hard for unbounded
size of the components (i.e., p or αn is not a constant) [24, 17]. A trivial branch-and-reduce
algorithm that tries all p + 1 possibilities for a connected subgraph of p + 1 vertices gets the
running time bound of O∗ ((p + 1)k ), which implies that the problem with parameter k is
FPT for each fixed p. In terms of kernelizations, a kernel of O(p2 k 2 ) vertices is known for
p-Size Separator [13]. This is a quadratic vertex kernel for each fixed p. This paper will
give the first linear vertex kernel for this problem. Our main result is Theorem 2, which can
be regarded as a generalization of the Nemhauser and Trotter’s local optimization theorem
for Vertex Cover, and we use only extremal combinatorial arguments to prove it.
When p = 1, p-Size Separator becomes Vertex Cover. Nemhauser and Trotter [27]
proved a famous theorem (NT-Theorem) for Vertex Cover.
I Theorem 1. [NT-Theorem] For an undirected graph G = (V, E) of n = |V | vertices and
√
m = |E| edges, there is an O( nm)-time algorithm to compute two disjoint vertex subsets C
and I of G such that for any minimum vertex cover K of the induced subgraph G[V \ (C ∪ I)],
K ∪ C is a minimum vertex cover of G and
|V \ (C ∪ I)| ≤ 2|K|.
This theorem was proved by constructing an algorithm based on linear programming relaxation [27] and the algorithm can be used to reduce the size of the input graph by
possibly finding partial solution. The NT-Theorem has great applications in approximation
algorithms [4, 21, 23] and parameterized algorithms [7, 2]. We can see that V \ I is a
2-approximation solution and G[V \ (C ∪ I)] is a 2k-vertex kernel with k being the size of
the vertex cover. Due to NT-Theorem’s practical usefulness and theoretical depth in graph
theory, it has attracted numerous further studies and follow-up work [18, 3, 9, 2, 32]. In this
paper, we will prove the following local optimization theorem similar to NT-Theorem for
p-Size Separator.
I Theorem 2.
m = |E| edges,
C and I of G
G[V \ (C ∪ I)],

[Our result] For an undirected graph G = (V, E) of n = |V | vertices and
there is an O(n4 m)-time algorithm to compute two disjoint vertex subsets
such that for any minimum p-size separator K of the induced subgraph
K ∪ C is a minimum p-size separator of G and

|V \ (C ∪ I)| ≤ 9p|K|.
Theorem 2 implies a kernel of 9pk vertices for p-Size Separator with k being the size of
the solution, which is linear in k for any constant p ≥ 1. Dell and van Melkebeek [12] proved
that Vertex Cover and some related problems do not have kernels consisting of O(k 2− )
edges for any constant  > 0 unless the polynomial-time hierarchy collapses. This also implies
that linear size would be the best possible bound on the number of vertices in any kernel

M. Xiao

of p-Size Separator for each fixed p ≥ 1. It is also known that p-Size Separator with
parameter k is W[1]-hard for unbounded p [24, 17]. Then it is unlikely to remove p from the
size function of any kernel for this problem. These two hardness results also imply that our
kernel result is somewhat close to optimal.
To prove Theorem 2, we will use a decomposition, called ‘weighted crown decomposition’.
It can be regarded as an extension of the crown decomposition for Vertex Cover [1, 10] as
well the structure under the expansion lemma (Lemma 8 in [19]). To find a weighted crown
decomposition, we need to consider a bipartite graph and find vertex-disjoint stars in it
with leaves from one side and centers from another side (also having some other properties).
This technique has been used to obtain kernels in many problems [30, 18, 19, 32]. The
expansion lemma [19] provides a condition for the existence of such star packings in bipartite
graphs. For our problem and the weighted crown decomposition, we need to consider a
vertex-weighted bipartite graph and find stars in it. So we prove a lemma (Lemma 5) for
the weighted case. We call this lemma the weighted expansion lemma for convenience. We
would like to mention that when the graph is a weighted graph, it will become hard to
compute such star packings and we may need to relax the size of the bipartite graph to obtain
polynomial time algorithms. So our algorithm for weighted expansion lemma is different
from that for normal expansion lemma, not just a simple extension. By using the weighted
expansion lemma, we can obtain a kernel of size O(p2 k). A more interesting part should be
the improvement from O(p2 k) to O(pk). We will use some techniques to iteratively adjust
some local structures. Finally, we can apply the weighted expansion lemma to only a (small)
part of the original bipartite graph and then get the bound of O(pk).
Some figures and proofs are moved to Appendix due to space limitation.

2

Preliminaries

Let G = (V, E) denote a graph with vertex set V and edge set E. We will use n and m to
denote the number of vertices and edges of our input graph G, respectively. We also use
γp (G) to denote the size of a minimum p-size separator of G for any integer p ≥ 1. For a
vertex subset V 0 ⊆ V , the subgraph induced on V 0 is denoted by G[V 0 ] and G[V \ V 0 ] may
be written as G \ V 0 . For a graph G0 , we use V (G0 ) and E(G0 ) to denote the vertex set and
edge set of G0 , respectively. We say that a vertex set V 0 (resp., a subgraph G0 ) is adjacent
to a vertex v 6∈ V 0 (resp., v 6∈ V (G0 )) if there is at least one edge between v and a vertex in
V 0 (resp., G0 ). For a vertex (resp., edge) subset V0 , a vertex (resp., edge) in V0 is called a
V0 -vertex (resp., V0 -edge). A bipartite graph with edges between two vertex sets V1 and V2
is denoted by (V1 , V2 , E12 ), where E12 is the set of edges between V1 and V2 . A set {v} of a
single element may be simply written as v.
For an integer d ≥ 1, a connected subgraph with d vertices is called a d-subgraph. A set
S of vertex-disjoint d-subgraphs is called a d-subgraph packing. A star with exactly d + 1
vertices is called a d-star. The unique vertex of degree > 1 in a d-star with d > 1 is called
the center of the star and all other degree-1 vertices are called the leaves of the star. For a
1-star, any vertex can be regarded as a center and the other vertex as a leaf. A star with
a center v is also called a star centered at v. For two disjoint vertex sets V1 and V2 , a star
with the center in V1 and all leaves in V2 is called a star from V1 to V2 . A full star packing
from V1 to V2 is a star packing of size equal to |V1 |. A star with vertex-weighted is called a
(p1 , p2 )-star if the total vertex weight in the star is at least p1 and at most p2 . In this paper,
we will always set the vertex weight zero for the center of a star. So a weight (p1 , p2 )-star
will mean a star with total leaf weight at least p1 and at most p2 .

3

4

Kernels for Separating a Graph into Components of Bounded Size

3

The weighted expansion lemma and an O(p2 k) kernel

We give an algorithm that returns a kernel of O(p2 k) vertices for p-Size Separator. We
mainly use the weighted expansion lemma (Lemma 5) to obtain this result.
For a graph G = (V, E) with a partition (A, B = V \ A), we define the auxiliary bipartite
graph HG = (A0 , B 0 , E 0 ) of G as follows: each vertex a ∈ A0 is corresponding to a connected
component Ca in the induced graph G[A]; the weight w(a) of a ∈ A0 is the number of vertices
in Ca ; B 0 is a copy of B, the weight w(b) of each b ∈ B 0 is 0, and a vertex a ∈ A0 is adjacent
to a vertex b ∈ B 0 if and only if there is a vertex in Ca adjacent to b ∈ B in the graph G.
Note that the auxiliary bipartite graph is a vertex-weighted graph. Please refer to Figure 5
in Appendix A for an illustration for auxiliary bipartite graphs. This graph will be frequently
used in our algorithms and analysis.
I Definition 3. [Weighted Crown Decomposition] For an integer p ≥ 1, a p-weighted
crown decomposition of a graph G = (V, E) is a partition of the vertex set of G into three
sets I, C and J such that
(1) there are no edges between I and J,
(2) each connected component in the induced graph G[I] has at most p vertices, and
(3) there is a full (p, ∞)-star packing from C 0 to I 0 in the auxiliary bipartite graph HG =
(I 0 , C 0 , E 0 ) of G[I ∪ C] with partition (I, C).
Figure 6 in Appendix A gives an illustration for weighted crown decompositions and
normal crown decompositions.
I Lemma 4. Let (I, C, J) be a p-weighted crown decomposition of a graph G = (V, E). Then
(I, C) satisfies the local optimality condition in Theorem 2, i.e., K ∪ C is a minimum p-size
separator of G for any minimum p-size separator K of the induced subgraph G[J].
A proof for this lemma can be found in Appendix B. Based on Lemma 4, we can switch
to find weighted crown decompositions instead of computing the sets I and C in Theorem 2
directly. Here arises a question how to find weighted crown decompositions of a graph?
I Lemma 5. [Weighted Expansion Lemma] Let p ≥ 1 be an integer and (A, B = V \ A)
be a partition of the vertex set of a graph G = (V, E) such that each connected component of
G[A] has at most p vertices. There are sets I ⊆ A and C ⊆ B such that (I, C, J = V \(I ∪C))
is a p-weighted crown decomposition of G and (I, C) satisfies the size condition:
|A \ I| ≤ (2p − 1)|B \ C|.
Furthermore, (I, C) can be computed in O(|V |2 |E|) time.
We mainly use an algorithm crown(G, B, p) to prove Lemma 5. The algorithm crown(G, B, p)
takes a graph G = (V, E), a vertex subset B ⊆ V and an integer p ≥ 1 as the input, and
outputs two sets I ⊆ V \ B and C ⊆ B such that (I, C, J = V \ (I ∪ C)) is a p-weighted crown
decomposition of G. The first step of crown(G, B, p) is to compute the auxiliary bipartite
graph HG = (A0 , B 0 , E 0 ) of G with partition (V \ B, B). In the following steps, the algorithm
mainly deals with the graph HG and always maintains an edge set M of HG such that each
vertex in A0 has exactly one edge in M (then the edges in M will form a star packing from
B 0 to A0 ). Such an edge set M is obtained initially by, for each vertex v ∈ A0 , selecting an
arbitrary edge incident on v to M . It is done in Step 2. In the next steps, we may modify
M by replacing an M -edge incident on a vertex v ∈ A0 with another edge incident on v ∈ A0 .
This operation will not destroy the above property of M .

M. Xiao

5

For a fixed M , we define the following notations. A path P in HG that alternates between
edges in M and edges not in M is called an M -alternating path. An M -alternating path is
called a strong M -alternating path from a vertex v to u if the first edge (the edge incident on
v) in P is in M . The edges in M form a star packing Q from B 0 to A0 . We partition Q into
three subsets Q1 , Q2 and Q3 , where Q1 is the set of stars with total vertex weight at least
2p, Q2 is the set of stars with total vertex weight at least p but less than 2p, and Q3 is the
set of stars with total vertex weight less than p. Let A0i = A0 ∩ V (Qi ) and Bi0 = B 0 ∩ V (Qi )
for i = 1, 2, 3.
There is a full (p, ∞)-star packing from B10 ∪ B20 to A01 ∪ A02 in HG . It is possible to
use B10 ∪ B20 and A01 ∪ A02 to construct C and I in Lemma 5. In fact, if there is no strong
M -alternating path from a vertex in B10 to a vertex in B30 then we can find a subset of
A01 ∪ A02 and a subset of B10 ∪ B20 to identify a solution (I, C) (this will be proved later). Our
idea is to destroy M -alternating paths from vertices in B10 to vertices in B30 by iteratively
replacing an M -edge incident on a vertex v ∈ A0 with another edge incident on v ∈ A0 . One
may think that if there is an M -alternating path P from a B10 -vertex to a B30 -vertex, we
can replace M ∩ E(P ) by E(P ) \ M in M to destroy P as what we do for unweighted cases.
However, this replacement may create new B10 -vertices and cause some trouble in the analysis.
To avoid possible endless loops, we need to use a ‘hierarchical structure’ of HG .
In the hierarchical structure, we classify some vertices in HG into different levels based
on M :
(i) all vertices in B10 are in level-0;
(ii) for each odd i ≥ 1, a vertex is in level-i if and only if it is adjacent to a vertex in
level-(i − 1) via an M -edge;
(iii) for each even i ≥ 1, a vertex is in level-i if and only if it has not be assigned to a level
before and it is adjacent to a vertex in level-(i − 1) via an edge not in M .
The hierarchical structure can be built in linear time via a breadth-first search (BFS).
Figure 1 gives an illustration for the hierarchical structure. Note that some vertices may
not be included in the hierarchical structure. These vertices can be simply ignored in our
algorithm.

A′1

A′2

A′3

a1

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
b1

b2
b1

b2
B′1

b3

b4
B′2

b5

b6
B′3

Level: 0

H G = ( A′, B′, E ′)

a2
a3
a4
a5

a7
b3

b4

b5

a11

4

5

a9
a10

a6

1

a8

2

3

The hierarchical structure

Figure 1 Graph HG and the hierarchical structure

A strong M -alternative path containing exactly i + 1 vertices from a vertex v0 in level-0
to a vertex u in level-i is called a pure M -alternative path from v0 to u. It is easy to see the
following properties in a hierarchical structure:

6

Kernels for Separating a Graph into Components of Bounded Size

Input: A graph G = (V, E), a vertex subset B ⊆ V and an integer p ≥ 1 such that each
connected component in G[V \ B] has size at most p.
Output: Two sets I ⊆ V \ B and C ⊆ B such that (I, C, J = V \ (I ∪ C)) is a p-weighted
crown decomposition of G.
1. Let A = V \ B and compute the auxiliary bipartite graph HG = (A0 , B 0 , E 0 ) of G with
partition (A, B).
2. For each vertex v ∈ A0 , arbitrarily select an edge incident on v and include the edge to
M.
3. According to M , compute A01 , A02 , A03 , B10 , B20 and B30 , and the hierarchical structure.
4. If {there exists a redundant vertex},
then eliminate a redundant vertex and goto Step 3.
5. Let C 0 be set of B 0 -vertices connected to a B10 -vertex via a strong M -alternating path
(also include the vertices in B10 themselves). Let I 0 be the set of A0 -vertices adjacent to a
vertex in C 0 via an edge in M .
6. Let C be the set of vertices in B in G corresponding to the vertices in C 0 in HG and I be
the set of vertices in the components of G[A] corresponding to the vertices in I 0 in HG .
7. Return (I, C).

Figure 2 Algorithm crown(G, B, p)

(P1) for each even number i all vertices in level-i are B 0 -vertices, and for each odd number i
all vertices in level-i are A0 -vertices;
(P2) a vertex appears in the hierarchical structure if and only if there is a strong M -alternative
path from a vertex in level-0 to it;
(P3) for any vertex in the hierarchical structure, there is a pure M -alternative path from a
vertex in level-0 to it.
A vertex v in a hierarchical structure is called a redundant vertex if
(i) it is in level-i with an odd number i, and
(ii) there is a neighbor u of v in level-(i + 1) such that after replacing the M -edge incident
on v with vu in M , the vertex u under the new edge set M is not a B10 -vertex.
The operation of eliminating a redundant vertex v is to update M by replacing the M -edge
incident on v with vu, where u is the vertex defined in the above definition of redundant
vertices.
Our algorithm crown(G, A, p) is simple, the only main step of which is to eliminate
redundant vertices. Once there are no redundant vertices left, we let C be the set of all
vertices reachable from B1 via strong M -alternating paths, including B1 , and let I be the
leaf neighbors of C that participate in M . The whole algorithm is described in Figure 2.
I Lemma 6. If there is no redundant vertex, then there is no strong M -alternating path
from a B10 -vertex to a B30 -vertex.
In fact, if there is a strong M -alternating path P from a B10 -vertex to a B30 -vertex u, we
can prove that the vertex v adjacent to u in P is a redundant vertex. Full proofs for the
following lemmas can be found in Appendix B.
I Lemma 7. Algorithm crown(G = (V, E), B, p) runs in O(|V |2 |E|) time.

M. Xiao

7

I Lemma 8. Algorithm crown(G, B, p) returns two sets I ⊆ V \ B and C ⊆ B such that
(I, C, J = V (G) \ (I ∪ C)) is a p-weighted crown decomposition of G.
I Lemma 9. The two sets I and C returned by crown(G, B, p) satisfy the following size
condition:
|V \ (B ∪ I)| ≤ (2p − 1)|B \ C|.

(1)

Lemma 7, Lemma 8 and Lemma 9 directly imply Lemma 5. We can get a kernel of
2p(p + 1)k vertices for p-Size Separator by Lemma 5. Our algorithm first selects a
maximal packing of connected (p + 1)-subgraphs and let B denote the vertex set of it. Then
|B| ≤ (p + 1)γp (G). If the size of A = V \ B is greater than (2p − 1)|B|, we just reduce the
graph by removing the two sets returned by crown(G, B, p). So we can bound the number of
vertices in the graph by (2p − 1)|B| + |B| ≤ 2p(p + 1)γp (G).
I Lemma 10. There is an algorithm that runs in O(mn2 ) time to return a kernel of at most
2p(p + 1)k vertices for p-Size separator.

4

The proof of Theorem 2 and an improved kernel

Lemma 5 in Section 3 can be used to reduce the input graph with a vertex partition
(A = V \ B, B), where B is taken as the vertex set of a packing of connected (p + 1)subgraphs. The size of B is at most (p + 1)γp (G). Lemma 5 guarantees that the size of A
is O(p|B|). Then we get a bound of O(p2 γp (G)) on the graph size for our problem. In this
section, we will improve the bound from O(p2 γp (G)) to O(pγp (G)) by proving Theorem 2.
Our initial idea to get the improvement is, not to apply Lemma 5 on the whole graph G,
but to find two subsets A1 ⊆ A and B1 ⊆ B and apply Lemma 5 only to the subgraph
G[A1 ∪ B1 ]. If |A \ A1 | + |B \ B1 | ≤ pγp (G) and |B1 | ≤ γp (G), then we may be able to bound
the size of A1 by O(p|B1 |) = O(pγp (G)) and the size of the whole instance by O(pγp (G)).
The crucial parts of this method are to find the partition (A, B) and the two subsets A1 and
B1 . In fact, our algorithm does not really find the two subsets A1 and B1 . We will still apply
Lemma 5 on the whole graph G with partition (A, B). It is necessary to find I and C only
in A1 and B1 for two subsets A1 and B1 satisfying the above properties. Before introducing
the main algorithm, we first derive a property and sub-algorithm that will be used later.

4.1

The local adjustment property

We introduce a property, which will be used to find the partition (A, B) of the input graph.
Recall that a vertex set in a graph is a p-size separator if after deleting it each connected
component of the remaining graph has at most p vertices. For a p-size separator containing
only one vertex, the unique vertex in it is also called a p-size separator vertex.
I Theorem 11. [Local Adjustment Property] Let p ≥ 1 be an integer and G = (V, E)
be a connected graph of more than 3p vertices. If G has no p-size separator vertex, then there
are two vertex-disjoint subsets V1 , V2 ⊆ V such that |Vi | ≥ p + 1 and the induced graph G[Vi ]
is a connected graph for i = 1, 2. Furthermore, the two subsets V1 and V2 can be computed in
O(p|E|) time.
To prove Theorem 11, we show that the following algorithm connect(G, p) correctly
computes the vertex subsets V1 and V2 .
First, we show that after each iteration of Step 2, G[V1 ] and G[V2 ] are two connected
graphs. Since V2 is taken as the vertex set of a connected component of G \ V1 in Step 2.2,

8

Kernels for Separating a Graph into Components of Bounded Size

Input: A connected graph G = (V, E) of more than 3p vertices having no p-size separator
vertex, and an integer p > 0.
Output: Two vertex-disjoint subsets V1 , V2 ⊆ V such that |Vi | ≥ p + 1 and the induced
graph G[Vi ] is a connected graph for i = 1, 2.
1. Initially V1 ← ∅ and V2 ← V .
2. If { |V1 | ≤ p}, do
2.1 Select a vertex v ∈ N (V1 ) (here we let N (∅) = V ) such that V1 ∪ {v} is not a p-size
separator and let V1 ← V1 ∪ {v}.
2.2 Let U be a maximum connected component in G \ V1 , V2 ← V (U ) and V1 ← V \ V2 .
3. Else return (V1 , V2 ).

Figure 3 Algorithm connect(G, p)

we know that G[V2 ] is a connected graph after executing Step 2.2. Assume that G[V1 ] is a
connected graph before executing an iteration of Step 2, which holds before the first execution
of Step 2 since we regard an empty graph as connected. We only need to show that G[V1 ] is
still a connected graph after executing an iteration of Step 2. Let V10 = V1 and V20 = V2 at the
time before executing an iteration of Step 2. Then both of G[V10 ] and G[V20 ] are connected
graphs. After executing Step 2.1, G[V1 = V10 ∪ {v}] is still connected since we select v from
N (V10 ). Since G[V20 ] is a connected graph, each connected component of G[V20 \ {v}] has
some vertex adjacent to v. Then for any connected component U0 of G[V20 \ {v}], the graph
G[V20 \ V (U0 )] is still connected. After Step 2.2, V1 = V \ V (U ) = (V10 ∪ {v}) ∪ (V20 \ V (U ))
for a connected component U of G[V20 \ {v}]. Thus, G[V1 ] is still a connected graph.
Second, we show that the vertex v in Step 2.1 always exists, which is important for the
correctness of the algorithm. It is clear that (V1 , V2 ) is a partition of the vertex set V before
or after an execution of Step 2. We still let V10 = V1 and V20 = V2 at the time before executing
an iteration of Step 2. Then both of G[V10 ] and G[V20 ] are connected graphs by the above
analysis. We know that N (V10 ) 6= ∅ since G is a connected graph. Let v0 be an arbitrary
vertex in N (V10 ). Assume that V10 ∪ {v0 } becomes a p-size separator of G. Let U = {Ui } be
the set of connected components of G \ (V10 ∪ {v0 }). Then each Ui contains at most p vertices.
Since v0 is not a p-size separator vertex of G, we know that there is a vertex v00 in Ui0 for
some Ui0 ∈ U such that v00 is adjacent to a vertex in V10 , i.e., v00 ∈ N (V10 ). Next, we show that
V10 ∪ {v00 } is impossible to be a p-size separator again. Let W = {Wi } be the set of connected
components of G \ (V10 ∪ {v00 }). Note that v00 ∈ Ui0 and then (∪i6=i0 Ui ) ∪ {v0 } ⊆ Wi1 for some
Wi1 ∈ W. If V10 ∪ {v00 } is a p-size separator, then |(∪i6=i0 Ui ) ∪ {v0 }| ≤ |Wi0 | ≤ p. Therefore,
|V | = |V10 | + |V20 | ≤ p + |(∪i6=i0 Ui ) ∪ {v0 } ∪ Ui0 | ≤ p + p + p = 3p, a contradiction with the
graph G having more than 3p vertices. So V10 ∪ {v00 } is impossible to be a p-size separator.
The vertex v in Step 2.1 always exists and it can be found in linear time by checking at most
two vertices in N (V10 ).
Finally, we are ready to prove the correctness of the whole algorithm and analyze the
running time. After Step 2, we have that |V1 | ≥ p + 1. Note that in Step 2.1, the vertex v is
selected such that V1 ∪ {v} is not a p-size separator vertex and in Step 2.2, U is selected as
a component of maximum size. So we know that |V2 | = |V (U )| ≥ p + 1. We have proved
that after Step 2, G[V1 ] and G[V2 ] are two connected graphs. Then the two sets V1 and V2
returned in Step 3 satisfy the requirement. Next, we only need to show that the algorithm

M. Xiao

always stops in O(p|E|) time. We have shown that the vertex v in Step 2.1 can be found in
O(|E|) time. Then Step 2 can be executed in O(|E|) time. No vertex in V1 will be moved
out of V1 and in each iteration of Step 2 at least one new vertex in included to V1 . So Step 2
can be executed for at most p + 1 iterations and the algorithm always stops and runs in
O(p|E|) time.
In fact, the bound 3p + 1 on the number of vertices in Theorem 11 is tight. For if a graph
has only 3p vertices but has no p-size separator vertex, it may not have two vertex subsets
V1 and V2 satisfying the conditions in Theorem 11. A graph of a triangle is an example for
p = 1.

4.2

The main algorithm

Our algorithm is still based on a vertex partition (A, B = V \ A) of the graph. For a subset
B ∗ ⊆ B, a component of G[A] is called a B ∗ -attached component if the component has a
vertex adjacent to some vertex in B ∗ . We use G(B ∗ ) to denote the graph induced by B ∗
together with the vertices of all B ∗ -attached components. We call G(B ∗ ) the B ∗ -associate
subgraph.
In our algorithm, the partition (A, B) is not fixed. However, through the algorithm, B
always satisfies the base-properties:
(Q1) B is a p-size separator, i.e., each connected component of G[A] has at most p vertices.
(Q2) B is the union of several pairwise disjoint vertex sets, called bases, each of which is either
a set of a single vertex or the vertex set of a (p + 1)-subgraph. A base of a single vertex
is called a single-base and a base of p + 1 vertices is called a group-base.
(Q3) The number of bases in B does not decrease in the algorithm and it is at most γp (G).
(Q4) Let HG = (A0 , B 0 , E 0 ) be the auxiliary bipartite graph of G with partition (A, B). Let
Bs0 ⊆ B 0 be the subset of vertices in B 0 corresponding to the set of vertices in single-bases
in B. There is a full (4p, ∞)-star packing from Bs0 to A0 .
Figure 7 in Appendix A gives an illustration for such partition (A, B) with the baseproperties. Initially B contains only group-bases. For this case, B is the vertex set of a
maximal (p + 1)-subgraph packing and the base-properties clearly hold. Then the algorithm
tries to increase either the number of bases in B by replacing a group-base with two groupbases or the number of single-bases in B by replacing a group-base with a single-base. Let
S be a group-base in the current B (may have always contained some single-bases). We
consider the S-associate subgraph G(S).
Case 1. G(S) has at least 3p + 1 vertices and has no p-size separator vertex: we call the
group-base S extendable. For this case, G(S) satisfies the conditions of the input graph of
connect. We can get two connected components Sn1 and Sn2 of p + 1 vertices in G(S) by
using Theorem 11 and the algorithm connect. Then we replace S with two group-bases Sn1
and Sn2 in B. Furthermore, we can extend each single-base to a group-base in B (keeping
all bases pairwise vertex-disjoint). The reason why we need to replace single-bases with
group-bases is to show that the total number of bases in B is at most γp (G) in (Q3). We
also need (Q4), because it is crucial for us to extend single-bases to group-bases keeping all
bases pairwise vertex-disjoint. In our algorithm, when we find an extendable group-base,
we will increase the number of bases in B by one according to this. This operation is
called ‘Extension Operation’. We will introduce the details of it later. Note that Extension
Operation can be executed for at most γp (G) times.
Case 2. G(S) has a p-size separator vertex v or has at most 3p vertices: we use B̄
to denote the set after replacing S with a single-base v in B. We call the group-base S

9

10

Kernels for Separating a Graph into Components of Bounded Size

changeable if B̄ fulfills (Q4). When we find a changeable group-base S, we replace S with
the vertex v in B. It is easy to see that after this operation, B still holds the base-properties.
Our algorithm will iteratively deal with extendable and changeable group-bases found by
the algorithm. Finally, the remaining group-bases will not cause troubles in our analysis. We
construct a graph G∗ by merging each group-base in G into a single vertex, called group-vertex.
Let B ∗ be the set after replacing each group-base with a group-vertex in B. We invoke
crown(G∗ , B ∗ , p). Let (I, C) = crown(G∗ , B ∗ , p). We will guarantee that: the set C ⊆ B ∗
returned by crown(G∗ , B ∗ , p) does not contain any group-vertex, |A \ C| = |A∗ \ C| = O(pk),
and |B \ C| = O(pk). Then we can reduce the instance by removing I ∪ C in G by Lemma 5.
The remaining part of the graph has only O(pk) vertices. The main steps of the algorithm
to compute I and C are presented in Figure 4. Next, we give the details of some steps in the
algorithm and proofs.
Input: A connected graph G = (V, E) and an integer p > 0.
Output: Two vertex subsets I and C such that (I, C, J = V \ (I ∪ C)) a p-weighted crown
decomposition of G satisfying the size condition in Theorem 2.
1. Compute a maximal packing S of connected (p + 1)-subgraphs.
2. let B be the set of vertices appearing in S and let A = V \ B, where the vertex set of
each (p + 1)-subgraph in S is a group-base in B.
3. If {there exits an extendable group-base S}, do
3.1 increase the number of bases in B according to Extension Operation: first replace S
with two new group-bases and then extend each single-base to a group-base;
3.2 update S by letting it be the packing of connected (p + 1)-subgraphs corresponding to
the group-bases in B;
3.3 goto Step 2.
4. construct G∗ from G by merging each group-base into a group-vertex, and let B ∗ be
the set obtained by replacing each group-base with a group-vertex in B. Let (I, C) =
crown(G∗ , B ∗ , p0 = 4p).
// We also keep original G and B.
5. If {A vertex u ∈ C is a group-vertex}, do
// Then u should be changeable
5.1 update B by replacing S (S is the group-base corresponding to the group-vertex u)
with a single-base v in B and let A = V \ B, where v is a p-size separator vertex of
G(S);
5.2 goto Step 3.
6. return (I, C) ( Now C does not contain any group-vertex and then vertex sets I and C
returned by crown(G∗ , B ∗ , p0 = 4p) are also two vertex sets in the original graph G).

Figure 4 Algorithm SCC(G, p)

Step 3. Let S be an extendable group-base in Step 3. Then G(S) is a connected graph
of at least 3p + 1 vertices and it has no p-set separator vertex. By invoking connect(G(S), p),
we can find two connected subgraphs G[V1 ] and G[V2 ] of at least p + 1 vertices, where
V1 ∪ V2 = V (G(S)). Note that each S-attached component has at most p vertices and then
each of V1 and V2 must contain some vertices in S. We look at G[Vi \ S] (i = 1, 2), each
connected component of it is a S-attached component or a partial of a S-attached component.
After removing some of such components from G[Vi ] the remaining graph is still connected.
So we iteratively remove a connected component of G[Vi \ S] from G[Vi ] until G[Vi ] has less

M. Xiao

than 2p + 1 vertices. We use Vi0 to denote the current set Vi . Now G[Vi0 ] is still connected
and has at least p + 1 vertices since each connected component of G[Vi \ S] has at most p
vertices. We select a set Vi00 of exactly p + 1 vertices from Vi0 such that G[Vi00 ] is a connected
graph. The two (p + 1)-subgraphs G[V100 ] and G[V200 ] are what we are looking for. We update
B by replacing S with two group-bases Sn1 = V100 and Sn2 = V200 in B. Next, we show that
each single-base in B can be extended to a group-base keeping all vertices in B different. By
(Q4), we know that there is a full (4p, ∞)-star packing from Bs0 to A0 (before replacing S
with Sn1 and Sn2 ). So each vertex v ∈ Bs0 (a vertex in a single-base) has the some ‘exclusive’
{v}-attached components (which are corresponding to the leaves of the star centered at v in
the full (4p, ∞)-star packing). The number of vertices in exclusive {v}-attached components
is at least 4p. Some exclusive {v}-attached components may be included to V1 ∪ V20 . However,
|V1 ∪ V2 \ S| ≤ 2p + 2p − (p + 1) = 3p − 1. The number of vertices in the exclusive {v}-attached
components not containing any vertices in V1 ∪ V2 is at least 4p − (3p − 1) = p + 1. These
vertices together with v will form a connected component of at least p + 1 vertices. We extend
a single-base {v} to a group-base by using these vertices. Note that each single-base v only
uses exclusive {v}-attached components to extend to a group-base. So all the group-bases
will be vertex-disjoint. The above operation is called Extension Operation.
Next, we analyze the running time bound of Step 3. In fact, the full (4p, ∞)-star packing
used in this step is computed in Step 4. So in this step, we mainly use O(pm) time to invoke
connect(G(S), p). All the other operations can be implemented in linear time. So Step 3
uses O(pm) time.
Step 5. We mainly prove the claim in this step: if a vertex u ∈ C is a group-vertex,
then u is a changeable group-vertex. Let S be the group-base in B corresponding to the
group-vertex u ∈ B ∗ . Step 3 has been executed and then S is not extendable. In fact, the
S-associate subgraph G(S) has at least p0 + (p + 1) = 5p + 1 > 3p vertices since u ∈ C and
there is a (p0 , ∞)-star from u to vertices in I. So we know that G(S) has a p-size separator
vertex v.
To prove that S is changeable, we need to consider (Q4). Let Bs∗ ⊆ B ∗ be the set of
vertices corresponding to the vertices in single-bases in B. There is a full (p0 = 4p, ∞)-star
packing from (C ∩ Bs∗ ) ∪ {u} to I. Note that there are no edges between I and B ∗ \ C.
Then there is a full (4p, ∞)-star packing from Bs∗ \ C to A∗ \ I = V (G∗ ) \ B ∗ \ I since (Q4)
holds on B. Then there is a full (4p, ∞)-star packing from Bs∗ ∪ {u} to A∗ , which implies
that (Q4) holds on B̄, where B̄ is obtained by replacing S with v. Thus, u is a changeable
group-vertex.
In Step 5, after replacing a changeable group-base S with a single-base v, B still has
the base-properties: It is easy to see that (Q2) and (Q3) trivially hold; The definition of
changeable group-bases directly implies (Q1) and (Q4).
Steps 4-5 mainly use O(n2 m) time to invoke the algorithm crown(G∗ , B ∗ , p0 ). Other
operations can be executed in linear time.
Based on the above analysis for Steps 3-5, we are ready to prove the main results:
I Lemma 12. Algorithm SCC(G, p) runs in O(γp (G)2 n2 m) time and the two sets I and C
returned by SCC(G, p) make (I, C, J = V \ (I ∪ C)) a p-weighted crown decomposition of G.
A proof of Lemma 12 can be found in Appendix B.
I Lemma 13. The two sets I and C returned by SCC(G, p) satisfy the size condition in
Theorem 2, i.e., |V (G) \ (C ∪ I)| ≤ 9p|K|, for any p-size separator K of the induced subgraph
G[V \ (C ∪ I)].

11

12

Kernels for Separating a Graph into Components of Bounded Size

Proof. We consider the graph G∗ constructed in Step 4 and the original graph G. It is easy
to see that
|B ∗ \ C| ≤ |K|.
By Lemma 9, we know that |V (G∗ ) \ (B ∗ ∪ I)| ≤ (2p0 − 1)|B ∗ \ C|. Note that V (G) \ (B ∪ I) =
V (G∗ ) \ (B ∗ ∪ I). Then we have that
|V (G) \ (B ∪ I)| ≤ (2p0 − 1)|K| = (8p − 1)|K|.
Let x be the number of group-vertices in B ∗ . We know that x ≤ |B ∗ \ C| and |B \ C| =
|B \ C| + xp. Thus,
|B \ C| = (p + 1)|B ∗ \ C| ≤ (p + 1)|K|.
∗

By the above two inequalities, we get that
|V (G) \ (C ∪ I)| = |V (G) \ (B ∪ I)| + |B \ C| ≤ 9p|K|.
J
Theorem 2 directly follows from Lemma 12 and Lemma 13, which also implies:
I Corollary 14. p-Size separator admits a kernel of 9pk vertices.

5

Concluding remarks

In this paper, we first introduce a weighted crown decomposition and a weighted expansion
lemma, and obtain an O(p2 k) vertex kernel for p-Size separator by using them. The
weighted expansion lemma is not a simple extension of the original expansion lemma. We need
to use a ‘hierarchical structure’ to prove it. Then we further improve the kernel bound from
O(p2 k) to O(pk) by proving Theorem 2. This theorem can be regarded as a generalization
of the Nemhauser and Trotter’s local optimization theorem for vertex Cover and it is
proved based on extremal combinatorial arguments. The improvement is obtained by using
a ‘local adjustment property’ and some other techniques. These techniques are possible to
be used to improve kernel sizes for more problems, especially problems with kernelization
algorithms based on techniques similar to the expansion lemma or crown decompositions.
References
1

2
3
4
5
6
7

F.N. Abu-Khzam, R.L. Collins, M.R. Fellows, M.A. Langston, W.H. Suters, C.T. Symons:
Kernelization algorithms for the Vertex Cover problem: Theory and experiments, in: ALENEX 04, ACM/SIAM, (2004) 62–69.
F.N. Abu-Khzam, M.R. Fellows, M.A. Langston, W.H. Suters: Crown structures for vertex
cover kernelization, Theory Comput. Syst. 41 (3) (2007) 411–430.
R. Bar-Yehuda, D. Rawitz, D. Hermelin: An extension of the Nemhauser & Trotter theorem
to generalized vertex cover with applications, SIAM J. Disc. Math. 24(1) (2010) 287–300.
R. Bar-Yehuda, S. Even: A local-ratio theorem for approximating the weighted vertex cover
problem, Ann. Discrete Math. 25 (1985) 27–45.
W. Ben-Ameur, M. Mohamed-Sidi, J. Neto: The k-separator problem: polyhedra, complexity and approximation results. J. of Combinatorial Optimization 29(1): 276–307 (2015)
N. Bousquet, J. Daligault, and S. Thomassé: Multicut is FPT. In: Proceedings of 43th
STOC, 2011:459–468
J. Chen, I.A. Kanj, W. Jia: Vertex cover: Further observations and further improvements,
J. Algorithms 41 (2) (2001) 280–301.

M. Xiao

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

J. Chen, Y. Liu, S. Lu, B.O’Sullivan, and I. Razgon: A fixed-parameter algorithm for the
directed feedback vertex set problem. J. of ACM, 2008, 55(5):21.
M. Chlebík, J. Chlebíková: Crown reductions for the minimum weighted vertex cover problem, Discrete Appl. Math. 156 (2008) 292–312.
B. Chor, M.R. Fellows, D.W. Juedes: Linear kernels in linear time, or how to save k colors
in O(n2 ) steps, In: Proceedings of 30th WG, Springer, (2004) 257–269.
M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk and S. Saurabh: Minimum Bisection
is Fixed Parameter Tractable. In: Proceedings of 46th STOC, 2014: 323–332.
H. Dell, D. van Melkebeek: Satisfiability Allows No Nontrivial Sparsification unless the
Polynomial-Time Hierarchy Collapses. J. ACM 61(4)(2014): 23:1–23:27
P.G. Drange, M.S. Dregi, P.v. Hof: On the Computational Complexity of Vertex Integrity
and Component Order Connectivity. ISAAC 2014: 285–297
J. Enright and K. Meeks: Deleting edges to restrict the size of an epidemic. To appear in
COCOA 2015.
U. Feige, M. Hajiaghayi, J. Lee: Improved approximation algoritms for minimum-weight
vertex separator. In: Proceedings of 37th STOC, 2005, 563–572.
U. Feige, R. Krauthgamer: A Polylogarithmic Approximation of the Minimum Bisection.
SIAM J. Comput. 31(4), 1090–1118 (2002)
U. Feige and M. Mahdian: Finding small balanced separators. In: Proceedings of 38th
STOC 2006: 375–384
M.R. Fellows, J. Guo, H. Moser, R. Niedermeier: A generalization of Nemhauser and
Trotter’s local optimization theorem. J. of Comput. and Syst. Sci. 77(2011) 1141–1158.
F.V. Fomin, D. Lokshtanov, N. Misra, G. Philip, S. Saurabh: Hitting forbidden minors:
Approximation and Kernelization. STACS 2011: 189–200
P. Heggernes, P.van’t Hof, D.Marx, N.Misra, Y.Villanger: On the parameterized complexity
of finding separators with non-hereditary properties. Algorithmica 72: 687–713 (2015)
D.S. Hochbaum: Approximation algorithms for the set covering and vertex cover problems,
SIAM J. Comput. 11 (3) (1982) 555–556.
K.Kawarabayashin and M.Thorup: The Minimum k-way Cut of Bounded Size is FixedParameter Tractable. In: Proceedings of 52nd FOCS 160–169 (2011)
S. Khuller: The Vertex Cover problem, SIGACT News 33 (2) (2002) 31–33.
D.Marx. Parameterized graph separation problems. Theoretical Computer Science,
351(3):394–406, 2006.
D.Marx, B.O’Sullivan, I.Razgon: Finding small separators in linear time via treewidth
reduction. ACM T. on Algorithms 9(4): 30 (2013)
D.Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size
of the cutset. SIAM J. Comput. 43(2): 355–388 (2014)
G.L. Nemhauser, L.E. Trotter: Vertex packings: Structural properties and algorithms,
Math. Program. 8 (1975) 232–248.
I. Razgon and B.O’Sullivan: Almost 2-SAT is fixed-parameter tractable. J. of Computer
and System Sciences 75(8):435–450, 2009
B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Operations Research
Letters, 32(4):299–301, 2004
S. Thomassé: A 4k 2 kernel for feedback vertex set. ACM T. on Algorithms 6(2) (2010)
M. Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theory
Comput. Syst., 46(4):723–736, 2010
M. Xiao: On a generalization of Nemhauser and Trotter’s local optimization theorem. In
ISAAC 2015, 442–452, (2015)

13

14

Kernels for Separating a Graph into Components of Bounded Size

Appendix

A

Figures

w= 2

3

4

1

4

A′

A

B′

B

w=0

H G = ( A′, B′, E ′)

G = (V = A ∪ B, E )

Figure 5 The graph G and the auxiliary bipartite graph HG of G with partition (A, B)

I

I

C

C
J

J

……

A crown decomposition

……

A weighted crown decomposition

Figure 6 Crown decompositions and weighted crown decompositions

...

A

B

single-bases

group-bases

Figure 7 A partition (A, B) holding the base-properties

B

Some Proofs

Lemma 4 Let (I, C, J) be a p-weighted crown decomposition of a graph G = (V, E). Then
(I, C) satisfies the local optimality condition in Theorem 2, i.e., K ∪ C is a minimum p-size
separator of G for any minimum p-size separator K of the induced subgraph G[J].

M. Xiao

15

Proof. It is easy to see that K ∪ C is a p-size separator of G: by Definition 3 we know that
each vertex in I is in a component of size at most p in the remaining graph after deleting C;
and each vertex in J \ K is in a component of size at most p in the remaining graph after
deleting C ∪ K since K is a p-size separator of subgraph G[J] = G[V \ (I ∪ C)].
Next, we show that K ∪ C is also a minimum p-size separator of G. Let D be an arbitrary
minimum p-size separator of G. Let D1 = D ∩ (I ∪ C) and D2 = D ∩ J. Since there are |C|
vertex-disjoint connected subgraphs of G[I ∪ C] each of which contains at least p + 1 vertices,
each p-size separator contains at least |C| vertices in I ∪ C. Then we have that
|D1 | ≥ |C|.
Set D2 is a p-size separator of G[V \ D1 ] and set K is a minimum p-size separator of
G[V \ (I ∪ C)]. Note that D1 ⊆ I ∪ C and then G[V \ (I ∪ C)] is an induced subgraph of
G[V \ D1 ]. The size of a minimum p-size separator of G[V \ D1 ] will not be smaller than the
size of a minimum p-size separator of G[V \ (I ∪ C)]. Thus,
|D2 | ≥ |K|.
Therefore, |K ∪ C| = |K| + |C| ≤ |D1 | + |D2 | = |D|.

J

Lemma 6 If there is no redundant vertex, then there is no strong M -alternating path from
a B10 -vertex to a B30 -vertex.
Proof. Assume that there is a strong M -alternating path from a B10 -vertex to a B30 -vertex u.
Then there is a pure M -alternating path P from a B10 -vertex to u by properties (P2) and
(P3). Assume that u is in level-i in the hierarchical structure. Then i is an even number
since u is a B 0 -vertex by (P1). We show that the vertex v adjacent to u in P is a redundant
vertex. Since u is a B 0 -vertex and P is a strong M -alternating path from a B10 -vertex to
u, we know that vu is an edge not in M and then v is in level-(i − 1) in the hierarchical
structure, where i − 1 is an odd number. The total weight of the vertices adjacent to u via an
M -edge is less than p since u ∈ B30 and w(v) ≤ p since v ∈ A0 . Then after adding uv to M
(also deleting the original M -edge incident on v), the total weight of the vertices adjacent to
u via an M -edge is less than 2p. So v is a redundant vertex and then the lemma holds. J
Lemma 7 Algorithm crown(G = (V, E), B, p) runs in O(|V |2 |E|) time.
Proof. Step 5 can be executed in linear time via a BFS. It is easy to see that each of other
steps takes only linear time. Then we only need to analyze how many loops of Steps 3-4 will
be executed.
Let v be a redundant vertex in level-i. Then v is adjacent to a level-(i − 1) vertex v0 via
an M -edge v0 v. In the operation of eliminating v in Step 4, we will replace the edge v0 v
with another edge vv ∗ in M , where v ∗ is a B 0 -vertex in level-(i + 1). After this operation, no
new B10 -vertex is created and no vertex will be move to a ‘higher’ level with a smaller index.
At least v will appear in a level with index greater than i or not appear in the hierarchical
structure any more. So after this operation some vertices (at least one vertex) either move
to a level with larger index or disappear from the hierarchical structure. So Step 4 can be
executed for at most |V |2 time. Then the algorithm always stops and runs in O(|V |2 |E|)
time.
J
Lemma 8 Algorithm crown(G, B, p) returns two sets I ⊆ V \ B and C ⊆ B such that
(I, C, J = V (G) \ (I ∪ C)) is a p-weighted crown decomposition of G.
Proof. We have shown in Lemma 7 that crown(G, B, p) always stops. To prove the correctness,
we check the three conditions in the definition of p-weighted crown decompositions.

16

Kernels for Separating a Graph into Components of Bounded Size

According to the definition of C 0 and Lemma 6, we know that C 0 is a subset of B10 ∪ B20 .
Therefore, there is a full (p, ∞)-star packing from C 0 to I 0 , which is formed by the edges in
M . Condition (3) in Definition 3 holds.
Condition (2) trivially holds since I is just a subset of A = V (G) \ B and the input of
crown(G, B, p) requires that each component of G[A] has at most p vertices.
Next we consider condition (1). We first show that there is no edge between I 0 and
0
B \ C 0 . Assume to the contrary that there is an edge uv between I 0 and B 0 \ C 0 , where u ∈ I 0
and v ∈ B 0 \ C 0 . We show that there is a strong M -alternating path P from a B10 -vertex
to v. Assume that uv 0 ∈ M . Then v 0 is a vertex in C 0 since u is in I 0 . There is a strong
M -alternating path P 0 from a B10 -vertex v ∗ to v 0 according to the definition of C 0 . If P 0
passes u, then let P be the subpath of P 0 from v ∗ to u adding an edge uv. Otherwise we let
P be the path adding v 0 uv to the end of P 0 . We can see that P is still a strong M -alternating
path from a B10 -vertex to v, which together with Lemma 6 imply a contradiction that there
is a redundant vertex.
Therefore, there is no edge between I 0 and B 0 \ C 0 in HG and then there is no edge
between I and B \ C in G. It is clear that there is no edge between I and A \ I in G. So
there is no edge between I and J = (A \ I) ∪ (B \ C) in G. Condition (1) holds.
All the three conditions in Definition 3 hold and then I and C make (I, C, J = V (G) \
(I ∪ C)) a p-weighted crown decomposition.
J
Lemma 9 The two sets I and C returned by crown(G, B, p) satisfy the following size
condition:
|V \ (B ∪ I)| ≤ (2p − 1)|B \ C|.

(2)

Proof. According to the definition of C 0 we know that B 0 \ C 0 does not contain any vertex in
B10 . Then the weight of vertices in A0 \ I 0 is bounded by (2p − 1)|B 0 \ C 0 |, which implies (2).
J
Lemma 12 Algorithm SCC(G, p) runs in O(γp (G)2 n2 m) time and the two sets I and C
returned by SCC(G, p) make (I, C, J = V \ (I ∪ C)) a p-weighted crown decomposition of G.
Proof. First, we prove that two sets I and C returned by SCC(G, p) make (I, C, J = V \(I∪C))
a p-weighted crown decomposition of G by checking the three conditions in the definition of
p-weighted crown decompositions.
In Step 6, no vertex in C is a group-vertex and then each vertex in I and C is a vertex in
the original graph G. By Lemma 8, the two sets I and C returned by crown hold Condition
(3) in Definition 3. There are also no edge between I and (B \ C) ∪ (A \ I) by Lemma 8. The
condition of (1) in Definition 3 holds. Condition (2) in Definition 3 holds because the set B
always holds the base-properties (we have shown above that after one execution of Step 3
the set S is still a maximal connected (p + 1)-subgraph packing and after one execution of
Step 5 the set B still holds the base-properties).
Second, we consider the running time bound. We have analyzed above each execution
of Step 3 takes O(pm) time and each execution of Step 4 takes O(n2 m) time. We analyze
how many iterations Steps 3-5 will be executed. Step 3 can be executed for at most γp (G)
times. Between two adjacent executions of Step 3, Steps 4-5 can be executed for at most
γp (G) times since each execution of Step 5 will increase the number of single-bases, which
will not decrease except executing Step 3. Therefore, Steps 4-5 can be executed for at most
γp (G)2 times. The whole algorithm runs in O(γp (G)2 n2 m) time.
J

