Biology Reference
In-Depth Information
Fig. 1.6. An illustration of the partition of the neighborhood of a vertex
v
. The two vertices with
rectangles are exits, the other white ones are prisoners.
one prisoner. If each prisoner is connected to at least one vertex
other than
v
via an edge, and the prisoners dominate the ex-
its, then delete
v
. To reconstruct a solution for the unreduced
instance, add
v
to every clique containing a prisoner of
v
.
Lemma 1.2.
Reduction Rule CC3 is correct.
Proof.
By definition, every neighbor of
v
's prisoners is also a neighbor of
v
itself. If a prisoner of
v
participates in a clique
C
,then
C
is also a clique
in the graph. Therefore, it is correct to add
v
to every clique containing a prisoner
in the reduced graph. Next, we show that all edges adjacent to
v
are covered
by the cliques resulting by adding
v
to the cliques containing
v
's prisoners. We
consider separately the edges connecting
v
to prisoners and edges connecting
v
to exits. Regarding an edge
∪{
v
}
to a prisoner
w
,vertex
w
has to be part of a
clique
C
of the solution for the instance after application of the rule. Therefore,
the edge
{
v,w
}
{v,w}
is covered by
C ∪{v}
in the solution for the unreduced instance.
Regarding an edge
to an exit
x
,theexit
x
is dominated by a prisoner
w
and
therefore
x
has to be part of a clique
C
with
w
. Hence, the edge
{
v,x
}
{
v,x
}
is covered
by
C
∪{
v
}
in the solution for the unreduced instance.
Concerning experimental results, Gramm et al. [35] implemented an algo-
rithm to optimally solve C
LIQUE
C
OVER
that is based on four data reduction
rules (CC1-CC3 and one additional rule) and a simple branching strategy. The
implementation was able to solve within a few seconds 14 real-world instances
from an application in graphical statistics, with up to 124 vertices and more than
2 700 edges [36]. Further experiments on random graphs showed that in particu-
lar sparse instances could be solved quickly. The algorithm relied mainly on the
data reduction rules: many instances were reduced to an empty instance before the
branching even began. By way of contrast, when the data reduction was not suc-
Search WWH ::
Custom Search