Fixed-Parameter Algorithms for Graph-Modeled Data Clustering - Clustering Challenges in Biological Network - page 8

1.2.1.1. An Introductory Example
Consider our running example V ERTEX C OVER . To reduce the input size for a
given instance of this problem, it is clearly permissible to remove isolated vertices,
that is, vertices with no adjacent edges. This leads to a first simple data reduction
rule.
R EDUCTION R ULE VC1. Remove all isolated vertices.
In order to cover an edge in the graph, one of its two endpoints must be in
the vertex cover. If one of these is a degree-1 vertex, then the other endpoint has
the potential to cover more edges than the degree-1 vertex, leading to a second
reduction rule.
R EDUCTION R ULE VC2. For degree-1 vertices, put their
neighboring vertex into the cover. c
Note that this reduction rule assumes that we are only looking for one optimal
solution to the V ERTEX C OVER instance we are trying to solve; there may exist
other minimum vertex covers that do include the reduced degree-1 vertex.
After having applied the easy rules VC1 and VC2, we can further do the fol-
lowing in the fixed-parameter setting where we ask for a vertex cover of size at
most k .
R EDUCTION R ULE VC3. If there is a vertex v of degree at
least k +1, put v into the cover.
The reason this rule is correct is that if we did not take v into the cover, then
we would have to take every single one of its k +1neighbors into the cover in
order to cover all edges adjacent to v . This is not possible because the maximum
allowed size of the cover is k .
After exhaustively performing the rules VC1-VC3, no vertex in the remaining
graph has a degree higher than k , meaning that choosing a vertex into the cover
can cause at most k edges to become covered. Since the solution set may be no
larger than k , the remaining graph can have at most k 2 edges if it is to have a
solution. By rules VC1 and VC2, every vertex has degree at least two, which
implies that the remaining graph can contain at most k 2 vertices.
c “Put into the cover” means adding the vertex to the solution set and removing it and its incident edges
from the instance.