Biology Reference
In-Depth Information
R EDUCTION R ULE CC2.
whose
endpoints have exactly the same closed neighborhood, that is,
N [ u ]= N [ v ], then delete u . To reconstruct a solution for the
unreduced instance, add u to every clique containing v .
If there is an edge
{
u,v
}
Rules CC1 and CC2 together suffice to show the problem kernel (the basic
underlying observation was already made by Gyarfas [41]).
Theorem 1.5 (Gy arf as [41] and Gramm et al. [35]). A C LIQUE C OVER in-
stance reduced with respect to Rules CC1 and CC2 contains at most 2 k vertices
or, otherwise, has no solution.
Proof. Consider a graph G =( V,E ) that is reduced with respect to Rules CC1
and CC2 and has a clique cover C 1 ,...,C k of size k . We assign to each vertex v
V a binary vector b v of length k where bit i , 1
i
k ,issetiff v is contained
If we assume that G has more than 2 k vertices, then there must
in clique C i .
be u
V with b u = b v . Since Rule CC1 does not apply, every vertex is
contained in at least one clique, and since b u = b v , u and v are contained in the
same cliques. Therefore, u and v are connected. As they also share the same
neighborhood, Rule CC2 applies, in contradiction to our assumption that G is
reduced with respect to Rule CC2. Consequently, G cannot have more than 2 k
vertices.
= v
ByTheorem1.1,thisimpliesthatC LIQUE C OVER is fixed-parameter tractable
with respect to parameter k . Unfortunately, the worst-case size of a reduced in-
stance is still exponential, as opposed to the polynomially-sized kernels that are
known for V ERTEX C OVER and C LUSTER E DITING .
As an example of an advanced data reduction rule, we now formulate a gen-
eralization of Rule CC2. While one can show that this rule finds a strict superset
of the reduction opportunities of Rule CC2, it does not seem possible to use it to
improve the worst-case problem kernel size bound in Theorem 1.5. Nevertheless,
Rule CC2 improves the running time of solving C LIQUE C OVER in practice, as
described below.
To discuss the advanced data reduction rule, we need some additional termi-
nology: For a vertex v , we partition the set of vertices that are connected by an
edge to v into prisoners p with N ( p )
.
We say that the prisoners dominate the exits if every exit x has an adjacent pris-
oner.
N ( v ) and exits x with N ( x )
\
N ( v )
=
An illustration of the concept of prisoners and exits is given in Fig. 1.6.
R EDUCTION R ULE CC3. Consider a vertex v that has at least
Search WWH ::




Custom Search