Above guarantee parameterization for vertex cover on graphs with maximum degree 4
Dekel Tsur





Above guarantee parameterization for vertex cover on graphs with maximum degree 4
    Dekel Tsur
Ben-Gurion University of the Negev.
Email: 
    
=================================================================================




In the vertex cover problem, the input is a graph G and an integer k, and
the goal is to decide whether there is a set of vertices S of size
at most k
such that every edge of G is incident on at least one vertex in S.
We study the vertex cover problem on graphs with maximum degree 4 and
minimum degree at least 2, parameterized by r = k-n/3.
We give an algorithm for this problem whose running time is O^*(1.6253^r).
As a corollary, we obtain an O^*(1.2403^k)-time algorithm for vertex
cover on graphs with maximum degree 4.




  
Keywords graph algorithms, parameterized complexity.



§ INTRODUCTION

For an undirected graph G, a vertex cover of G is a set of vertices
S such that every edge of G is incident on at least one vertex in S.
In the parameterized vertex cover problem,
the input is a graph G and an integer k
and the goal is to decide whether there is a vertex cover of G of size
at most k.
The parameterized vertex cover problem has been studied extensively.
The first parameterized algorithm for vertex cover was given
in <cit.>.
Improved algorithms were given in <cit.>.
The parameterized vertex cover problem was also studied on graphs with maximum
degree 3 <cit.>
and maximum degree 4 <cit.>.






Consider the vertex problem on graphs with maximum degree Δ.
It is easy to eliminate vertices with degree at most 1 from the graph.
Thus, we can assume that the input graph has minimum degree at least 2.
It is easy to show that the minimum size of a vertex cover in a graph with
maximum degree Δ and minimum degree at least 2 is at least
2/2+Δn, where n is the number of vertices
(cf. <cit.>).
Therefore, it is more natural to use the “above guarantee” parameter
r_Δ = k-2/2+Δn.
For Δ = 3, Xiao <cit.> gave an algorithm with
O^*(1.6651^r_3) running time.
An O(c^r_Δ)-time algorithm for vertex cover can also give an algorithm
for vertex cover parameterized by k.
Suppose that there is an exponential algorithm for vertex cover on graphs with
maximum degree Δ whose running time is O^*(d^n).
Let α = 1/(2/(2+Δ) + log_c d).
Given an instance (G,k) of vertex cover,
if n > α k, run the parameterized algorithm on (G,k) in
O^*(c^r_Δ) = O^*(d^α k) time,
and otherwise run the exponential algorithm on G in
O^*(d^n) = O^*(d^α k) time.
For graphs with maximum degree 3, combining the O^*(1.6651^r_3)-time
algorithm of Xiao <cit.> with the O(1.0836^n)-time algorithm
of Xiao and Nagamochi <cit.> gives an O^*(1.1558^k)-time
algorithm, which is faster than the previous algorithms given for this
problem <cit.>.

In this paper we give an algorithm for vertex cover on graphs with maximum
degree 4 and minimum degree at least 2 whose running time is
O^*(1.6253^r_4).
Combining our algorithm with the O(1.1376^n)-time algorithm of
Xiao and Nagamochi <cit.> gives an O^*(1.2403^k)-time
algorithm for vertex cover on graphs with maximum degree 4.
This algorithm is faster than the O^*(1.2637^k)-time algorithm of
Agrawal et al. <cit.>.

Our algorithm is similar to the algorithm of Xiao <cit.>
for graphs with maximum degree 3.
Unlike the algorithm of Xiao that uses one branching rule, our algorithm
uses several branching rules.
The branching rules of our algorithm are based on the rules of the algorithm of
Chen et al. <cit.> with minor modifications in order obtain a faster algorithm.
Since the rules of our algorithm are based on the rules
of <cit.>,

we omit the proof of correctness of these rules.



§ PRELIMINARIES

For a graph G and a set of vertices S, G-S is the graph obtained from
G by removing the vertices of S and the edges incident on these vertices.
For a set of vertices S, N(S) = (⋃_v∈ S N(v))∖ S.

