Kernelization and Parameterized Algorithms for
3-Path Vertex Cover ⋆

arXiv:1608.07022v1 [] 25 Aug 2016

Mingyu Xiao and Shaowei Kou
School of Computer Science and Engineering,
University of Electronic Science and Technology of China, Chengdu 611731, China
myxiao@gmail.com, kou sw@163.com

Abstract. A 3-path vertex cover in a graph is a vertex subset C such
that every path of three vertices contains at least one vertex from C. The
parameterized 3-path vertex cover problem asks whether a graph has a
3-path vertex cover of size at most k. In this paper, we give a kernel of
5k vertices and an O∗ (1.7485k )-time polynomial-space algorithm for this
problem, both new results improve previous known bounds.

1

Introduction

A vertex subset C in a graph is called an ℓ-path vertex cover if every path of
ℓ vertices in the graph contains at least one vertex from C. The ℓ-path vertex
cover problem, to find an ℓ-path vertex cover of minimum size, has been studied
in the literature [5,6]. When ℓ = 2, this problem becomes the famous vertex
cover problem and it has been well studied. In this paper we study the 3-path
vertex cover problem. A 3-path vertex cover is also known as a 1-degree-bounded
deletion set. The d-degree-bounded deletion problem [11,25,26] is to delete a
minimum number of vertices from a graph such that the remaining graph has
degree at most d. The 3-path vertex cover problem is exactly the 1-degreebounded deletion problem. Several applications of 3-path vertex covers have
been proposed in [6,16,27].
It is not hard to establish the NP-hardness of the 3-path vertex cover problem
by reduction from the vertex cover problem. In fact, it remains NP-hard even
in planar graphs [28] and in C4 -free bipartite graphs with vertex degree at most
3 [4]. There are several graph classes, in which the problem can be solved in
polynomial time [2,3,4,6,7,14,15,18,19,20].
The 3-path vertex cover problem has been studied from approximation algorithms, exact algorithms and parameterized algorithms. There is a randomized
23
[16]. In
approximation algorithm with an expected approximation ratio of 11
∗
n
terms of exact algorithms, Kardoš et al. [16] gave an O (1.5171 )-time algorithm to compute a maximum dissociation set in an n-vertex graph. Chang et
al. [8] gave an O∗ (1.4658n)-time algorithm and the result was further improved
to O∗ (1.3659n) later [27].
⋆

This is the version accepted by TAMC 2016. To appear in: TAMC 2016, LNCS 9796,
pp. 1–15, 2016.

2

In parameterized complexity, this problem is fixed-parameter tractable by
taking the size k of the 3-path vertex cover as the parameter. The running
time bound of parameterized algorithm for this problem has been improved at
least three times during the last one year. Tu [22] showed that the problem can
be solved in O∗ (2k ) time. Wu [24] improved the result to O∗ (1.882k ) by using
the measure-and-conquer method. The current best result is O∗ (1.8172k ) by
Katrenič [17]. In this paper we will further improve the bound to O∗ (1.7485k ).
Another important issue in parameterized complexity is kernelization. A kernelization algorithm is a polynomial-time algorithm which, for an input graph
with a parameter (G, k) either concludes that G has no 3-path vertex cover of
size k or returns an equivalent instance (G′ , k ′ ), called a kernel, such that k ′ ≤ k
and the size of G′ is bounded by a function of k. Kernelization for the d-degreebounded deletion problem has been studied in the literature [11,25]. For d = 1,
Fellows et al.’s algorithm [11] implies a kernel of 15k vertices for the 3-path vertex
cover problem, and Xiao’s algorithm [25] implies a kernel of 13k vertices. There
is another closed related problem, called the 3-path packing problem. In this
problem, we are going to check if a graph has a set of at least k vertex-disjoint
3-paths. When we discuss kernelization algorithms, most structural properties
of the 3-path vertex cover problem and the 3-path packing problem are similar.
Several previous kernelization algorithms for the 3-path packing problem are
possible to be modified for the 3-path vertex cover problem. The bound of the
kernel size of the 3-path packing problem has been improved for several times
from the first bound of 15k [21] to 7k [23] and then to 6k [10]. Recently, there is a
paper claiming a bound of 5k vertices for the 3-path packing problem in net-free
graphs [9]. Although the paper [9] provides some useful ideas, the proof in it is
incomplete and the algorithm may not stop. Several techniques for the 3-path
packing problem in [23] and [9] will be used in our kernelization algorithm. We
will give a kernel of 5k vertices for the 3-path vertex cover problem.
Omitted proofs in this extended abstract can be found in the full version of
this paper.

2

Preliminaries

