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

The purpose of this survey is twofold: First, we provide a primer about some
important and practically relevant techniques for the design of fixed-parameter
algorithms in the realm of graph-modeled data clustering (Sec. 1.2); in particu-
lar, Sec. 1.2.1 exhibits kernelizations (data reductions with provable performance
guarantees) and Sec. 1.2.2 discusses depth-bounded search trees . Second, we
present three concrete case studies from the realm of graph-modeled data clus-
tering where fixed-parameter algorithms have been devised, implemented, and
successfully tested:

•

C LIQUE (Sec. 1.3.1). Using techniques that were originally developed
for the fixed-parameter tractable V ERTEX C OVER problem, it is possi-
ble to detect a size-( n k ) clique in an n -vertex and m -edge graph in

O (1 . 3 k + kn + m ) time [12, 15]. So-called k -isolated cliques ,thatis,
i -vertex cliques that have less than k

−

i edges to vertices that lie outside of
them, can be exhaustively enumerated in O (4 k

·

k 2 m ) time [44, 49, 50].

·

• C LUSTER E DITING (Sec. 1.3.2). In this problem, the assumption is that

the input graph has an underlying cluster structure that is a disjoint union
of cliques, which has been distorted by adding and removing at most k
edges. For an n -vertex input graph, this underlying cluster structure can
be found in O (1 . 92 k + n + m ) time [33, 34, 63].

• C LIQUE C OVER (Sec. 1.3.3). The assumed underlying cluster structure

in this problem is an overlapping union of cliques, that is, the task is to
cover the edges of a given graph with a minimum number of cliques.
Fixed-parameter algorithms allow for optimal problem solutions within
a running time that is competitive with common heuristics [35, 36].

Practical experiments that we discuss in the case studies suggest that the pre-
sented fixed-parameter algorithms are capable of solving many real-world in-
stances in reasonable time. In particular, they perform much better on real-world
data than the provable worst-case bounds suggest. Thus, for some NP-hard clus-
tering problems, fixed-parameter tractability theory offers algorithms which are
both efficient and capable of delivering optimal solutions. It should hence be part
of the algorithmic toolkit for coping with graph-based clustering problems.
We conclude our survey with advice on employing fixed-parameter algorithms
in practice (Sec. 1.4.1) and with a list of specific challenges for future research
(Sec. 1.4.2).