The merge operation on a set of vertices S in a graph G generates a
graph G' by deleting the vertices of S and adding a new vertex v^*.
The vertex v^* is adjacent to a vertex u in G' if and only if
there is an edge in G between u and a vertex in S.



 §.§ Reduction rules

In this section we describe several reduction rules that are used by our
algorithm.

Rule (D0) and Rule (D1) below handle vertices with degree at most 1.
While we assume that the input graph has minimum degree 2,
graphs generated during the algorithm can contain vertices with degree 
at most 1 and these rules are used to eliminate such vertices.
D0
If there is a vertex v with degree 0, delete v from G.


D1
If there is a vertex v with degree 1, delete the unique neighbor of v
from G and decrease k by 1.









A general crown in a graph G is a pair C,H of disjoint nonempty
sets of vertices such that the vertices in C have degree 0 in G-H.
A crown C,H is called good if G-C-H has minimum degree at least 2.
A proper crown is a general crown C,H such that
there is a matching between C and H of size |H|.
An almost crown is a general crown C,H such that
|H|=|C|+1 and |N(S)| ≥ |S|+1 for every ∅≠ S⊆ C.
We use the following reduction rules from <cit.>.

C1
If C,H is a proper crown, delete C∪ H from G and decrease k by |H|.

C2
If C,H is an almost crown and H is not an independent set,
delete C∪ H from G and decrease k by |H|.

C3
If C,H is an almost crown and H is an independent set,
merge the vertices in C ∪ H and decrease k by |H|-1.



Let G be a graph with minimum degree at least 2.
If C,H is a general crown and |C| ≥ |H|-1,
it is possible in polynomial time to either find a good proper crown C',H',
or to conclude that C,H is an almost crown.




§ THE ALGORITHM


In this section we give an algorithm for vertex cover parameterized by r = r_4
on graphs with maximum degree at most 4 and minimum degree at least 2.
We first describe an algorithm  for solving the vertex cover problem
on connected graphs with maximum degree at most 3 and
minimum degree at least 2.
The algorithm maintains the following invariants on the current graph:
[(1)]

  * The minimum degree is at least 2.

  * The maximum degree is at most 3.

  * Except for the initial instance, every connected component is not 3-regular.


Before describing algorithm , we give a procedure .
The input to the procedure is an instance (G,k) of vertex cover and
sets of vertices S_1,…,S_t.
The goal of the procedure is to performs branching on the instances
(G-S_1,k-|S_1|),…,(G-S_t,k-|S_t|), after applying Rule (D0)
and Rule (D1) on each instance.
However, it is possible that due to many applications of Rule (D0),
the decrease in r in at least one branch will be too small.
In this case, the procedure performs a suitable reduction rule, or
make a recursive call. When procedure  makes a recursive call,
it marks one of the sets.
Procedure  performs the following steps.


  * 
For i=1,…,t,
repeatedly apply Rule (D0) and Rule (D1) on the instance (G-S_i,k-|S_i|).
Let (G_i,k_i) be resulting instance.
Let C_i be a set containing all the vertices that were
deleted by applications of Rule (D0).
Let H_i be a set containing S_i and all the vertices that were
deleted by applications of Rule (D1)
(note that (G_i,k_i) = (G-C_i-H_i,k-|H_i|)).

  * 
If there is i such that S_i is not marked, C_i ≠∅,
H_i ≠∅, and |C_i| ≥ |H_i|-1:


  * 
Apply Lemma <ref> on the
general crown C_i,H_i and either obtain a good proper crown C,H
in G, or conclude that C_i,H_i is an almost crown in G.

  * 
If C,H is a proper crown, apply Rule (C1) on (G,k) and C,H,
and let (G',k') be the resulting instance.
Return G'k'.

  * 
If H_i is not an independent set, apply Rule (C2) on (G,k) and C_i,H_i,
and let (G',k') be the resulting instance.
Return G'k'.

  * 
If |N(H_i)∖ C_i| ≤ 2, apply Rule (C3) on (G,k) and C_i,H_i,
and let (G',k') be the resulting instance.
Return G'k'.


  * 
