A 2`k Kernel for `-Component Order Connectivity
Mithilesh Kumar1 and Daniel Lokshtanov2
1

2

Department of Informatics, University of Bergen
Norway
Mithilesh.Kumar@ii.uib.no
Department of Informatics, University of Bergen
Norway
daniello@ii.uib.no

arXiv:1610.04711v1 [] 15 Oct 2016

Abstract
In the `-Component Order Connectivity problem (` ∈ N), we are given a graph G on
n vertices, m edges and a non-negative integer k and asks whether there exists a set of vertices
S ⊆ V (G) such that |S| ≤ k and the size of the largest connected component in G − S is at most
`. In this paper, we give a kernel for `-Component Order Connectivity with at most 2`k
vertices that takes nO(`) time for every constant `. On the way to obtaining our kernel, we prove
a generalization of the q-Expansion Lemma to weighted graphs. This generalization may be of
independent interest.
1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems
Keywords and phrases Parameterized algorithms, Kernel, Component Order Connectivity, Maxmin allocation, Weighted expansion
Digital Object Identifier 10.4230/LIPIIT.2016.23

1

Introduction

In the classic Vertex Cover problem, the input is a graph G and integer k, and the task
is to determine whether there exists a vertex set S of size at most k such that every edge
in G has at least one endpoint in S. Such a set is called a vertex cover of the input graph
G. An equivalent definition of a vertex cover is that every connected component of G − S
has at most 1 vertex. This view of the Vertex Cover problem gives rise to a natural
generalization: can we delete at most k vertices from G such that every connected component
in the resulting graph has at most ` vertices? Here we study this generalization. Formally,
for every integer ` ≥ 1, we consider the following problem, called `-Component Order
Connectivity (`-COC).
`-Component Order Connectivity (`-COC)
Input: A graph G on n vertices and m edges, and a positive integer k.
Task: determine whether there exists a set S ⊆ V (G) such that |S| ≤ k and the maximum
size of a component in G − S is at most `.
The set S is called an `-COC solution. For ` = 1, `-COC is just the Vertex Cover
problem. Aside from being a natural generalization of Vertex Cover, the family {`-COC
: ` ≥ 1} of problems can be thought of as a vulnerability measure of the graph G - how many
vertices of G have to fail for the graph to break into small connected components? For a
study of `-COC from this perspective see the survey of Gross et al. [12].
From the work of Lewis and Yannakakis [16] it immediately follows that `-COC is NPcomplete for every ` ≥ 1. This motivates the study of `-COC within paradigms for coping with
© Mithilesh Kumar and Daniel Lokshtanov;
licensed under Creative Commons License CC-BY
42nd Conference on Very Important Topics (CVIT 2016).
Editors: John Q. Open and Joan R. Acces; Article No. 23; pp. 23:1–23:14
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

23:2

A 2`k Kernel for `-Component Order Connectivity

NP-hardness, such as approximation algorithms [22], exact exponential time algorithms [11],
parameterized algorithms [5, 7] and kernelization [14, 17]. The `-COC problems have (for
some values of `) been studied within all four paradigms, see the related work section.
In this work we focus on `-COC from the perspective of parameterized complexity and
kernelization. Our main result is an algorithm that given an instance (G, k) of `-COC,
runs in polynomial time, and outputs an equivalent instance (G0 , k 0 ) such that k 0 ≤ k and
|V (G0 )| ≤ 2`k. This is called a kernel for `-COC with 2`k vertices. Our kernel significantly
improves over the previously best known kernel with O(`k(k + `)) vertices by Drange et
al. [8]. Indeed, for ` = 1 our kernel matches the size of the smallest known kernel for Vertex
Cover [3] that is based on the classic theorem of Nemhauser and Trotter [18].
Related Work. 1-COC, better known as Vertex Cover, is extremely well studied from
the perspective of approximation algorithms [22, 6], exact exponential time algorithms [10,
19, 24], parameterized algorithms [5, 4] and kernelization [3, 18]. The kernel with 2k
vertices for Vertex Cover is considered one of the fundamental results in the field of
kernelization. The 2-COC problem is also well studied, and has been considered under several
different names. The problem, or rather the dual problem of finding a largest possible
set S that induces a subgraph in which every connected component has order at most
2, was first defined by Yannakakis [25] under the name Dissociation Set. The problem
has attracted attention in exact exponential time algorithms [13, 23], the fastest currently
known algorithm [23] has running time O(1.3659n ). 2-COC has also been studied from the
perspective of parameterized algorithms [2, 20] (under the name Vertex Cover P3 ) as well
as approximation algorithms [21]. The fastest known parameterized algorithm, due to Chang
et al. [2] has running time 1.7485k nO(1) , while the best approximation algorithm, due to Tu
and Zhou [21] has factor 2.
For the general case of `-COC, ` ≥ 1, Drange et al. [8] gave a simple parameterized
algorithm with running time (` + 1)k nO(1) , and a kernel with O(k`(` + k)) vertices. The
parameterized algorithm of Drange et al. [8] can be improved to (` + 0.0755)k nO(1) by
reducing to the (` + 1)-Hitting Set problem, and applying the iterative compression based
algorithm for (` + 1)-Hitting Set due to Fomin et al. [9]. The reduction to (` + 1)-Hitting
Set, coupled with the simple factor (` + 1)-approximation algorithm for (` + 1)-Hitting
Set [22] immediately also yields an (` + 1)-approximation algorithm for `-COC. There has
also been some work on `-COC when the input graph is restricted to belong to a graph class,
for a discussion of this work see [8].
Comparing the existing results with our work, we see that our kernel improves over the
kernel of Drange et al. [8] from at most O(k`(` + k)) vertices to at most 2k` vertices. Our
kernel is also the first kernel with a linear number of vertices for every fixed ` ≥ 2.
Our Methods. Our kernel for `-COC hinges on the concept of a reducible pair of vertex
sets. Essentially (this is not the formal definition used in the paper!), a reducible pair is a
pair (X, Y ) of disjoint subsets of V (G) such that N (Y ) ⊆ X, every connected component of
G[Y ] has size at most `, and every solution S to G has to contain at least |X| vertices from
G[X ∪ Y ]. If a reducible pair is identified, it is easy to see that one might just as well pick
all of X into the solution S, since any solution has to pay |X| inside G[X ∪ Y ], and after X
is deleted, Y breaks down into components of size at most ` and is completely eliminated
from the graph.
At this point there are several questions. (a) How does one argue that a reducible pair is
in fact reducible? That is, how can we prove that any solution has to contain at least |X|
vertices from X ∪ Y ? (b) How big does G have to be compared to k before we can assert the
existence of a reducible pair? Finally, (c) even if we can assert that G contains a reducible

M. Kumar and D. Lokshtanov

23:3

pair, how can we find one in polynomial time?
To answer (a) we restrict ourselves to reducible pairs with the additional property that
each connected component C of G[Y ] can be assigned to a vertex x ∈ N (C), such that for
every x ∈ X the total size of the components assigned to x is at least `. Then x together
with the components assigned to it form a set of size at least ` + 1 and have to contain a
vertex from the solution. Since we obtain such a connected set for each x ∈ X, the solution
has to contain at least |X| vertices from X ∪ Y . Again we remark that this definition of a
reducible pair is local to this section, and not the one we actually end up using.
To answer (b) we first try to use the q-Expansion Lemma (see [5]), a tool that has found
many uses in kernelization. Roughly speaking the Expansion Lemma says the following:
if q ≥ 1 is an integer and H is a bipartite graph with bipartition (A, B) and B is at least
q times larger than A, then one can find a subset X of A and a subset Y of B such that
N (Y ) ⊆ X, and an assignment of each vertex y ∈ Y to a neighbor x of y, such that every
vertex x in X has at least q vertices in Y assigned to it.
Suppose now that the graph does have an `-COC solution S of size at most k, and that
V (G) \ S is sufficiently large compared to S. The idea is to apply the Expansion Lemma
to the bipartite graph H, where the A side of the bipartition is S and the B side has one
vertex for each connected component of G − S. We put an edge in H between a vertex v in
S and a vertex corresponding to a component C of G − S if there is an edge between v and
C in G. If G − S has at least |S| · ` connected components, we can apply the `-Expansion
Lemma on H, and obtain a set X ⊆ S, and a collection Y of connected components of
G − X satisfying the following properties. Every component C ∈ Y satisfies N (C) ⊆ X and
|C| ≤ `. Furthermore, there exists an assignment of each connected component C to a vertex
x ∈ N (C), such that every x ∈ X has at least ` components assigned to it. Since x has at
least ` components assigned to it, the total size of the components assigned to x is at least
S
`. But then, X and Y = C∈Y C form a reducible pair, giving an answer to question (b).
Indeed, this argument can be applied whenever the number of components of G − S is at
least ` · |S|. Since each component of G − S has size at most `, this means that the argument
can be applied whenever |V (G) \ S| ≥ `2 · |S| ≥ `2 k.
Clearly this argument fails to yield a kernel of size 2`k, because it is only applicable
when |V (G)| = Ω(`2 k). At this point we note that the argument above is extremely wasteful
in one particular spot: we used the number of components assigned to x to lower bound
the total size of the components assigned to x. To avoid being wasteful, we prove a new
variant of the Expansion Lemma, where the vertices on the B side of the bipartite graph
H have non-negative integer weights. This new Weighted Expansion lemma states that if
q, W ≥ 1 are integers, H is a bipartite graph with bipartition (A, B), every vertex in B has
a non-negative integer weight which is at most W , and the total weight of B is at least
(q + W − 1) · |A|, then one can find a subset X of A and a subset Y of B such that N (Y ) ⊆ X,
and an assignment of each vertex y ∈ Y to a neighbor x of y, such that for every vertex in
X, the total weight of the vertices assigned to it is at least q. The proof of the Weighted
Expansion Lemma is based on a combination of the usual, unweighted Expansion Lemma
with a variant of an argument by Bezáková and Dani [1] to round the linear program for
Max-min Allocation of goods to customers.
Having the Weighted Expansion Lemma at hand we can now repeat the argument
above for proving the existence of a reducible pair, but this time, when we build H, we
can give the vertex corresponding to a component C of G − S weight |C|, and apply the
Weighted Expansion Lemma with q = ` and W = `. Going through the argument again,
it is easy to verify that this time the existence of a reducible pair is guaranteed whenever

CVIT 2016

23:4

A 2`k Kernel for `-Component Order Connectivity

|V (G) \ S| ≤ (2` − 1)k, that is when |V (G)| ≥ 2`k.
We are now left with question (c) - the issue of how to find a reducible pair in polynomial
time. Indeed, the proof of existence crucially relies on the knowledge of an (optimal) solution
S. To find a reducible pair we use the linear programming relaxation of the `-COC problem.
We prove that an optimal solution to the LP-relaxation has to highlight every reducible
pair (X, Y ), essentially by always setting all the variables corresponding to X to 1 and the
variables corresponding to Y to 0. For Vertex Cover (i.e 1-COC), the classic Nemhauser
Trotter Theorem [18] implies that we may simply include all the vertices whose LP variable is
set to 1 into the solution S. For `-COC with ` ≥ 2 we are unable to prove the corresponding
statement. We are however, able to prove that if a reducible pair (X, Y ) exists, then X
(essentially) has to be assigned 1 and Y (essentially) has to be assigned 0. We then give
a polynomial time algorithm that extracts X and Y from the vertices assigned 1 and 0
respectively by the optimal linear programming solution. Together, the arguments (b) and
(c) yield the kernel with 2`k vertices. We remark that to the best of our knowledge, after the
kernel for Vertex Cover [3] our kernel is the first example of a kernelization algorithm based
on linear programming relaxations.
Overview of the paper. In Section 2 we recall basic definitions and set up notations.
The kernel for `-COC is proved in Sections 3, 4 and 5. In Section 3 we prove the necessary
adjustment of the results on Max-Min allocation of Bezáková and Dani [1] that is suitable to
our needs. In Section 4 we state and prove our new Weighted Expansion Lemma, and in
Section 5 we combine all our results to obtain the kernel.

2

Preliminaries

Let N denote the set of positive integers {0, 1, 2, . . . }. For any non-zero t ∈ N, [t] :=
{1, 2, . . . , t}. We denote a constant function f : X → N such that for all x ∈ X, f (x) = c,
by f = c. For any function f : X → N and a constant c ∈ N, we define the function
f + c : X → N such that for all x ∈ X, (f + c)(x) = f (x) + c. We use the same symbol f to
denote the restriction of f over a subset of it’s domain, X. For a set {v} containing a single
element, we simply write v. A vertex u ∈ V (G) is said to be incident on an edge e ∈ E(G) if
u is one of the endpoints of e. A pair of edges e, e0 ∈ E(G) are said to be adjacent if there is
a vertex u ∈ V (G) such that u is incident on both e and e0 . For any vertex u ∈ V (G), by
N (u) we denote the set of neighbors of u i.e. N (u) := {v ∈ V (G) | uv ∈ E(G)}. For any
subgraph X ⊆ G, by N (X) we denote the set of neighbors of vertices in X outside X, i.e.
S
N (X) := ( u∈X N (u)) \ X. A pair of vertices u, v ∈ V (G) are called twins if N (u) = N (v).
An induced subgraph on X ⊆ V (G) is denoted by G[X].
A path P is a graph, denoted by a sequence of vertices v1 v2 . . . vt such that for any
i, j ∈ [t], vi vj ∈ E(P ) if and only if |i − j| = 1. A cycle C is a graph, denoted either by a
sequence of vertices v1 v2 . . . vt or by a sequence of edges e1 e2 . . . et , such that for any i, j ∈ [t]
ui uj ∈ E(C) if and only if |i − j| = 1 mod t or in terms of edges, for any i, j ∈ [t], ei is
adjacent to ej if and only if |i − j| = 1 mod t. The length of a path(cycle) is the number
of edges in the path(cycle). A triangle is a cycle of length 3. In G, for any pair of vertices
u, v ∈ V (G) dist(u, v) represents the length of a shortest path between u and v. A tree is a
connected graph that does not contain any cycle. A rooted tree T is a tree with a special
vertex r called the root of T . With respect to r, for any edge uv ∈ E(T ) we say that v is
a child of u (equivalently u is parent of v) if dist(u, r) <dist(v, r). A forest is a collection
of trees. A rooted forest is a collection of rooted trees. A clique is a graph that contains
an edge between every pair of vertices. A vertex cover of a graph is a set of vertices whose

M. Kumar and D. Lokshtanov

23:5

removal makes the graph edgeless.
Fixed Parameter Tractability. A parameterized problem Π is a subset of Σ∗ × N. A
parameterized problem Π is said to be fixed parameter tractable(FPT) if there exists an
algorithm that takes as input an instance (I, k) and decides whether (I, k) ∈ Π in time
f (k) · nc , where n is the length of the string I, f (k) is a computable function depending only
on k and c is a constant independent of n and k.
A kernel for a parameterized problem Π is an algorithm that given an instance (T, k)
runs in time polynomial in |T |, and outputs an instance (T 0 , k 0 ) such that |T 0 |, k 0 ≤ g(k) for
a computable function g and (T, k) ∈ Π if and only if (T 0 , k 0 ) ∈ Π. For a comprehensive
introduction to FPT algorithms and kernels, we refer to the book by Cygan et al. [5].
A data reduction rule, or simply, reduction rule, for a parameterized problem Q is a
function φ : Σ∗ × N → Σ∗ × N that maps an instance (I, k) of Q to an equivalent instance
(I 0 , k 0 ) of Q such that φ is computable in time polynomial in |I| and k. We say that two
instances of Q are equivalent if (I, k) ∈ Q if and only if (I 0 , k 0 ) ∈ Q; this property of the
reduction rule φ, that it translates an instance to an equivalent one, is referred as the safeness
of the reduction rule.

3

Max-min Allocation

We will now view a bipartite graph G := ((A, B), E) as a relationship between “customers”
represented by the vertices in A and “items” represented by the vertices in B. If the graph
is supplied with two functions wa : A → N and wb : B → N, we treat these functions as a
“demand function” and a “capacity” function, respectively. That is, we consider each item
v ∈ B to have value wb (v), and every customer u ∈ A wants to be assigned items worth at
least wa (u). An edge between u ∈ A and v ∈ B means that the item v can be given to u.
A weight function f : E(G) → N describes an assignment of items to customers, provided
that the items can be “divided” into pieces and the pieces can be distributed to different
customers. However this “division” should not create more value than the original value of
the items. Formally we say that the weight function satisfies the capacity constraint wb (v)
P
of v ∈ B if uv∈E(G) f (uv) ≤ wb (v). The weight function satisfies the capacity constraints
if it satisfies the capacity constraints of all items v ∈ B.
P
For each item u ∈ A, we say that f allocates uv∈E(G) f (uv) value to u. The weight
function f satisfies the demand wa (u) of u ∈ A if it allocates at least wa (u) value to u, and
f satisfies the demand constraints if it does so for all u ∈ A. In other words, the weight
function satisfies the demands if every customer gets items worth at least her demand. The
weight function f over-satisfies a demand constraint wa (u) of u if it allocates strictly more
than wa (u) to u.
We will also be concerned with the case where items are indivisible. In particular we
say that a weight function f : E(G) → N is unsplitting if for every v ∈ B there is at most
one edge uv ∈ E(G) such that f (uv) > 0. The essence of the next few lemmas is that if
we have a (splitting) weight function f of items whose value is at most W , and f satisfies
the capacity and demand constraints, then we can obtain in polynomial-time an unsplitting
weight function f 0 that satisfies the capacity constraints and violates the demand constraints
by at most (W − 1). In other words we can make a splitting distribution of items unsplitting
at the cost of making each customer lose approximately the value of the most expensive item.
Allocating items to customers in such a way as to maximize satisfaction is well studied
in the literature. The lemmata 1 and 2 are very similar, both in statement and proof, to
the work of Bezáková and Dani [1][Theorem 3.2], who themselves are inspired by Lenstra et

CVIT 2016

23:6

A 2`k Kernel for `-Component Order Connectivity

al. [15]. However we do not see a way to directly use the results of Bezáková and Dani [1],
because we need a slight strengthening of (a special case of) their statement.
I Lemma 1. There exists a polynomial-time algorithm that given a bipartite graph G, a
capacity function wb : B → N, a demand function wa : A → N and a weight function
f : E(G) → N that satisfies the capacity and demand constraints, outputs a function
f 0 : E(G) → N such that f 0 satisfies the capacity and demand constraints and the graph
Gf 0 = (V (G), {uv ∈ E(G) | f 0 (uv) > 0}) induced on the non-zero weight edges of G is a
forest.
Proof. We start with f and in polynomially many steps, change f into the required function
f 0 . If Gf = (V (G), {uv ∈ E(G) | f (uv) > 0}) is a forest, then we return f 0 = f . Otherwise,
suppose that Gf contains a cycle C := e1 e2 e3 . . . e2s . Proceed as follows. Without loss of
generality, suppose c = f (e1 ) = min{f (e) | e ∈ C}, and note that c > 0. Compute the edge
weight function f ? : E → R defined as follows. For ei ∈ C, we define f ? (ei ) = f (e) − c if i is
odd, and define f ? (ei ) = f (e) + c if i is even. For e ∈
/ C we define f ? (ei ) = f (e).
Every vertex of G is incident to either 0 or exactly 2 edges of C. If the vertex v is incident
to two edges of C then one of these edges, say e2i , has even index in C, and the other, e2i+1
has odd. For the edge e2i we have f ? (e2i ) = f (e2i ) + c and for e2i+1 we have f ? (e2i+1 ) =
P
P
f (e2i+1 ) − c. Thus we conclude that for all v ∈ V (G), u∈N (v) f ? (uv) = u∈N (v) f (uv),
and that therefore f ? satisfies the capacity and demand constraints. Furthermore at least
one edge that is assigned non-zero weight by f is assigned 0 by f ? and Gf ? = (V (G), {uv ∈
E(G) | f ? (uv) > 0}) has one less cycle than Gf . For a polynomial-time algorithm, repeatedly
apply the process described above to reduce the number of edges with non-zero weight, as
long as Gf ? contains a cycle.
J
I Lemma 2. There exists a polynomial-time algorithm with the following specifications. It
takes as input a bipartite graph G := ((A, B), E), a demand function wa : A → N, a capacity
function wb : B → N, an edge weight function f : E(G) → N that satisfies both the capacity
and demand constraints, and a vertex r ∈ A. The algorithm outputs an unsplitting edge
weight function h : E(G) → N that satisfies the capacity constraints, satisfies the demands
wa0 = wa − (W − 1) where W = maxv∈B wb (v), and additionally satisfies the demand wa (r)
of r.
Proof. Without loss of generality the graph Gf := (V (G), {uv ∈ E(G) | f (uv) > 0}) is a
forest. If it is not, we may apply Lemma 1 to f , and obtain a function f 0 that satisfies the
capacity and demand constraints, and such that Gf 0 = (V (G), {uv ∈ E(G) | f 0 (uv) > 0}) is
a forest. We then rename f 0 to f . By picking a root in each connected component of Gf we
may consider Gf as a rooted forest. We pick the roots as follows, if the component contains
the special vertex r, we pick r as root. If the component does not contain r, but contains at
least one vertex u ∈ A, we pick that vertex as the root. If the component does not contain
any vertices of A then it does not contain any edges and is therefore a single vertex in B, we
pick that vertex as root. Thus, every item v ∈ B that is incident to at least one edge in Gf
has a unique parent u ∈ A in the forest Gf . We define the new weight function h. For every
edge uv ∈ E(G) with u ∈ A and v ∈ B we define h(uv) as follows. h(uv) = wb (v) if u is the
parent of v in Gf , and h(uv) = 0 otherwise.
Clearly h is unsplitting and satisfies the capacity constraints. We now prove that h also
satisfies the demand constraints wa0 and satisfies the demand constraint wa (r) of r. Consider
the demand constraint wa0 (u) for an arbitrary customer u ∈ A. There are two cases, either u
is the root of the component of Gf or it is not. If u is the root, then for every edge uv ∈ E(G)

M. Kumar and D. Lokshtanov

23:7

f (e2 ) + c

v

A

u

f (e1 ) − c = 0

f (e4 ) + c

f (e2s ) + c

B

≤ wb (v)
≥ wa (u)

f (e3 ) − c

···

wb (v0 )

v0
0

v

0

B
u

wb (v)

≥ wa (u) − W + 1
≥ wa (u) − W + 1

u

wb (v1 )

wb (v3 )
wb (v2 )

A
v1

v2

v3

Figure 1 Proof of Lemma 1 and 2. Cyclically shift smallest weight in a non-zero weight cycle to
obtain a forest. Root each tree in the forest at a vertex in A such that each vertex in B has a parent
in A. Assign the value of v ∈ B to its parent u ∈ A. In this new assignment, a non-root vertex
u ∈ A loses its parent v0 ∈ B and f (v0 u) ≤ W − 1 which explains the cost of making a splitting
assignment into an unsplitting assignment.

such that f (uv) > 0 we have that uv ∈ E(Gf ) and consequently that u is the parent of
v. Hence h(uv) = wb (v) ≥ f (uv), and therefore h satisfies the demand wa (u) of u. Since
wa (u) ≥ wa0 (u), we have that h satisfies the demand wa0 (u). Furthermore, since r is the root
of its component this also proves that h satisfies the demand wa (r).
Consider now the case that u is not the root of its component in Gf . Then u has a unique
parent in Gf , call this vertex v ? ∈ B. We first prove that f (uv ? ) ≤ wb (v ? ) − 1. Indeed,
since v ? is incident to the edge uv ? we have that v ? has a parent u? in Gf , and that u? 6= u
because v ? is the parent of u. We have that f (u? v ? ) + f (uv ? ) ≤ wb (v ? ) and that f (u? v ? ) ≥ 1,
because u? v ? is an edge in Gf . It follows that f (uv ? ) ≤ wb (v ? ) − 1. We now proceed to
proving that h satisfies the demand wa0 (u).
For every edge uv ∈ E(G) \ {uv ? } such that uv ∈ E(G) such that f (uv) > 0 we
have that uv ∈ E(Gf ) and consequently that u is the parent of v. Hence we have that
h(uv) = wb (v) ≥ f (uv). Furthermore h(uv ? ) = 0 while f (uv ? ) ≤ wb (v ? ) − 1 ≤ W − 1.
Therefore h satisfies the demand wa0 (u).
J

4

The Weighted Expansion Lemma

Our kernelization algorithm will use “q-expansions” in bipartite graphs, a well known tool in
kernelization [5]. We begin by stating the definition of a q-expansion and review the facts
about them that we will use.
I Definition 3 (q-expansion). Let G := ((A, B), E) be a bipartite graph. We say that A
has q-expansion into B if there is a family of sets {Va | Va ⊆ N (a), |Va | ≥ q, a ∈ A} such that
for any pair of vertices ai , aj ∈ A,i 6= j, Vai ∩ Vaj = ∅.
I Definition 4 (Twin graph). For a bipartite graph G := ((A, B), E) with a weight function
wb : B → N, the twin graph TAB := (A, B 0 ) of G is obtained as follows: B 0 contains |wb (v)|
twins of every vertex v ∈ B i.e. B 0 := {v1 , v2 , . . . vwb (v) | v ∈ B} and edges in TAB such that

CVIT 2016

23:8

A 2`k Kernel for `-Component Order Connectivity

for all v ∈ B and i ∈ [wb (v)], N (vi ) = N (v) i.e. E(TAB ) := {avi |a ∈ A, vi ∈ B 0 , v ∈ B, av ∈
E(G)}.
I Lemma 5. [5] Let G be a bipartite graph with bipartition (A, B). Then there is a qexpansion from A into B if and only if |N (X)| ≥ q|X| for every X ⊆ A. Furthermore, if
there is no q-expansion from A into B, then a set X ⊆ A with |N (X)| < q|X| can be found
in polynomial-time.
I Lemma 6 (Expansion Lemma [5]). Let q ≥ 1 be a positive integer and G be a bipartite graph
with vertex bipartition (A, B) such that |B| ≥ q|A|, and there are no isolated vertices in B.
Then there exist nonempty vertex sets X ⊆ A and Y ⊆ B such that there is a q-expansion of
X into Y , and no vertex in Y has a neighbor outside X, i.e. N (Y ) ⊆ X. Furthermore, the
sets X and Y can be found in time polynomial in the size of G.
I Lemma 7 (folklore). There exists a polynomial-time algorithm that given a bipartite graph
G := ((A, B), E) and an integer q decides (and outputs in case yes) if there exist sets
X ⊆ A, Y ⊆ B such that there is a q-expansion of X into Y .
Proof. We describe a recursive algorithm. If A = ∅ or B = ∅, then output no and terminate.
Otherwise, construct the twin graph TBA with weight function w : A → N where for
all u ∈ A, w(u) = q and let M be a maximum matching in TBA . Consider the graph
G0 := (A, B) with edge set E(G0 ) := {uv, u ∈ A, v ∈ B | ui v ∈ M }. Let A0 ⊆ A such that for
S
all u ∈ A0 , dG0 (u) ≥ q and let B 0 ⊆ B such that B 0 := u∈A0 NG0 (u). If N (B 0 ) ⊆ A0 , then
return (A0 , B 0 ) and terminate. Otherwise, recurse on G[A0 ∪ (B \ NG (A \ A0 ))].
If there are no sets X, Y such that there is a q-expansion of X into Y , then for any pair
of sets A0 ⊆ A, B 0 ⊆ B either N (B 0 ) \ A0 6= ∅ or |B 0 | < q|A0 |. Since at each recursive step,
the size of the graph with which the algorithm calls itself decreases, eventually either A0
becomes empty or B \ NG (A \ A0 ) becomes empty. Hence, the algorithm outputs no. Now
we need to show that if there exist sets (A∗ , B ∗ ) such that there is a q-expansion of A∗
into B ∗ , then at each recursive call, we have that A∗ ⊆ A and B ∗ ⊆ B. At the start of
the algorithm, A∗ ⊆ A and B ∗ ⊆ B. Since N (B ∗ ) ⊆ A∗ and for all u ∈ A∗ dG (u) ≥ q, we
have that A∗ ∪ B ∗ ⊆ V (G0 ). If N (B 0 ) ⊆ A0 , then the algorithm of Lemma 6 when run on
G0 , q will output (A∗ , B ∗ ). Note that B ∗ ⊆ B 0 . At the recursive step, A∗ ⊆ A0 and since
B ∗ ∩ NG (A \ A0 ) = ∅, we have that B ∗ ⊆ B 0 \ NG (A \ A0 ). Hence, G[A∗ ∪ B ∗ ] is a subgraph
of G[A0 ∪ (B \ NG (A \ A0 ))] which concludes the correctness of the algorithm. Since at each
recursive call the size of the graph decreases by at least 1, the total time taken by the above
algorithm is polynomial in n.
J
One may think of a q-expansion in a bipartite graph with bipartition (A, B) as an
allocation of the items in B to each customer in A such that every customer gets at least q
items. For our kernel we will need a generalization of q-expansions to the setting where the
items in B have different values, and every customer gets items of total value at least q.
I Definition 8 (Weighted q-expansion). Let G := ((A, B), E) be a bipartite graph with
capacity function wb : B → N. Then, a weighted q-expansion in G is an edge weight function
f : E(G) → N that satisfies the capacity constraints wb and also satisfies the demand
constraints wa = q. For an integer W ∈ N, the q-expansion f is called a W -strict q-expansion
if f allocates at least q + W − 1 value to at least one vertex r in A, and in this case we say
that f is W -strict at r. Further, a q-expansion f is strict (at r) if it is 1-strict (at r). If f is
unsplitting we call f an unsplitting q-expansion.

M. Kumar and D. Lokshtanov

23:9

I Lemma 9. There exists a polynomial-time algorithm that given a bipartite graph G :=
((A, B), E), an integer q and a capacity function wb : B → N outputs (if it exist) two sets
X ⊆ A and Y ⊆ B along with a weighted q-expansion in G[X ∪ Y ] such that N (Y ) ⊆ X.
Proof. Construct the twin graph TAB := (A, B 0 ) of G. Run the algorithm of Lemma 7 with
input TAB , q that outputs sets X ⊆ A and Y 0 ⊆ B 0 such that X has q-expansion into Y 0
and N (Y 0 ) ⊆ X. Consider the set Y := {v ∈ B | vi ∈ Y 0 }. Define a weight function f :
E(G[X ∪ Y ]) → N as follows: for all uv ∈ E(G[X ∪ Y ]) f (uv) = |{vi ∈ Y 0 |vi matched to u}|.
Clearly, N (Y ) ⊆ X. Now we claim that f is a weighted q-expansion in G[X ∪ Y ] with
capacity function wb and demand function wa = q. For any vertex u ∈ A, there are at least q
P
vertices in Y 0 are matched to u. Hence for all u ∈ A, we have that v∈N (u) f (uv) ≥ q = wa .
At the same time, for any vertex v ∈ B, there are at most wb (v) copies of v in Y 0 . Therefore,
P
for all v ∈ Y we have u∈N (v) f (uv) ≤ wb (v).
J
I Lemma 10. There exists a polynomial-time algorithm that given a weighted q-expansion
f : E(G) → N in G := ((A, B), E), a capacity function wb : B → N and an integer W such
that W = maxe∈E(G) f (e) outputs an unsplitting W -strict weighted (q − W + 1)-expansion in
G.
Proof. Run the algorithm of Lemma 2 with inputs G, f, wa = q, wb , W and a vertex u ∈ A.
In case f is strict, u is the vertex r that makes f strict. Let the function h : E(G) → N
be the output of Lemma 2. Now h is an unsplitting edge weight function that satisfies the
capacity constraints, satisfies the demands q − W + 1, and additionally satisfies the demand q
of u. Hence, h is the required unsplitting weighted W -strict (q − W + 1)-expansion in G. J
I Lemma 11 (Weighted Expansion Lemma). Let q, W ≥ 1 be positive integers and G be a
bipartite graph with vertex bipartition (A, B) and wb : B → {1, . . . , W } be a capacity function
P
such that v∈B wb (v) ≥ (q + W − 1) · |A|, and there are no isolated vertices in B. Then
there exist nonempty vertex sets X ⊆ A and Y ⊆ B such that N (Y ) ⊆ X and there is an
unsplitting weighted W -strict q-expansion of X into Y . Furthermore, the sets X and Y can
be found in time polynomial in the size of G.
Proof. Construct the twin graph TAB from G and wb , the bipartition of TAB is (A, B 0 ).
Now, obtain using the Expansion Lemma 6 with q 0 = q + W − 1 on TAB sets X ⊆ A and
Y 0 ⊆ B 0 , such that N (Y 0 ) ⊆ X and there is a (q + W − 1)-expansion from X to Y 0 in TAB .
Let Y := {v ∈ B | vi ∈ Y 0 } (here the vi ∈ Y 0 are as in Definition 4). Then N (Y ) ⊆ X and
the (q + W − 1)-expansion from X to Y 0 in TAB immediately yields a weighted (q + W − 1)expansion f from X to Y in G. Applying Lemma 10 on G[X ∪ Y ] using the weighted
(q + W − 1)-expansion f proves the statement of the lemma.
J

5

Obtaining the Linear Kernel

I Definition 12. For a graph G and a pair of vertex-disjoint sets X, Y ⊆ V (G), we define
the weighted graph G̃XY as follows: V (G̃XY ) := X ∪ Ỹ such that there is a bijection
h : cc(G[Y ]) → Ỹ where cc(G[Y ]) is the set of connected components of G[Y ]. E(G̃XY ) :=
{xc | x ∈ X, c ∈ Ỹ , c = h(C) and x ∈ NG (C)}. We also define a weight function w : Ỹ → N
such that for all c ∈ Ỹ , w(c) = |h−1 (c)|.
I Definition 13 (Reducible Pair). For a graph G, a pair of vertex-disjoint sets (X, Y ) where
X, Y ⊆ V (G) is called a (strict) reducible pair if N (Y ) ⊆ X, the size of every component in
G[Y ] is at most `, and there exists a (strict) weighted (2` − 1)-expansion in G̃XY .

CVIT 2016

23:10

A 2`k Kernel for `-Component Order Connectivity

I Definition 14. A reducible pair (X, Y ) is called minimal if there is no reducible pair
(X 0 , Y 0 ) such that X 0 ⊂ X and Y 0 ⊆ Y .
I Lemma 15. There exists a polynomial-time algorithm that given an `-COC instance (G, k)
together with a vertex-disjoint set pair A, B ⊆ V (G) outputs (if it exists) a reducible pair
(X, Y ) where X ⊆ A and Y ⊆ B.
Proof. Construct G̃AB := (A, B̃) and run the algorithm of Lemma 9 with input G̃AB , w, q =
2` − 1 which outputs sets X ⊆ A and Y 0 ⊆ B̃ (if it exists) along with a weighted (2` − 1)expansion of X into Y 0 such that N (Y 0 ) ⊆ X. Now from Y 0 we obtain the set Y :=
S
−1
(y). Clearly, N (Y ) ⊆ X and hence, (X, Y ) is the desired reducible pair.
J
y∈Y 0 h
I Lemma 16. Given an `-COC instance (G, k), if |V (G)| ≥ 2`k and (G, k) is a yes-instance,
then there exists a reducible pair (X, Y ).
Proof. Without loss of generality, we can assume that G is a connected graph. Let S be
an `-COC solution of size at most k. Clearly, |V \ S| ≥ (2` − 1)k. We define A := S and
B := V \ S and construct G̃AB = (A, B̃). We have the weight function wb : B̃ → N such that
for all v ∈ B̃, wb (v) = |h−1 (v)| ≤ `, as the size of components in G[V \ S] is at most `. We
P
have that v∈B̃ wb (v) ≥ (2` − 1)|A| and there are no isolated vertices in B̃. Hence, (A, B)
is the desired reducible pair.
J
I Lemma 17. Let (X, Y ) be a reducible pair. Then, there exists a partition of X ∪ Y into
C1 , ..., C|X| such that (i) for all ui ∈ X, we have ui ∈ Cj if and only if i = j, (ii) for all
i ∈ [|X|], |Ci | ≥ ` + 1, (iii) for every component C in G[Y ], there exists a unique Ci such
that V (C) ⊆ Ci and ui ∈ N (C) and (iv) if (X, Y ) is a strict reducible pair, then there exists
Cj such that |Cj | ≥ 2` + 1.
Proof. Construct G̃XY := (X, Ỹ ). Run the algorithm of Lemma 10 with input G̃XY , q =
2` − 1, and W = `(as the capacity of any vertex in Ỹ is at most `) which outputs an
unsplitting weighted `-expansion f 0 in G̃XY . In polynomial time, we modify f 0 such that if
there is a vertex v ∈ Ỹ such that ∀u ∈ N (v), f 0 (uv) = 0, we choose a vertex u ∈ N (v) and set
S
f 0 (uv) = wb (v). For each ui ∈ X define Ci := ui f 0 (ui v)6=0 h−1 (v). Since f 0 is unsplitting,
the collection C1 , . . . , C|X| forms a partition of X ∪ Y . By the definition of Ci , we have
that for any ui ∈ X, ui ∈ Cj if and only if i = j. For any component C in G[Y ], h(C) is
matched to a unique vertex ui ∈ X by f 0 , we have that V (C) ⊆ Ci . As f 0 is a weighted
P
P
`-expansion, |Ci | = 1 + f 0 (ui v)6=0 |h−1 (v)| = 1 + f 0 (ui v)6=0 f 0 (ui v) ≥ 1 + `. Let (X, Y ) be
strict at uj ∈ X. Then, we can use Lemma 10 to obtain the expansion f 0 such that it is
P
P
strict at uj . Hence, |Cj | = 1 + f 0 (uj v)6=0 |h−1 (v)| = 1 + f 0 (uj v)6=0 f 0 (uj v) > 1 + ` + (` − 1)
which implies |Cj | ≥ 2` + 1. This concludes the proof of the lemma.
J
I Lemma 18. Let (X, Y ) be a reducible pair. If (G, k) is a yes-instance for `-COC, then
there exists an `-COC solution S of size at most k such that X ⊆ S and S ∩ Y = ∅.
Proof. By Lemma 17 we have that there are C1 , . . . , C|X| ⊆ X ∪ Y vertex disjoint sets of
size at least ` + 1 such that for all i ∈ [|X|], G[Ci ] is a connected set. Let S 0 be an arbitrary
solution. Then, S 0 must contain at least one vertex from each Ci . Let S := S 0 \ (X ∪ Y ) ∪ X.
We have that |S| ≤ |S 0 | − |X| + |X| = |S 0 |. As any connected set of size ` + 1 that contains
a vertex in Y also contains a vertex in X and X ⊆ S, S is also an `-COC solution.
J
Now we encode an `-COC instance (G, k) as an Integer Linear Programming instance.
We introduce n = |V (G)| variables, one variable xv for each vertex v ∈ V (G). Setting the

M. Kumar and D. Lokshtanov

23:11

variable xv to 1 means that v is in S, while setting xv = 0 means that v is not in S. To
ensure that S contains a vertex from every connected set of size ` + 1, we can introduce
P
constraints v∈C xv ≥ 1 where C is a connected set of size ` + 1. The size of S is given by
P
v∈V (G) xv . This gives us the following ILP formulation:
P
minimize
x ,
P v∈V (G) v
subject to
v∈C xv ≥ 1 for every connected set C of size ` + 1
0 ≤ xv ≤ 1
for every v ∈ V (G)
xv ∈ Z
for every v ∈ V (G).
Note that there are nO(`) connected sets of size at most ` in a graph on n vertices. Hence,
providing an explicit ILP requires nO(`) time which forms the bottleneck for the runtime of
the kernelization algorithm that follows. We consider the Linear Programming relaxation of
above ILP obtained by dropping the constraint that x ∈ Z. By an optimal LP solution SL
with weight L we mean the set of values assigned to each variable, and optimal value is L.
For a set of vertices X ∈ V (G), X = 1 (X = 0) denotes that every variable corresponding to
vertices in X is set to 1 (0).
I Lemma 19. Let SL be an optimal LP solution for G such that xv = 1 for some v ⊆ V (G).
Then, SL − xv is an optimal LP solution for G − v of value L − 1.
Proof. Clearly, SL − xv is feasible solution for G − v of value L − 1. Suppose it is not optimal.
Let SL0 be an optimal LP solution for G − v such that L0 < L − 1. Then, SL0 ∪ xv with
xv = 1 is an optimal LP solution for G with value < L − 1 + 1 = L contradicting that the
optimal solution value of LP for G is L.
J
From now on by running LP after setting xv = 1 for some vertex v, we mean running the LP
algorithm for G − v and including xv = 1 in the obtained solution to get a solution for G.
I Lemma 20. Let (X, Y ) be a strict reducible pair. Then every optimal LP solution sets at
least one variable corresponding to a vertex in X to 1.
Proof. By Lemma 18, we have that every connected set of size ` + 1 in G[X ∪ Y ] contains
a vertex in X. Hence, from any LP solution SL , a feasible LP solution can be obtained by
setting X = 1 and Y = 0. Since, we have at least |X| many vertex disjoint LP constraints,
P
for each vi ∈ X, we have u∈Ci xu = 1. By Lemma 17, there is a set Cj ⊆ X ∪ Y such that
|Cj | ≥ 2` + 1. If xvj 6= 1, then there is a vertex w ∈ Cj such that xw > 0. Let w ∈ C ⊂ Cj
where G[C] is a connected component in G[Y ]. Since |C| ≤ `, there is a connected set C 0 of
P
size at least ` + 1 in G[Cj ] − C. But now u∈C 0 xu < 1 contradicting that SL is feasible. J
I Lemma 21. Let (X, Y ) be a minimal reducible pair. If for any vertex v ∈ X, an optimal
LP solution sets xv = 1, then it also sets X = 1 and Y = 0.
Proof. We prove the lemma by contradiction. Let X 0 ⊂ X be the largest subset of X such
that X 0 = 1. Consider G̃XY . Let Y 0 ⊆ Ỹ be the set of vertices such that N (Y 0 ) ⊆ X 0 . Let
S
P
Z := v∈Y 0 h−1 (v). By the minimality of (X, Y ), we have that v∈Y 0 w(v) < (2` − 1)|X 0 |.
P
Hence, v∈Ỹ \Y 0 w(v) > (2` − 1)|X \ X 0 |. Clearly, the weighted (2` − 1)-expansion in the
reducible pair (X, Y ) when restricted to (X \X 0 , Y \Z) provides a weighted (2`−1)-expansion
of X \X 0 into Y \Z. This implies that (X \X 0 , Y \Z) is a strict reducible pair in G−(X 0 ∪Z).
By Lemma 19, we have that the LP solution restricted to G − (X 0 ∪ Z) is optimal. Since
(X \ X 0 , Y \ Z) is a strict reducible pair, by Lemma 20, there is a vertex u ∈ X \ X 0 such
that xu = 1, but this contradicts the maximality of X 0 . Therefore, if for any vertex v ∈ X,
an LP solution sets xv = 1, then it sets X = 1 and Y = 0.
J

CVIT 2016

23:12

A 2`k Kernel for `-Component Order Connectivity

I Lemma 22. There exists a polynomial time algorithm that given an integer ` and `-COC
instance (G, k) on at least 2`k vertices either finds a reducible pair (X, Y ) or concludes that
(G, k) is a no-instance.
Proof. If (G, k) is a yes-instance of `-COC, then by Lemma 16, there exists a reducible pair
(X, Y ). We use the following algorithm to find one:
Step 1 Run the LP algorithm. Let A = 1 and B = 0 in the LP solution.
Step 2 If both A and B are non-empty, then run the algorithm of Lemma 15 with input
(G, k), A, B. If it outputs a reducible pair (X, Y ), then return (X, Y ) and terminate.
Otherwise, go to step 3.
Step 3 Now we do a linear search for a vertex in X. For each vertex v ∈ V (G), do the
following: in the original LP introduce an additional constraint that sets the value of the
variable xv to 1 i.e. xv = 1 and run the LP algorithm. If the optimal value of the new
LP is the same as the optimal value of the original LP, then let A = 1 and B = 0 be the
sets of variables set to 1 and 0 respectively in the optimal solution of the new LP and go
to step 2.
Step 4 Output a trivial no-instance.
Step 1 identifies the set of variables set to 1 and 0 by the LP algorithm. By Lemma 21, we
have that if there is a minimal reducible pair (X, Y ) in G, then X ⊆ A and Y ⊆ B. So, in
Step 2 if the algorithm succeeds in finding one, we return the reducible pair and terminate
otherwise we look for a potential vertex in X and set it to 1. If (X, Y ) exists, then for at least
one vertex, setting xv = 1 would set X = 1 and Y = 0 (by Lemma 21) without changing
the LP value and we go to Step 2 to find it. If for each choice of v ∈ V (G), the LP value
changes when xv is set to 1, we can conclude that there is no reducible pair and output a
trivial no instance. Since, we need to do this search at most n times and each step takes only
polynomial time, the total time taken by the algorithm is polynomial in the input size. J
I Theorem 23. For every constant ` ∈ N, `-Component Order Connectivity admits a
kernel with at most 2`k vertices that takes nO(`) time.
Acknowledgements The research leading to these results has received funding from the
European Research Council under the European Union’s Seventh Framework Programme
(FP7/2007-2013) / ERC grant agreement no. 306992 and the Beating Hardness by Preprocessing grant funded by the Bergen Research Foundation.
References
1
2

3

4
5

Ivona Bezáková and Varsha Dani. Allocating indivisible goods. SIGecom Exchanges,
5(3):11–18, 2005.
Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith, and Ping-Chen
Su. Fixed-parameter algorithms for vertex cover p3. Discrete Optimization, 19:12–
22, 2016. URL: http://dx.doi.org/10.1016/j.disopt.2015.11.003, doi:10.1016/j.
disopt.2015.11.003.
Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further
improvements. J. Algorithms, 41(2):280–301, 2001. URL: http://dx.doi.org/10.1006/
jagm.2001.1186, doi:10.1006/jagm.2001.1186.
Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor.
Comput. Sci., 411(40-42):3736–3756, 2010.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.

M. Kumar and D. Lokshtanov

6
7
8

9
10
11
12

13

14
15
16

17

18

19
20
21

22
23

23:13

Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover.
Annals of mathematics, pages 439–485, 2005.
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity.
Texts in Computer Science. Springer, 2013.
Pål Grønås Drange, Markus Sortland Dregi, and Pim van ’t Hof. On the computational complexity of vertex integrity and component order connectivity. In Algorithms
and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, pages 285–297, 2014. URL: http://dx.doi.org/10.1007/
978-3-319-13075-0_23, doi:10.1007/978-3-319-13075-0_23.
Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh. Iterative compression and exact algorithms. Theor. Comput. Sci., 411(7-9):1045–1053, 2010.
Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach
for the analysis of exact algorithms. J. ACM, 56(5), 2009.
Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical
Computer Science. An EATCS Series. Springer, 2010.
D. Gross, M. Heinig, L. Iswara, W. Kazmierczak, K. Luttrell, J. T. Saccoman, and C. Suffel.
A survey of component order connectivity models of graph theoretic networks. 12:895–910,
2013.
Frantisek Kardos, Ján Katrenic, and Ingo Schiermeyer. On computing the minimum 3path vertex cover and dissociation number of graphs. Theor. Comput. Sci., 412(50):7009–
7017, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.09.009, doi:10.1016/j.
tcs.2011.09.009.
Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS,
113, 2014.
Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for
scheduling unrelated parallel machines. Math. Program., 46:259–271, 1990.
John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219–230, 1980. URL: http://dx.doi.
org/10.1016/0022-0000(80)90060-4, doi:10.1016/0022-0000(80)90060-4.
Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization–preprocessing
with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, pages 129–161.
Springer, 2012.
George L. Nemhauser and Leslie E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Math. Program., 6(1):48–61, 1974. URL: http://dx.doi.org/10.
1007/BF01580222, doi:10.1007/BF01580222.
J. M. Robson. Algorithms for maximum independent sets. J. Algorithms, 7(3):425–440,
1986.
Jianhua Tu. A fixed-parameter algorithm for the vertex cover p3 problem. Inf. Process.
Lett., 115(2):96–99, 2015.
Jianhua Tu and Wenli Zhou. A factor 2 approximation algorithm for the vertex cover p3
problem. Inf. Process. Lett., 111(14):683–686, July 2011. URL: http://dx.doi.org/10.
1016/j.ipl.2011.04.009, doi:10.1016/j.ipl.2011.04.009.
David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms.
Cambridge University Press, 2011.
Mingyu Xiao and Shaowei Kou. Faster computation of the maximum dissociation set
and minimum 3-path vertex cover in graphs. In Frontiers in Algorithmics - 9th International Workshop, FAW 2015, Guilin, China, July 3-5, 2015, Proceedings, pages 282–
293, 2015. URL: http://dx.doi.org/10.1007/978-3-319-19647-3_26, doi:10.1007/
978-3-319-19647-3_26.

CVIT 2016

23:14

A 2`k Kernel for `-Component Order Connectivity

24

25

Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. In
Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong,
China, December 16-18, 2013, Proceedings, pages 328–338, 2013.
Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM J. Comput., 10(2):310–327, 1981. URL: http://dx.doi.org/10.1137/0210022, doi:10.1137/
0210022.

