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

Fig. 1.4. Illustration for the C LUSTER E DITING problem: By removing two edges from and adding
one edge to the graph on the left (that is, k =3), we can obtain a graph that consists of two disjoint
cliques.

by adding or removing edges. C LUSTER E DITING appears as an important prob-
lem in the analysis of data from synthetic genetic arrays [8, 23].

C LUSTER E DITING
Input: An undirected graph G =( V,E ) and a nonnegative in-
teger k .
Ta s k : Modify G to consist of disjoint cliques by adding or
deleting at most k edges.

Figure 1.4 illustrates this problem. C LUSTER E DITING is NP-hard [53, 66],
and its minimization version can be approximated in polynomial time within a
factor of 4 [13]. A randomized expected factor-3 approximation algorithm was
given by Ailon et al. [4]. C LUSTER E DITING is also a special case of the C OR -
RELATION C LUSTERING problem occurring in machine learning [6].
In what follows, we concentrate on a search tree-based fixed-parameter ap-
proach towards exactly solving C LUSTER E DITING . Here, the overall strategy is
based on an easy-to-see observation, namely that a cluster graph has a very special
structure: If two vertices are connected by an edge, then their neighborhoods must
be the same. Hence, whenever we encounter two connected vertices u and v in the
input graph G that are connected by an edge and where one vertex, say u ,hasa
neighbor w that is not connected to v , we call a conflict triple of vertices

because it compels us to do one of three things: Either remove the edge

{ u,v,w }

{ u,v } ,

or connect v with w , or remove the edge . Each of these three modifica-

tions counts with respect to the parameter k and, therefore, exhaustively branching
into these cases for at most k forbidden substructures, we obtain a search tree of
size O (3 k ) to solve C LUSTER E DITING .
The search tree size can be significantly reduced. More specifically, a more so-
phisticated branching strategy gives a search tree size of O (2 . 27 k ) [34], which—
using computer-generated branching rules—has been further improved to a size
of O (1 . 92 k ) [33]. The computer-generated result, however, is based on a quite
complicated branching with lots of case distinctions that might not be of practical
value. In the following, we describe the key observations and fundamental ideas
behind the improved search trees for C LUSTER E DITING . As a remark, there also

{ u,w }