We let G = (V, E) denote a simple and undirected graph with n = |V | vertices
and m = |E| edges. A singleton {v} may be simply denoted by v. The vertex set
and edge set of a graph G′ are denoted by V (G′ ) and E(G′ ), respectively. For a
subgraph (resp., a vertex subset) X, the subgraph induced by V (X) (resp., X)
is simply denoted by G[X], and G[V \ V (X)] (resp., G[V \ X]) is also written
as G \ X. A vertex in a subgraph or a vertex subset X is also called a X-vertex.
For a vertex subset X, let N (X) denote the set of open neighbors of X, i.e.,
the vertices in V \ X adjacent to some vertex in X, and N [X] denote the set of
closed neighbors of X, ie., N (X) ∪ X. The degree of a vertex v in a graph G,
denoted by d(v), is defined to be the number of vertices adjacent to v in G. Two
vertex-disjoint subgraphs X1 and X2 are adjacent if there is an edge with one
endpoint in X1 and the other in X2 . The number of connected components in

3

a graph G is denoted by Comp(G) and the number of connectedP
components of
size i in a graph G is denoted by Compi (G). thus, Comp(G) = i Compi (G).
A 3-path, denoted by P3 , is a simple path with three vertices and two edges.
A vertex subset C is called a 3-path vertex cover or a P3 V C-set if there is no
3-path in G \ C. Given a graph G = (V, E), a P3 -packing P = {L1 , L2 , ..., Lt }
of size t is a collection of vertex-disjoint P3 in G, i.e., each element Li ∈ P is a
3-path in G and V (Li1 ) ∩ V (Li2 ) = ∅ for any two different 3-paths Lii , Li2 ∈ P.
A P3 -packing is maximal if it is not properly contained in any strictly larger
P3 -packing in G. The set of vertices in 3-paths in P is denoted by V (P).
Let P be a P3 -packing and A be a vertex set such that A ∩ V (P) = ∅ and A
induces a graph of maximum degree 1. We use Ai to denote the set of degree-i
vertices in the induced graph G[A] for i = 0, 1. A component of two vertices
in G[A] is called an A1 -edge. For each Li ∈ P, we use A(Li ) to denote the set
of A-vertices that are in the components of G[A] adjacent to Li . For a 3-path
Li ∈ P, the degree-2 vertex in it is called the middle vertex of it and the two
degree-1 vertices in it are call the ending vertices of it.

3

A Parameterized Algorithm

In this section we will design a parameterized algorithm for the 3-path vertex cover problem. Our algorithm is a branch-and-reduce algorithm that runs
in O∗ (1.7485k ) time and polynomial space, improving all previous results. In
branch-and-reduce algorithms, the exponential part of the running time is determined by the branching operations in the algorithm. In a branching operation,
the algorithm solves the current instance I by solving several smaller instances.
We will use the parameter k as the measure of the instance and use T (k) to
denote the maximum size of the search tree generated by the algorithm running
on any instance with parameter at most k. A branching operation, which generates l small branches with measure decrease in the i-th branch being at least ci ,
creates a recurrence relation T (k) ≤ T (k−c1 )+T (k−c2 )+· · ·+T (k−cl )+1. The
Pl
largest root of the function f (x) = 1 − i=1 x−ci is called the branching factor
of the recurrence. Let γ be the maximum branching factor among all branching factors in the algorithm. The running time of the algorithm is bounded by
O∗ (γ k ). More details about the analysis and how to solve recurrences can be
found in the monograph [13]. Next, we first introduce our branching rules and
then present our algorithm.
3.1

Branching Rules

We have four branching rules. The first branching rule is simple and easy to
observe.
Branching rule (B1): Branch on a vertex v to generate |N [v]| + 1 branches by
either
(i) deleting v from the graph, including it to the solution set, and decreasing k
by 1, or

4

(ii) deleting N [v] from the graph, including N (v) to the solution set, and decreasing k by |N (v)|, or
(iii) for each neighbor u of v, deleting N [{u, v}] from the graph, including N ({u, v})
to the solution set, and decreasing k by |N ({u, v})|.
A vertex v is dominated by a neighbor u of it if v is adjacent to all neighbors
of u. The following property of dominated vertices has been proved and used
in [27].
Lemma 1. Let v be a vertex dominated by u. If there is a minimum 3-path
vertex cover C not containing v, then there is a minimum 3-path vertex cover
C ′ of G such that v, u ∈
/ C ′ and N ({u, v}) ⊆ C ′ .
Based on this lemma, we design the following branching rule.
Branching rule (B2): Branch on a vertex v dominated by another vertex u to
generate two instances by either
(i) deleting v from the graph, including it to the solution set, and decreasing k
by 1, or
(ii) deleting N [{u, v}] from the graph, including N ({u, v}) to the solution set,
and decreasing k by |N ({u, v})| = |N (v)| − 1.
For a vertex v, a vertex s ∈ N2 (v) is called a satellite of v if there is a
neighbor p of v such that N [p] − N [v] = {s}. The vertex p is also called the
parent of the satellite s at v.
Lemma 2. Let v be a vertex that is not dominated by any other vertex. If v
has a satellite, then there is a minimum 3-path vertex cover C such that either
v ∈ C or v, u 6∈ C for a neighbor u of v.
Branching rule (B3): Let v be a vertex that has a satellite but is not dominated
by any other vertex. Branch on v to generate |N [v]| instances by either
(i) deleting v from the graph, including it to the solution set, and decreasing k
by 1, or
(ii) for each neighbor u of v, deleting N [{u, v}] from the graph, including N ({u, v})
to the solution set, and decreasing k by |N ({u, v})|.
Lemma 3. Let v be a degree-3 vertex with a degree-1 neighbor u1 and two adjacent neighbors u2 and u3 . There is a minimum 3-path vertex cover C such that
either C ∪ {u1 , v} = ∅ or C ∪ {u1 , u2 , u3 } = ∅.
Branching rule (B4): Let v be a degree-3 vertex with a degree-1 neighbor u1
and two adjacent neighbors u2 and u3 . Branch on v to generate two instances
by either
(i) deleting N [{u1 , v}] from the graph, including {u2 , u3 } to the solution set, and
decreasing k by 2, or
(ii) deleting N [{u2 , u3 }] ∪ {u1 } from the graph, including N ({u2 , u3 }) to the
solution set, and decreasing k by |N ({u2 , u3 })|.

