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