Fixed-Parameter Algorithms for Graph-Modeled Data Clustering - Clustering Challenges in Biological Network - page 15

include expert knowledge as to what cliques that are present in the input graph are
(biologically) “meaningful.”
Analogously to the task of finding a maximum-size clique, the task of enu-
merating maximal cliques in a graph is equivalent to enumerating minimal vertex
covers for its complement graph. To enumerate all maximal cliques in a graph, one
can therefore rely on kernelizations for V ERTEX C OVER that are suited for find-
ing all vertex covers up to a certain size [17] and on enumerative depth-bounded
search trees such as discussed by Damaschke [21]. However, so far there is no
empirical evidence of the practical viability of this approach.
An interesting result concerning the enumeration of maximal cliques that
makes a more “indirect” use of V ERTEX C OVER was recently shown by Ito et
al. [44]. It is based on an alternative parameterization other than the clique size.
This parameterization is based on the observation that the hardness of finding a
large clique in a graph is determined by the isolation of that clique, meaning that
if we restrict ourselves to finding cliques that have only a few edges to “external”
vertices outside of the clique, then this is a much easier task compared to finding
cliques that have many edges to external vertices. The intuitive reason for this
is that isolated cliques are better distinguishable from the remaining graph. To
quantify the isolation of a clique, Ito et al. [44] introduced the notion of an iso-
lation factor k .An i -vertex clique is said to be k -isolated if it has less than k

i
edges to external vertices. It turns out that enumerating all k -isolated cliques is
fixed-parameter tractable with respect to k . Komusiewicz et al. [49, 50] pointed
out an error in the algorithm and provided a corrected version.

·

Theorem 1.3. (Ito et al. [44], Komusiewicz et al. [49, 50]). All k -isolated cliques
in an m -edge graph can be enumerated in O (4 k k 2 m ) time. ·

The underlying algorithm of this result is based on a search tree for V ER -
TEX C OVER ; the main achievement lies in showing that the isolation factor k can
also serve as a bound for the depth of this search tree, which is achieved by a
parameter-dependent data reduction. This nicely demonstrate the benefit of al-
ternative parameterizations for a problem. Ito et al. [44] mentioned that some
preliminary experiments suggest that the detection of isolated cliques is quite ef-
ficient in practice.

1.3.2. Cluster Editing

The C LUSTER E DITING problem is based on the assumption that the input graph
is a disjoint union of cliques—a so-called cluster graph —that has been perturbed