5

3.2

The Algorithm

We will use P3VC(G, k) to denote our parameterized algorithm. The algorithm
contains 7 steps. When we execute one step, we assume that all previous steps
are not applicable anymore on the current graph. We will analyze each step after
describing it.
Step 1 (Trivial cases) If k ≤ 0 or the graph is an empty graph, then return
the result directly. If the graph has a component of maximum degree 2, find a
minimum 3-path vertex cover S of it directly, delete this component from the
graph, and decrease k by the size of S.
After Step 1, each component of the graph contains at least four vertices. A
degree-1 vertex v is called a tail if its neighbor u is a degree-2 vertex. Let v be a
tail, u be the degree-2 neighbor of v, and w be the other neighbor of u. We show
that there is a minimum 3-path vertex cover containing w but not containing
any of u and v. At most one of u and v is contained in any minimum 3-path
vertex cover C, otherwise C ∪ {w} \ {u, v} would be a smaller 3-path vertex
cover. If none of u and v is in a minimum 3-path vertex cover C, then w must be
in C to cover the 3-path uvw and then C is a claimed minimum 3-path vertex
cover. If exactly one of u and v is contained in a minimum 3-path vertex cover
C, then C ′ = C ∪ {w} \ {u, v} is a claimed minimum 3-path vertex cover.
Step 2 (Tails) If there is a degree-1 vertex v with a degree-2 neighbor u,
then return p3vc(G \ N [{v, u}], k − 1).
Step 3 (Dominated vertices of degree ≥ 3) If there is a vertex v of degree ≥ 3 dominated by u, then branch on v with Rule (B2) to generate two
branches
p3vc(G \ {v}, k − 1)

and

p3vc(G \ N [{v, u}], k − |N ({v, u})|).

Lemma 1 guarantees the correctness of this step. Note that |N ({v, u})| = d(v)−1.
This step gives a recurrence
T (k) ≤ T (k − 1) + T (k − (d(v) − 1)) + 1,

(1)

where d(v) ≥ 3. For the worst case that d(v) = 3, the branching factor of it is
1.6181.
A degree-1 vertex with a degree-1 neighbor will be handled in Step 1, a degree1 vertex with a degree-2 neighbor will be handled in Step 2, and a degree-1 vertex
with a neighbor of degree ≥ 3 will be handled in Step 3. So after Step 3, the
graph has no vertex of degree ≤ 1. Next we consider degree≥ 4 vertices.
Step 4 (Vertices of degree ≥ 4 with satellites) If there is a vertex v of
d(v) ≥ 4 having a satellite, then branch on v with Rule (B3) to generate d(v) + 1
branches
p3vc(G\{v}, k−1)

and

p3vc(G\N [{v, u}], k−|N ({v, u})|) for each u ∈ N (v).

6

The correctness of this step is guaranteed by lemma 2. Note that there is no
dominated vertex after Step 3. Each neighbor u of v is adjacent to at least one
vertex in N2 (v) and then |N ({v, u})| ≥ d(v).
This step gives a recurrence
T (k) ≤ T (k − 1) + d(v) · T (k − d(v)) + 1,

(2)

where d(v) ≥ 4. For the worst case that d(v) = 4, the branching factor of it is
1.7485.
After Step 4, if there is still a vertex of degree ≥ 4, we use the following
branching rule. Note that now each neighbor u of v is adjacent to at least two
vertices in N2 (v) and then |N ({v, u})| ≥ d(v) + 1.
Step 5 (Normal vertices of degree ≥ 4 ) If there is a vertex v of d(v) ≥
4, then branch on v with Rule (B1) to generate d(v) + 2 branches
p3vc(G \ {v}, k − 1),
and

p3vc(G \ N [v], k − |N (v)|)
p3vc(G \ N [{v, u}], k − |N ({v, u})|) for each u ∈ N (v).

Since |N ({v, u})| ≥ d(v) + 1, this step gives a recurrence
T (k) ≤ T (k − 1) + T (k − d(v)) + d(v) · T (k − (d(v) + 1)) + 1,

(3)