Otherwise, call GkH_i,N(H_i), where H_i is marked.



  * 
Return G_1k_1⋯G_tk_t.

Note that the graph G' in line <ref>, <ref>,
or <ref> has minimum degree at least 2 (as C,H and C_i,H_i are
good crowns).








If line <ref>, <ref>, or <ref> of procedure
 is executed,
the value of r does not increase when moving from the
instance (G,k) to the instance (G',k').


Suppose first that line <ref> is executed.
Since G has minimum degree at least 2, the number of edges between
C and H is at least 2|C|.
Each vertex in H has degree at most 4 (we note that we used 4 and not 3 since
we will need this lemma also for the algorithm on graphs with maximum degree 4),
and therefore
the number of edges between C and H is at most 4|H|.
It follows that 2|C|≤ 4|H|.
By definition,
k' = k - |H| and |V(G')| = |V(G)|-|C|-|H|.
Therefore, the value of r decreases by
|H|-(|C|+|H|)/3 = (2|H|-|C|)/3 ≥ 0.








Now suppose that line <ref> is executed.
By definition, k' = k - |H_i| and
|V(G')| = |V(G)|-(|C_i|+|H_i|) = |V(G)|-(2|H_i|-1).
Therefore, the value of r decreases by
|H_i|-(2|H_i|-1)/3 = (|H_i|+1)/3 ≥ 1.








Finally, if line <ref> is executed,
k' = k - (|H_i|-1) and
|V(G')| = |V(G)|-(|C_i|+|H_i|-1) = |V(G)|-2(|H_i|-1).
Therefore, the value of r decreases by
|H_i|-1-2(|H_i|-1)/3 = (|H_i|-1)/3 ≥1/3.



Suppose that line <ref> of procedure  is executed.
For every i such that S_i is not marked,
when moving from the instance (G,k) to the instance (G_i,k_i),
the value of r decreases by at least (|H_i|+2)/3 if |H_i| ≥ 2,
decreases by 2/3 if |H_i|=1, and does not change if |H_i| = 0.


Suppose that |H_i| ≥ 2.
We have that |C_i| ≤ |H_i| - 2 otherwise line <ref> of the
algorithm would not be executed.
By definition, in the instance (G_i,k_i) the value of k decreases
by |H_i| and the value of n decreases by |H_i|+|C_i|.
Therefore, the value of r decreases by |H_i|-(|H_i|+|C_i|)/3 =
(2|H_i|-|C_i|)/3 ≥ (|H_i|+2)/3.

If |H_i| = 1 then |C_i| = 0 otherwise line <ref> of the
algorithm would not be executed.
Therefore, the value of r decreases by 1-1/3 = 2/3.
Finally, if |H_i| = 0 then |C_i| = 0, and the value of r does not change.


We now analyze a call to  in which S_1 is marked and 
line <ref> is executed.
By definition, S_1 = H' and S_2 = N(H'), where C',H' is
an almost crown that was obtained during the parent call to .
Note that since Rules (D0) and (D1) cannot be applied on G-C'-H', it follows
that H_1 = S_1 = H' and C_1 = C'.
When moving from (G,k) to (G_1,k_1), the value
of k decreases by |H_1|=|H'| and the value of n decreases by
|H_1|+|C_1| = 2|H'|-1. Therefore, the value of r decreases by
|H'|-(2|H'|-1) = (|H'|+1)/3 ≥ 1.
By Lemma <ref>, when moving from (G,k) to (G_2,k_2),
the value of r decreases by at least (|H_2|+2)/3 ≥ (|H'|+4)/3 ≥ 2
(|H_2|≥ |S_2| = |N(H')| = |C'|+|N(H') ∖ C'| ≥ |C'|+3 = |H'|+2).
Therefore, the branching vector in this case is at least (1,2) and
the branching number is at most 1.6181.

We now describe algorithm . The algorithm applies
the first applicable rule from the following rules.

If r < 0, return `no'.



If V(G) = ∅ return `yes'.



If there is a vertex v with degree 2 whose two neighbors are not adjacent
and |N(N(v))∖{v}| ≤ 2,
apply Rule (C3) on (G,k) with C = {v} and H = N(v),
and let (G',k') be the resulting instance.
Return G'k'∅.


Note that if Rule () is applied, when moving from (G,k) to
(G',k'), the value of r decreases by |H|-(|C|+|H|)/3 = 1/3.


If there is a vertex v with degree 2 whose two neighbors are not adjacent,
return GkN(v),N(N(v)).

We now analyze the branching number of Rule ().
We can assume that the call to  executes line <ref>
(if line <ref>, <ref> or <ref> is executed then
no branching is performed, and if line <ref> is executed,
we already showed that the branching number is at most 1.6181).
By Lemma <ref>, when procedure  processes the set
S_1 = N(v), the decrease in r is at least
(|H_1|+2)/3 ≥ (|S_1|+2)/3 = 4/3.
Additionally, when procedure  processes the set S_2 = N(N(v)),
the decrease in r is at least (|H_2|+2)/3 ≥ (|S_2|+2)/3 ≥ 2.
Therefore, the branching vector is at least (4/3,2), and the branching
number is at most 1.5248.


If there is a vertex v with degree 2, return GkN(v).




If G is 3-regular, select an arbitrary vertex v and return
Gk{v},N(v).


We do not analyze the branching number of Rule () since this rule is applied
at most once and therefore does not affect the time complexity of the algorithm.
The running time of algorithm  is O^*(1.6181^r).
In order to handle non-connected graphs with maximum degree at most 3,
we use an algorithm  that performs the following steps.


  * If G is connected return Gk.

  * Let G' be a connected component of G.

  * 
For k' = ⌈ |V(G')|/3⌉,…,k-⌈ (n-|V(G')|)/3⌉,
if G'k' returns `yes', return G-V(G')k-k'.

  * Return `no'.

Note that in line <ref> we have k' ≤ k-(n-|V(G')|)/3 and
therefore k'-|V(G')|/3 ≤ k-n/3 = r.
Thus, the time complexity of all the calls to  in line <ref>
is O^*(1.6181^r).
It follows that the running time of algorithm  is O^*(1.6181^r).

We now describe an algorithm  for connected graphs with maximum
degree 4 and minimum degree at least 2.
The algorithm maintains the following invariants on the current graph:
[(1)]

  * 
The minimum degree is at least 2.

  * 
The maximum degree is 4.

  * 
Except for the initial instance, every connected component is not 4-regular.

Let  be a procedure identical to  except that the calls
to  are replaced with calls to .
Algorithm  uses Rules (1)–(<ref>) above,
where the calls to  are replaced with calls to ,
and the following rules.


If the maximum degree of G is at most 3, return Gk.



If G is 4-regular, select an arbitrary vertex v and return
Gk{v},N(v).



If v is a vertex with degree 3 such that there is an edge between
two neighbors u,w of v, return
GkN(v),N(x),
where x is the third neighbor of v.


By Lemma <ref>, the branching vector of Rule () is
at least (5/3,5/3) (since |N(v)| =  3 and |N(x)|≥ 3),
and the branching number is at most 1.5158.


If there is a vertex v with degree 3 and a vertex t such that
|N(t) ∩ N(v)| ≥ 2, return GkN(v),{v,t}.


By Lemma <ref>, the branching vector of Rule () is
at least (5/3,4/3),
and the branching number is at most 1.5906.

For the following rules note that there is a connected component of G
that contains at least one vertex with degree 3 and at least one vertex with
degree 4.
Therefore, there is a vertex v with degree 3 that is adjacent to a vertex
with degree 4.
Denote the neighbors of v by z,u,w, where (z) = 4.
Note that since Rule (<ref>) cannot be applied,
the sets N(z) ∖{v}, N(u) ∖{v}, and
N(w) ∖{v} are pairwise disjoint.


If at least one vertex from u,w has degree 4,
return GkN(v), {z}∪ N(u) ∪ N(w), N(z).


By Lemma <ref>, the branching vector of Rule () is
at least (5/3,3,2) (since |N(v)|=3,
|{z}∪ N(u) ∪ N(w)| ≥ 7, and |N(z)| = 4).
We can improve the bound on the branching vector as follows.
Consider the processing of S_3 = N(z) in procedure .
We consider two cases.
For the first case, assume that Rule (D1) is not applied in
line <ref> of procedure .
We claim that in this case Rule (D0) is applied only on z.
Suppose conversely that the rule is applied on a vertex x ≠ z.
By definition, N(x) ⊆ N(z).
x cannot be u or v since the sets N(z) ∖{v},
N(u) ∖{v}, and N(w) ∖{v} are pairwise disjoint.
Therefore, N(x) ⊆ N(z) ∖{v}.
The graph G has minimum degree 3, and therefore N(x) = N(z) ∖{v}.
It follows that Rule (<ref>) can be applied on x, a contradiction.
Thus, Rule (D0) is applied only on z.
It follows that H_3 = N(z) and C_3 = {z}.
Therefore, the decrease in r is 4 - 5/3 = 7/3.
If Rule (D1) is applied at least once, |H_3| ≥ |S_3|+1 = 5.
By Lemma <ref> the decrease in r is
at least (|H_3|+2)/3 ≥7/3.
We obtained that the branching vector is at least  (5/3,3,7/3)
and the branching number is at most 1.6253.


Otherwise ((u) = (w) = 3), return Gk{z},N(z).


By Lemma <ref>, the branching vector of Rule () is
at least (2/3,2) (since |N(z)| = 4).
We can improve the bound on the branching vector as follows.
Consider the processing of S_1 = {z} in procedure .
Since G has minimum degree 3 and |S_1|=1, we have that G-S_1 has
minimum degree at least 2. Therefore, Rules (D0) and (D1) are not applied by
procedure , so G_1 = G-{z} and k_1 = k-1.
In the instance (G_1,k_1), v has degree 2 and its two neighbors u,w
are not adjacent (since Rule (<ref>) could not be applied on
(G,k)).
Moreover, |N_G_1({u,w})∖{v}| = 4
(since N(u) ∖{v} and N(w)∖{v} are disjoint, and these
sets do not contain z).
Therefore, in the instance (G_1,k_1) Rule (<ref>) can be applied
on v.
We change the algorithm to force that in the instance (G_1,k_1),
Rule (<ref>) will be applied on v (even though the requirement
|N(N(v))∖{v}| ≤ 2 is not satisfied).
The application of Rule (<ref>) on v decreases the value of r by
1/3.
Taking this decrease into account,
the branching vector of Rule () is at least
(2/3+1/3,2) and the branching number is at most 1.6181.

We now show that the algorithm maintains the three invariants defined above.
Suppose that the current input graph G to  satisfies the invariants.
We need to show that the graphs generated from G on which  is
recursively called also satisfy the invariants.
This is straightforward for all the rules of the algorithm except Rule (<ref>).
Consider the application of Rule (<ref>) on G
and the application of Rule (<ref>) on G_1 = G-{z},
and let G_2 be the resulting graph.
We have _G_2(v^*) = |N_G_1({u,w})∖{v}| = 4.
All the other vertices in G_2 have degrees between 2 and 4.
Therefore, G_2 satisfies Invariant (<ref>) and
Invariant (<ref>).
At least one of the two vertices in N(u)∖{v} has degree 3
in G (otherwise Rule (<ref>) can be applied on u).
This vertex also has degree 3 in G_2 (since N(z)∖{v} and
N(u)∖{v}, and N(w)∖{v} are pairwise disjoint)
and therefore G_2 satisfies Invariant (<ref>).

We obtain that algorithm  solves the vertex cover problem on
connected graphs with maximum degree 4 and minimum degree at least 2 in
O^*(1.6253^r) time.
To handle non-connected graph, we use an algorithm  which is analogous to
algorithm .

abbrv


