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

caused by distinguishing more and more cases pays off. A simpler algorithm with
slightly worse bounds on the search tree size often turns out to be preferable in
practice. Here, recent progress with the analysis of search tree algorithms using
multivariate recurrences [27] might help: with this method, it was shown that
some simple algorithms perform in fact much better than previously proved [31].
Also, new algorithms were developed guided by the new analysis methods [31];
however, there is no practical experience yet with these approaches.
In combination with data reduction (see Sec. 1.3.1), the use of depth-bounded
search trees has proven itself quite useful in practice, allowing to find vertex covers
of more than ten thousand vertices in some dense graphs of biological origin [3].
Search trees also trivially allow for a parallel implementation: when branching
into subcases, each processor in a parallel setting can further explore one of these
branches with no additional communication required. Cheetham et al. [14] expose
this in their parallel V ERTEX C OVER solver to achieve a near-optimum (i.e., lin-
ear with the number of processors employed) speedup on multiprocessor systems.
Finally, it is generally beneficial to augment search tree algorithms with admis-
sible heuristic evaluation functions in order to further increase their performance
and memory efficiency by cutting away search tree parts that cannot lead to good
solutions [29, 51].
1.3. Case Studies from Graph-Modeled Data Clustering
This section surveys fixed-parameter algorithms and experimental results for three
important NP-complete problems from the realm of graph-modeled data cluster-
ing, namely C LIQUE ,C LUSTER E DITING ,andC LIQUE C OVER . The purpose of
these case studies is twofold: First, they serve to teach in more detail the method-
ological approaches of designing kernelizations and depth-bounded search trees.
Second, the encouraging experimental results that are known for these problems
underpin the general usefulness of fixed-parameter algorithms for optimally solv-
ing NP-hard problems in graph-modeled data clustering.
1.3.1. Clique
A “classical” combinatorial problem that is closely connected to graph-modeled
data clustering is to find a clique in a graph, that is, a subset of vertices that are
fully connected.
C LIQUE
I NPUT : An undirected graph G =( V,E ) and a nonnegative