which d(v) ≥ 4. For the worst case that d(v) = 4, the branching factor of it is
1.6930.
After Step 5, the graph has only degree-2 and degree-3 vertices. We first
consider degree-2 vertices.
A path u0 u1 u2 u3 of four vertices is called a chain if the first vertex u0 is of
degree ≥ 3 and the two middle vertices are of degree 2. Note that there is no
chain with u0 = u3 after Step 3. So when we discuss a chain we always assume
that u0 6= u3 . A chain can be found in linear time if it exists. In a chain u0 u1 u2 u3 ,
u2 is a satellite of u0 with a parent u1 .
Step 6 (Chains) If there is a chain u0 u1 u2 u3 , then branch on u0 with
Rule (B3). In the branch where u0 is deleted and included to the solution set, u1
becomes a tail and we further handle the tail as we do in Step 2.
We get the following branches
and

p3vc(G \ N [{u1 , u2 }], k − 2)

p3vc(G \ N [{u0 , u}], k − |N ({u0 , u})|) for each u ∈ N (u0 ).

Note that |N ({u0 , u})| ≥ d(u0 ) since there is no dominated vertex. We get a
recurrence
T (k) ≤ T (k − 2) + d(u0 ) · T (k − d(u0 )) + 1,

where d(u0 ) ≥ 3. For the worst case that d(u0 ) = 3, the branching factor of it is
1.6717.
After Step 6, each degree-2 vertex must have two nonadjacent degree-3 vertices. Note that no degree-2 is in a triangle if there is no dominated vertex.

7

Step 7 (Degree-2 vertices with a neighbor in a triangle) If there is a
degree-2 vertex v with N (v) = {u, w} such that a neighbor u of it is in a triangle
uu1 u2 , then branch on w with Rule (B1) and then in the branch w is deleted
and included in the solution set further branch on u with Rule (B4). We get the
following branches
p3vc(G \ N [{u, v}], k − |N ({u, v})|),
p3vc(G \ N [{u1 , u2 }] ∪ {u, w}, k − |N ({u1 , u2 }) ∪ {w}|), and

p3vc(G \ N [{w, u′ }], k − |N ({w, u′ })|) for each u′ ∈ N (w).

There two neighbors u and w of v are degree-3 vertices. Since there is no
dominated vertex, for any edge v1 v2 it holds |N ({v1 , v2 })| ≥ min{d(v1 ), d(v2 )}.
We know that |N ({u, v})| ≥ d(u) = 3, |N ({u1 , u2 }) ∪ {w}| ≥ |N ({u1 , u2 })| ≥ 3
(since no degree-2 vertex is in a triangle) and |N ({w, u′ })| ≥ d(w) for each
u′ ∈ N (w). We get the following recurrence
T (k) ≤ T (k − 3) + T (k − 3) + 3 · T (k − 3) + 1.
The branching factor of it is 1.7100.
After Step 7, no degree-3 vertex in a triangle is adjacent to a degree-2 vertex.
Step 8 (Degree-2 vertices v with a degree-3 vertex in N2 (v)) If there
is a degree-2 vertex v such that at least one of its neighbors u and w, say u, has
a degree-3 neighbor u1 , then branch on u with Rule (B1) and in the branch where
u is deleted and included to the solution set, branch on w with Rule (B2). We
get the branches
p3vc(G \ {u, v, w}, k − 2), p3vc(G \ N [{w, v}], k − |N ({w, v})|),
and p3vc(G \ N [{u, u′ }], k − |N ({u, u′ })|) for each u′ ∈ N (u).
Note that d(u) = d(w) = 3. It holds |N ({w, v})| ≥ d(w) = 3 and |N ({u, u′ })| ≥
d(u) = 3 for u′ ∈ N (u). Furthermore, we have that |N ({u, u1 })| ≥ 4 because u
and u1 are degree-3 vertices not in any triangle. We get the following recurrence
T (k) ≤ T (k − 2) + T (k − 3) + 2 · T (k − 3) + T (k − 4).
The branching factor of it is 1.7456.
Lemma 4. After Step 8, if the graph is not an empty graph, then each component of the graph is either a 3-regular graph or a bipartite graph with one side
of degree-2 vertices and one side of degree-3 vertices.
Lemma 5. Let G = (V1 ∪ V2 , E) be a bipartite graph such that all vertices in V1
are of degree 2 and all vertices in V2 are of degree 3. The set V1 is a minimum
3-path vertex cover of G.
Step 9 (Bipartite graphs) If the graph has a component H being a bipartite graph with one side V1 of degree-2 vertices and one side V2 of degree-3
vertices, then return p3vc(G \ H, k − |V1 |).

8

Step 10 (3-regular graphs) If the graph is a 3-regular graph, pick up an
arbitrary vertex v and branch on it with Rule (B1).
Lemma 4 shows that the above steps cover all the cases, which implies the correctness of the algorithm. Note that all the branching operations except Step 10
in the algorithm have a branching factor at most 1.7485. We do not analyze
the branching factor for Step 10, because this step will not exponentially increase the running time bound of our algorithm. Any proper subgraph of a
connected 3-regular graph is not a 3-regular graph. For each connected component of a 3-regular graph, Step 10 can be applied for at most one time and all
other branching operations have a branching factor at most 1.7485. Thus each
connected component of a 3-regular graph can be solved in O∗ (1.7485k ) time.
Before getting a connected component of a 3-regular graph, the algorithm always
branches with branching factors of at most 1.7485. Therefore,
Theorem 1. The 3-path vertex cover problem can be solved in O∗ (1.7485k ) time
and polynomial space.

