Biology Reference
In-Depth Information
I
H
G
Fig. 1.3. A graph
G
with a crown
I∪H
. The thick edges constitute a maximum matching of size
|H|
in the bipartite graph that is induced by the edges between
I
and
H
.
integer
k
.
T
ASK
:Finda
k
-vertex clique in
G
.
It is also a common task to
enumerate
maximal cliques in a graph, that is, all
cliques that are not a proper subset of any other clique.
C
LIQUE
is NP-hard [32] and hard to approximate in polynomial time [42]. In
a similar sense as it is generally assumed that P
= NP, it is strongly believed that
C
LIQUE
is not fixed-parameter tractable when parameterized by the size of the
cliques that are sought after [25]. Nevertheless, C
LIQUE
has a close connection
to the fixed-parameter tractable V
ERTEX
C
OVER
problem that we used as our
running example to introduce fixed-parameter techniques: If an
n
-vertex graph
contains a size-
k
clique, then its
complement graph
g
contains a size-(
n
k
) vertex
cover and vice versa. This can be made use of when seeking after or enumerating
cliques.
−
1.3.1.1.
Finding Maximum Cardinality Cliques
The catch when solving C
LIQUE
for a graph
G
by means of finding a minimum-
cardinality vertex cover for the complement graph
G
is that if the maximum size
k
of a clique in
G
is rather small compared to its total number of vertices
n
,then
G
will have a rather large minimum-size vertex cover. Therefore, one has to rely
on effective data reduction rules that preprocess the complement graph
G
so that
depth-bounded search tree algorithms become practically applicable for the re-
duced graph that remains. One kernelization for V
ERTEX
C
OVER
that has proven
itself to be of particular practical importance in this respect is the so-called
crown
reduction
[1], which generalizes the V
ERTEX
C
OVER
data reduction rule VC2
(the elimination of degree-1 vertices by taking their neighbors into the cover) and
thus leads to a data reduction that requires no explicit knowledge of the parame-
ter
k
and yields a kernel with a number of vertices
linear
in
k
.
g
That is, the graph that contains exactly those edges that are not contained in the original graph.
Search WWH ::
Custom Search