Biology Reference
In-Depth Information
A
crown
in a graph consists of an independent set
I
(that is, no two vertices
in
I
are connected by an edge) and a set
H
containing all vertices adjacent to
I
.In
order for
I
matching in the bipartite
graph induced by the edges between
I
and
H
(i.e., one in which every vertex of
H
is matched). An example for a crown structure is given in Fig. 1.3. If there is a
crown
I
∪
H
tobeacrown,therehastobeasize-
|
H
|
vertices to cover all
edges in the crown. But since all edges in the crown can be covered by taking
at
most
∪
H
in the input graph
G
, then we need
at least
|
H
|
vertices into the cover (as
I
is an independent set), there is a minimum-
size vertex cover for
G
that contains all the vertices in
H
and none of the vertices
in
I
. We may thus delete any given crown
I
|
H
|
.
It turns out that finding crowns can be achieved in polynomial time by com-
puting maximum matchings [18]. The size of the thus reduced instance is upper-
bounded via the following theorem.
∪
H
from
G
, reducing
k
by
|
H
|
Theorem 1.2 (Abu-Khzam et al. [1]).
A graph that is crown-free and has a ver-
tex cover of size at most
k
can contain at most
3
k
vertices.
There are several kernelizations for V
ERTEX
C
OVER
that achieve a kernel of
O
(
k
) vertices; some of these even yield an at-most-2
k
-vertex kernel, e.g., see
Ref. 1, 60. However, it has been found that crown reductions often offer a good
balance between the polynomial time that is required to compute the kernel and
the size that the reduced graphs usually turn out to have in practice [1-3].
Some quite successful implementations for solving C
LIQUE
rely on kerneliza-
tion techniques (especially crown reductions) for V
ERTEX
C
OVER
that are com-
bined with depth-bounded search trees [1, 2, 74]. The exploration of the search
trees is usually highly optimized, for instance, by using efficient data structures
and ensuring proper load balancing in parallel scenarios; details of these tech-
niques are described, e.g., by Abu-Khzam et al. [1] and Zhang et al. [74] Even
attempts to implement parts of the algorithms in hardware have been reported [3].
With the combination of kernelizations and depth-bounded search trees, it is
currently possible to find cliques that consist of over 400 vertices in some dense
graphs of biological origin within hours [3].
1.3.1.2.
Enumerating Maximal Cliques
Instead of finding a single maximum-size clique in a graph, one would often like
to enumerate all cliques of maximal size. In graph-modeled data clustering, this
can have mainly two reasons: First, an enumeration obviously identifies
all
clus-
ters that are present in the data. Second, with an enumerative solution one can
Search WWH ::
Custom Search