4

Kernelization

In this section, we show that the parameterized 3-path vertex cover problem
allows a kernel with at most 5k vertices.
4.1

Graph decompositions

The kernelization algorithm is based on a vertex decomposition of the graph,
called good decomposition, which can be regarded as an extension of the crown
decomposition [1]. Based on a good decomposition we show that an optimal
solution to a special local part of the graph is contained in an optimal solution
to the whole graph. Thus, once we find a good decomposition, we may be able
to reduce the graph by adding some vertices to the solution set directly. We
only need to find good decompositions in polynomial time in graphs with a large
size to get problem kernels. Some previous rules to kernels for the parameterized
3-path packing problem [10,12,23] are adopted here to find good decompositions
in an effective way.
Definition 1. A good decomposition of a graph G = (V, E) is a decomposition
(I, C, R) of the vertex set V such that
1. the induced subgraph G[I] has maximum degree at most 1;
2. the induced subgraph G[I ∪ C] has a P3 -packing of size |C|;
3. no vertex in I is adjacent to a vertex in R.
Lemma 6. A graph G that admits a good decomposition (I, C, R) has a P3 vertex cover (resp., P3 -packing) of size k if and only if G[R] has a P3 -vertex
cover (resp., P3 -packing) of size k − |C|.

9

Lemma 6 provides a way to reduce instances of the parameterized 3-path
vertex cover problem based on a good decomposition (I, C, R) of the graph:
deleting I ∪ C from the graph and adding C to the solution set. Here arise a
question: how to effectively find good decompositions? It is strongly related to
the quality of our kernelization algorithm. The kernel size will be smaller if we
can polynomially compute a good decomposition in a smaller graph. Recall that
we use Comp(G′ ) and Compi (G′ ) to denote the number of components and
number of components with i vertices in a graph G′ , respectively. For a vertex
subset A that induces a graph of maximum degree at most 1 and j = {1, 2}, we
use Nj (A) ⊆ N (A) to denote the set of vertices in N (A) adjacent to at least one
component of size j in G[A], and N2′ (A) ⊆ N2 (A) be the set of vertices in N (A)
adjacent to at least one component of size 2 but no component of size 1 in G[A].
We will use the following lemma to find good decompositions, which was also
used in [9] to design kernel algorithms for the 3-path packing problem.
Lemma 7. Let A be a vertex subset of a graph G such that each connected
component of the induced graph G[A] has at most 2 vertices. If
Comp(G[A]) > 2|N (A)| − |N2′ (A)|,

(4)

then there is a good decomposition (I, C, R) of G such that ∅ =
6 I ⊆ A and
C ⊆ N (A). Furthermore, the good decomposition (I, C,
R)
together
with a P3 √
packing of size |C| in G[I ∪ C] can be computed in O( nm) time.
By using Lemma 7, we can get a linear kernel for the parameterized 3-path
vertex cover problem quickly. We find an arbitrary maximal P3 -packing S and let
A = V \ V (S). We assume that S contains less than k 3-paths and then |V (S)| <
3k, otherwise the problem is solved directly. Note that |N (A)| ⊆ |V (S)|. If
|A| > 12k, then Comp(G[A]) ≥ |A|
2 > 6k > 2|V (S)| ≥ 2|N (A)| and we reduce
the instance by Lemma 7. So we can get a kernel of 15k vertices. This bound
can be improved by using a special case of Lemma 7.
For a vertex subset A such that G[A] has maximum degree at most 1. Let A0
be the set of degree-1 vertices in G[A]. Note that Comp(G[A0 ]) = Comp2 (G[A])
and |N (A0 )| = |N2 (A0 )| = |N2 (A)|. By applying Lemma 7 on A0 , we can get
Corollary 1 Let A be a vertex subset of a graph G such that each connected
component of the induced graph G[A] has at most 2 vertices. Let N2 (A) ⊆ N (A)
be the set of vertices in N (A) adjacent to at least one vertex in a component of
size 2 in G[A]. If
Comp2 (G[A]) > |N2 (A)|,

(5)

then there is a good decomposition (I, C, R) of G such that ∅ =
6 I ⊆ A and
C ⊆ N (A). Furthermore, the good decomposition (I, C,
R)
together
with a P3 √
packing of size |C| in G[I ∪ C] can be computed in O( nm) time.
Note that |A| = Comp1 (G[A])+2·Comp2 (G[A]). If |A| > 9k, then Comp1 (G[A])+
2 · Comp2 (G[A]) = |A| > 9k > 3|V (S)| ≥ 3|N (A)| ≥ (2|N (A)| − |N2′ (A)|) +

10

|N2 (A)| and at least one of (4) and (5) holds. Then by using Lemma 7 and
Corollary 1, we can get a kernel of size 9k + 3k = 12k. It is possible to bound
|N (A)| by k and then to get a kernel of size 3k + 3k = 6k. To further improve
the kernel size to 5k, we need some sophisticated techniques and deep analyses
on the graph structure.
4.2

