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

for Ref. 44, 49, 50, we are not aware of fixed-parameter approaches for
such scenarios.

• For simplicity, many fixed-parameter approaches drop the requirement

to be able to handle weighted problems or to handle enumeration. Ex-
tensions of known results in this direction are desirable.

• Of our three case studies, C LIQUE C OVER seems to be the least explored

problem. While kernels with a linear number of vertices are known for
V ERTEX C OVER and C LUSTER E DITING , the only known kernel for
C LIQUE C OVER is of exponential size. Also, no search tree with a fixed-
parameter bound on its size is known for C LIQUE C OVER except for a
trivial brute-force exploration of the problem kernel.

• Some works consider the variant of C LUSTER E DITING where there are

don't care -edges that have zero editing cost [6]. It is not yet known
whether a fixed-parameter algorithm exists for this problem.

A particularly important challenge for future work is to bring progress from
fixed-parameter algorithmics to a broader audience by providing easily accessible
software tools that are finely tuned by algorithm engineering and additional tools
such as heuristics and parallelization.

References

[1] F. N. Abu-Khzam, R. L. Collins, M. R. Fellows, M. A. Langston, W. H. Suters, and

C. T. Symons. Kernelization algorithms for the Vertex Cover problem: theory and
experiments. In Proc. 6th ALENEX , pages 62-69. SIAM, 2004.

[2] F. N. Abu-Khzam, M. A. Langston, and W. H. Suters. Fast, effective vertex cover

kernelization: A tale of two algorithms. In Proc. 3rd AICCSA . ACS/IEEE, 2005. 16
pages.

[3] F. N. Abu-Khzam, M. A. Langston, P. Shanbhag, and C. T. Symons. Scalable parallel

algorithms for FPT problems. Algorithmica , 45(3):269-284, 2006.

[4] N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: rank-

ing and clustering. In Proc. 37th STOC , pages 684-693. ACM, 2005.

[5] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M.

Protasi. Complexity and Approximation: Combinatorial Optimization Problems and
Their Approximability Properties . Springer, 1999.

[6] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning ,

56(1):89-113, 2004.

[7] M. Behrisch and A. Taraz. Efficiently covering complex networks with cliques of

similar vertices. Theoretical Computer Science , 355(1):37-47, 2006.

[8] A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. Journal

of Computational Biology , 6(3-4):281-297, 1999.

M. Benson, M. A. Langston, M. Adner, B. Andersson, A. Torinsson Naluai, and L. O. [9]