Fixed-parameter algorithms for cluster vertex deletion. (English) Zbl 1205.68263

Summary: We initiate the first systematic study of the NP-hard Cluster Vertex Deletion (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number of vertex deletions to transform a graph into a collection of disjoint cliques. The parameter is the number of vertex deletions. We present efficient fixed-parameter algorithms for CVD applying the fairly new iterative compression technique. Moreover, we study the variant of CVD where the maximum number of cliques to be generated is prespecified. Here, we exploit connections to fixed-parameter algorithms for (weighted) Vertex Cover.
An extended abstract of this paper appeared in Lect. Notes Comput. Sci. 4957, 711–722 (2008; Zbl 1136.68465).


68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85 Graph algorithms (graph-theoretic aspects)


Zbl 1136.68465
Full Text: DOI


[1] Abu-Khzam, F.N.: Kernelization algorithms for d-hitting set problems. In: Proc. 10th WADS. Lecture Notes in Computer Science, vol. 4619, pp. 434–445. Springer, Berlin (2007) · Zbl 1209.68610
[2] Abu-Khzam, F.N., Fernau, H.: Kernels: Annotated, proper and induced. In: Proc. 2nd IWPEC. Lecture Notes in Computer Science, vol. 4169, pp. 264–275. Springer, Berlin (2006) · Zbl 1154.68559
[3] Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: Ranking and clustering. In: Proc. 37th STOC, pp. 684–693. Assoc. Comput. Math., New York (2005) · Zbl 1192.90252
[4] Ailon, N., Charikar, M., Newman, A.: Proofs of conjectures in ”Aggregating inconsistent information: Ranking and clustering”. Technical Report TR-719-05, Department of Computer Science, Princeton University (2005) · Zbl 1192.90252
[5] Böcker, S., Briesemeister, S., Bui, Q.B.A., Truß, A.: A fixed-parameter approach for weighted cluster editing. In: Proc. 6th APBC. Series on Advances in Bioinformatics and Computational Biology, vol. 5, pp. 211–220. Imperial College Press, London (2008)
[6] Böcker, S., Briesemeister, S., Bui, Q.B.A., Truß, A.: Going weighted: Parameterized algorithms for cluster editing. In: Proc. 2nd COCOA. Lecture Notes in Computer Science, vol. 5165, pp. 1–12. Springer, Berlin (2008) · Zbl 1168.68441
[7] Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996) · Zbl 0875.68702
[8] Cai, M.-C., Deng, X., Zang, W.: An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30(6), 1993–2007 (2001) · Zbl 0980.68053
[9] Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for vertex cover. In: Proc. 31st MFCS. Lecture Notes in Computer Science, vol. 4162, pp. 238–249. Springer, Berlin (2006) · Zbl 1132.68421
[10] Dehne, F., Langston, M.A., Luo, X., Pitre, S., Shaw, P., Zhang, Y.: The cluster editing problem: Implementations and experiments. In: Proc. 2nd IWPEC. Lecture Notes in Computer Science, vol. 4169, pp. 13–24. Springer, Berlin (2006) · Zbl 1154.68451
[11] Dom, M., Guo, J., Hüffner, F., Niedermeier, R., Truß, A.: Fixed-parameter tractability results for feedback set problems in tournaments. In: Proc. 6th CIAC. Lecture Notes in Computer Science, vol. 3998, pp. 320–331. Springer, Berlin (2006) · Zbl 1183.68419
[12] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
[13] Fellows, M.R., Langston, M.A., Rosamond, F.A., Shaw, P.: Efficient parameterized preprocessing for cluster editing. In: Proc. 16th FCT. Lecture Notes in Computer Science, vol. 4639, pp. 312–321. Springer, Berlin (2007) · Zbl 1135.68511
[14] Fernau, H.: Parameterized algorithms for hitting set: The weighted case. In: Proc. 6th CIAC. Lecture Notes in Computer Science, vol. 3998, pp. 332–343. Springer, Berlin (2006) · Zbl 1183.68426
[15] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
[16] Fomin, F.V., Gaspers, S., Kratsch, D., Liedloff, M., Saurabh, S.: Iterative compression and exact algorithms. In: Proc. 33rd MFCS. Lecture Notes in Computer Science, vol. 5162, pp. 335–346. Springer, Berlin (2008) · Zbl 1173.68537
[17] Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
[18] Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18(5), 1013–1036 (1989) · Zbl 0679.68079
[19] Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. Theory Comput. 2, 249–266 (2006) · Zbl 1213.68704
[20] Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004) · Zbl 1090.68027
[21] Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: Exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373–392 (2005) · Zbl 1084.68117
[22] Guo, J.: A more effective linear kernelization for cluster editing. In: Proc. 1st ESCAPE. Lecture Notes in Computer Science, vol. 4614, pp. 36–47. Springer, Berlin (2007). Long version to appear in Theoretical Computer Science · Zbl 1176.05078
[23] Guo, J., Moser, H., Niedermeier, R.: Iterative compression for exactly solving NP-hard minimization problems. In: Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science. Springer, Berlin (2008, to appear) · Zbl 1248.68380
[24] Hüffner, F.: Algorithms and experiments for parameterized approaches to hard graph problems. Ph.D. thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena (2007) · Zbl 1250.05107
[25] Hüffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. Comput. J. 51(1), 7–25 (2008) · Zbl 05534205
[26] Jansen, K., Scheffler, P., Woeginger, G.: The disjoint cliques problem. RAIRO Rech. Opér. 31(1), 45–66 (1997) · Zbl 0881.90123
[27] Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980) · Zbl 0436.68029
[28] Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Proc. 20th ICALP. Lecture Notes in Computer Science, vol. 700, pp. 40–51. Springer, Berlin (1993) · Zbl 1310.68094
[29] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, London (2006) · Zbl 1095.68038
[30] Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms 47(2), 320–331 (2003) · Zbl 1046.68058
[31] Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73, 125–129 (2006) · Zbl 1014.68064
[32] Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst. (2008, to appear) · Zbl 1179.68111
[33] Rahmann, S., Wittkop, T., Baumbach, J., Martin, M., Truß, A., Böcker, S.: Exact and heuristic algorithms for weighted cluster editing. In: Proc. 6th CSB. Computational Systems Bioinformatics, vol. 6, pp. 391–401. Imperial College Press, London (2007)
[34] Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446–458 (2006) · Zbl 1086.68105
[35] Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004) · Zbl 1052.05061
[36] Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Appl. Math. 144(1–2), 173–182 (2004) · Zbl 1068.68107
[37] Wahlström, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Department of Computer and Information Science, Linköpings universitet (2007)
[38] van Zuylen, A., Williamson, D.P.: Deterministic algorithms for rank aggregation and other ranking and clustering problems. In: Proc. 5th WAOA. Lecture Notes in Computer Science, vol. 4927, pp. 260–273. Springer, Berlin (2008) · Zbl 1130.68342
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.