A 5k kernel

In this section, we use “crucial partitions” to find good partitions. A vertex
partition (A, B, Z) of a graph is called a crucial partition if it satisfies Basic
Conditions and Extended Conditions. Basic Conditions include the following
four items:
(B1)
(B2)
(B3)
(B4)

A induces a graph of degree at most 1;
B is the vertex set of a P3 -packing P;
No vertex in A is adjacent to a vertex in Z;
|Z| ≤ 5 · γ(G[Z]), where γ(G[Z]) is the size of a minimum P3 V C-set in the
induced subgraph G[Z].

Before presenting the definition of Extended Conditions, we give some used
definitions. We use Pj to denote the collection of 3-paths in P having j vertices
adjacent to A-vertices (j = 0, 1, 2, 3). Then P = P0 ∪ P1 ∪ P2 ∪ P3 . We use P 1 to
denote the collection of 3-paths L ∈ P such that |A(L)| = 1. We also partition
P1 \ P 1 into two parts:
let PM ⊆ P1 \ P 1 be the collection of 3-paths with the middle vertex adjacent
to some A-vertices;
let PL ⊆ P1 \ P 1 be the collection of 3-paths Li such that |A(Li )| ≥ 2 and one
ending vertex of Li is adjacent to some A-vertices.
A vertex in a 3-path in P is free if it is not adjacent to any A-vertex. A
3-path in P0 is bad if it has at least two vertices adjacent to some free-vertex in
a 3-path in PL and good otherwise. A 3-path in PL is bad if it is adjacent to a
bad 3-path in P0 and good otherwise.
Extended Conditions include the following seven items:
(E1) For each 3-path Li ∈ P \ P 1 , at most one vertex in Li is adjacent to some
vertex in A, i.e., P \ P 1 = P0 ∪ P1 ;
(E2) No 3-path in PM is adjacent to both of A0 -vertices and A1 -vertices;
(E3) No free-vertex in a 3-path in PL is adjacent to a free-vertex in another 3-path
in PL ;
(E4) No free-vertex in a 3-path in PL is adjacent to a free-vertex in a 3-path in
PM ;
(E5) Each 3-path in P 1 has at most one vertex adjacent to a free-vertex in a
3-path in PL ;
(E6) If a 3-path in P 0 has at least two vertices adjacent to some free-vertex in
a 3-path in PL , then all those free-vertices are from one 3-path in PL , i.e.,
each bad 3-path in P 0 is adjacent to free-vertices in only one bad 3-path in
PL ;

11

(E7) No free-vertex in a 3-path in PL is adjacent to a vertex in Z.
Lemma 8. A crucial partition of the vertex set of any given graph can be found
in polynomial time.
After obtaining a crucial partition (A, B, Z), we use the following three reduction rules to reduce the graph. In fact, Extended Conditions are mainly used
for the third reduction rule and the analysis of the kernel size.
Reduction Rule 1 If the number of 3-paths in P is greater than k − |Z|/5,
halt and report it as a no-instance.
Note that each P3 V C-set of the graph G must contain at least |Z|/5 vertices
in Z by Basic Condition (B4) and each P3 V C-set must contain one vertex from
each 3-path in P. If the number of 3-paths in P is greater than k − |Z|/5, then
any P3 V C-set of the graph has a size greater than k.
Reduction Rule 2 If Comp2 (G[A]) > |N2 (A)| (the condition in Corollary 1) holds, then find a good decomposition by Corollary 1 and reduce the
instance based on the good decomposition.
Reduction Rule 2 is easy to observe. Next, we consider the last reduction
rule. Let B ∗ be the set of free-vertices in good 3-paths in PL and let A∗ be
the set of A0 -vertices adjacent to 3-paths in P 1 . Let A′ = A ∪ B ∗ \ A∗ . By the
definition of crucial decompositions, we can get that
Lemma 9. The set A′ still induces of a graph of maximum degree 1.
Proof. Vertices in B ∗ are free-vertices and then any vertex in B ∗ is not adjacent
to a vertex in A. Furthermore, no two free-vertices in B ∗ from two different 3paths in PL are adjacent by Extended Condition (E3). Since A induces a graph
of maximum degree 1, we know that A ∪ B ∗ induces a graph of maximum degree
1. The set A′ = A ∪ B ∗ \ A∗ is a subset of A ∪ B ∗ and then A′ induces of a graph
of maximum degree 1.
⊓
⊔
Based on Lemma 9, we can apply the following reduction rule.
Reduction Rule 3 If Comp(G[A′ ]) > 2|N (A′ )| − |N2′ (A′ )| (the condition
in Lemma 6 on set A′ ) holds, then find a good decomposition by Lemma 6 and
reduce the instance based on the good decomposition.
Next, we assume that none of the three reduction rules can be applied and
prove that the graph has at most 5k vertices.
We consider a crucial partition (A, B, Z) of the graph. Let k1 be the number
of 3-paths in P. Since Reduction Rule 1 cannot be applied, we know that
k1 ≤ k − |Z|/5.

(6)

12

Since Reduction Rule 2 and Reduction Rule 3 cannot be applied, we also have
the following two relations
Comp2 (G[A]) ≤ |N2 (A)|,

(7)

Comp(G[A′ ]) ≤ 2|N (A′ )| − |N2′ (A′ )|.

(8)

and

By Extended Condition (E1), we know that P = P0 ∪ P1 ∪ P 1 = P0 ∪
PL ∪ PM ∪ P 1 . Let x1 and x2 be the numbers of good and bad 3-paths in PL ,
respectively. Let yi (i = 0, 1) be the number of 3-paths in P0 with i vertices
adjacent to some free-vertex in a 3-path in PL , and y2 be the number of 3-paths
in P0 with at least two vertices adjacent to some free-vertex in a 3-path in PL ,
i.e., the number of bad 3-paths in P0 . Let z1 and z2 be the numbers of 3-paths
in PM adjacent to only A0 -vertices and only A1 -vertices, respectively. Let w1 be
the number of 3-paths in P 1 adjacent to some free-vertex in a 3-path in PL and
w2 be the number of 3-paths in P 1 not adjacent to any free-vertex in a 3-path
in PL . We get that
k1 = x1 + x2 + y0 + y1 + y2 + z1 + z2 + w1 + w2 .

(9)

By Extended Conditions (E1) and (E2), we know that
|N (A)2 | ≤ x1 + x2 + z2 .

(10)

Extended Condition (E6) implies the number of bad 3-paths in PL is at most
the number of bad 3-paths in P0 , i.e.,
x2 ≤ y2 .

(11)

Each 3-path in P 1 is adjacent to only one A0 -vertex. Since A∗ is the set of
A0 -vertices adjacent to 3-paths in P 1 , we know that |A∗ | is not greater than
w1 + w2 , i.e., the number of 3-paths in P 1 . By the definition of A′ , we know that
Comp(G[A′ ]) ≥ Comp(G[A]) + x1 − (w1 + w2 ).

(12)

Next, we consider |N (A′ )| and |N2′ (A′ )|. Note that each 3-path has at most
one vertex adjacent to vertices in A \ A∗ by Extended Condition (E1). This
property will also hold for the vertex set A′ = (A \ A∗ ) ∪ B ∗ . We prove the
following two relations
|N (A′ )| ≤ x1 + x2 + y0 + y1 + z1 + z2 + w1 ,

(13)

|N2′ (A′ )| ≥ y1 + z2 + w1 .

(14)

and

By Extended Conditions (E1) and (E3), we know that each 3-path in PL has at
most one vertex in N ((A \ A∗ ) ∪ B ∗ ) = N (A′ ). By the definition of good 3-paths

13

in P0 , we know that each good 3-path in P0 has no vertex adjacent to vertices
in A and has at most one vertex adjacent to vertices in B ∗ (which will be in a
component of size 2 in G[A′ ]). There are exactly y1 vertices in good 3-paths in
P0 adjacent to vertices in B ∗ . No vertex in a bad 3-path in P0 is adjacent to a
vertex in A ∪ B ∗ by the definitions of bad 3-paths and B ∗ . Each 3-path in PM
has at most one vertex adjacent to A′ by Extended Conditions (E1) and (E4).
Only z2 vertices in 3-paths in PM are adjacent to vertices in A′ , all of which are
vertices of degree-1 in G[A′ ]. No vertex in a 3-path in P 1 is adjacent to a vertex
in A \ A∗ ⊇ A′ by the definition of A∗ . Furthermore, each 3-path in P 1 has at
most one vertex adjacent to vertices in B ∗ (which will be in a component of size
2 in G[A′ ]) by Extended Condition (E5) and there are exactly w1 vertices in
3-paths in P 1 adjacent to vertices in B ∗ . No vertex in Z is adjacent to a vertex
in A ∪ B ∗ by Basic Condition (B3) and Extended Condition (E7). Summing all
above up, we can get (13) and (14).
Relations (8), (12), (13) and (14) imply
Comp(G[A]) ≤ 2(x2 + y0 + z1 + w1 ) + x1 + y1 + z2 + w2 .

(15)

According to (7) and (10), we know that
Comp2 (G[A]) ≤ x1 + x2 + z2 .

(16)

Note that |A| = Comp(G[A]) + Comp2 (G[A]), we get
|A| = Comp(G[A]) + Comp2 (G[A])
≤ 2(x1 + x2 + y0 + z1 + z2 + w1 ) + x2 + y1 + w2
≤ 2(x1 + x2 + y0 + z1 + z2 + w1 ) + y2 + y1 + w2
≤ 2k1

by (15) and (16)
by (11)
by (9).

Note that |B| = 3k1 and k1 ≤ k − |Z|/5 by (6). We get that
|V | = |A| + |B| + |Z|
≤ 5k1 + |Z| ≤ 5k.
Theorem 2. The parameterized 3-path vertex cover problem allows a kernel of
at most 5k vertices.

References
1. FN.Abu-Khzam, RL.Collins, MR.Fellows, MA.Langston: Kernelization Algorithms
for the Vertex Cover Problem: Theory and Experiments. ALENEX/ANALC. 62–69
(2004)
2. V.E.Alekseev, R.Boliac, D.V.Korobitsyn, V.V.Lozin: NP-hard graph problems and
boundary classes of graphs. Theoretical Computer Science. 389(1–2), 219–236 (2007)
3. K.Asdre, S.D.Nikolopoulos, C.Papadopoulos: An optimal parallel solution for the
path cover problem on P4 -sparse graphs. Journal of Parallel and Distributed Computing. 67(1), 63–76 (2007)

14
4. R.Boliac, K.Cameron, V.V.Lozin: On computing the dissociation number and the
induced matching number of bipartite graphs. Ars Combinatoria. 72, 241–253 (2004)
5. B.Brešar, M.Jakovac, J.Katrenič, G.Semanišin, A.Taranenko: On the vertex k-path
cover. Discrete Applied Mathematics. 161(13–14), 1943–1949 (2013)
6. B.Brešar, F.Kardoš, J.Katrenič, G.Semanišin: Minimum k-path vertex cover. Discrete Applied Mathematics. 159(12), 1189–1195 (2011)
7. K.Cameron, P.Hell: Independent packings in structured graphs. Mathematical Programming. 105(2–3) , 201–213 (2006)
8. M-S.Chang, L-H.Chen, L-J.Hung, Y-Z.Liu, P.Rossmanith, S.Sikdar: An
O∗ (1.4658n )-time exact algorithm for the maximum bounded-degree-1 set
problem. In: The 31st Workshop on Combinatorial Mathematics and Computation
Theory. pp, 9–18 (2014)
9. M-S.Chang, L-H.Chen, L-J.Huang: A 5k kernel for P2 -packing in net-free graphs.
International Computer Science and Engineering Conference, 12–17, IEEE (2014)
10. J.Chen, H.Fernau, P.Shaw, J.Wang, Z.Yang: Kernels for Packing and Covering
Problems. In FAW-AAIM 2012, LNCS 7285, 199–211. Springer, Heidelberg (2012)
11. MR.Fellows, J.Guo, H.Moser, R.Niedermeier: A generalization of Nemhauser and
Trotter’s local optimization theorem. JCSS 77(6), 1141–1158 (2011)
12. H.Fermau, D.Raible: A parameterized perspective on packing paths of length two.
Journal of Combinatorial Optimization. 18(4), 319–341 (2009)
13. F.V.Fomin, D.Kratsch: Exact exponential algorithms. Berlin:Springer (2010)
14. F.Göring, J.Harant, D.Rautenbach, I.Schiermeyer: On F-independence in graphs.
Discussiones Mathematica Graph Theory. 29(2), 377–383 (2009)
15. R-W.Hung, M-S.Chang: Finding a minimum path cover of a distance-hereditary
graph in polynomial time. Discrete Applied Mathematics. 155(17), 2242–2256 (2007)
16. F.Kardoš, J.Katrenič: On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoretical Computer Science. 412(50), 7009–7017 (2011)
17. J.Katrenič: A faster FPT algorithm for 3-path vertex cover. Information Processing
Letters. 116(4): 273–278(2016)
18. V.V.Lozin, D.Rautenbach: Some results on graphs without long induced paths.
Information Processing Letters. 88(4), 167–171 (2003)
19. Y.Orlovich, A.Dolgui, G.Finke, V.Gordon, F.Werner: The complexity of dissociation set problems in graphs. Disc. Appl. Math. 159(13), 1352–1366 (2011)
20. C.H.Papadimitriou, M.Yannakakis: The complexity of restricted spanning tree
problems. Journal of ACM. 29(2), 285–309 (1982)
21. E.Prieto, C.Sloper: Looking at the stars. Theor. Comp. Sci. 351(3), 437–445 (2006)
22. J.Tu: A fixed-parameter algorithm for the vertex cover P3 problem. Information
Processing Letters. 115(2), 96–99 (2015)
23. J.Wang, D.Ning, Q.Feng, J.Chen: An improved kernelization for P2 -packing. Information Processing Letters. 110(5), 188–192 (2010)
24. B.Y.Wu: A Measure and Conquer Approach for the Parameterized Bounded
Degree-One Vertex Deletion. In: COCOON 2015. LNCS 9198, 469–480 (2015)
25. M.Xiao: On a Generalization of Nemhauser and Trotter’s Local Optimization Theorem. In: ISAAC 2015. LNCS 9472, pp. 442–452. Springer, Heidelberg (2015)
26. M. Xiao: A Parameterized Algorithm for Bounded-Degree Vertex Deletion. In:
T.N. Dinh and M.T. Thai (Eds.): COCOON 2016, Springer, Heidelberg (2016)
27. M.Xiao, S.Kou: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theoretical Computer Science. (2016)
doi:10.1016/j.tcs.2016.04.043
28. M.Yannakakis: Node-deletion problems on bipartite graphs. SIAM Journal on
Computing. 10(2), 310–327 (1981)

