Abstract
In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques).
Hüffner et al. [LATIN 2008, Theory Comput. Syst. 2010] initiated the parameterized study of Cluster Vertex Deletion, where the allowed modification is vertex deletion, and presented an elegant \(\mathcal{O}(2^k k^9 + nm)\)-time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for Cluster Vertex Deletion and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2k-barrier for Cluster Vertex Deletion and present an \(\mathcal{O}(1.9102^k (n+m))\)-time branching algorithm.
Partially supported by NCN grant N206567140 and Foundation for Polish Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.N.: A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences 76(7), 524–531 (2010)
Abu-Khzam, F.N., Fernau, H.: Kernels: Annotated, proper and induced. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 264–275. Springer, Heidelberg (2006)
Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: Ranking and clustering. Journal of the ACM 55(5), 23:1–23:27 (2008)
Alon, N., Makarychev, K., Makarychev, Y., Naor, A.: Quadratic forms on graphs. In: Proceedings of STOC 2005, pp. 486–493. ACM (2005)
Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Machine Learning 56, 89–113 (2004)
Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. Journal of Computational Biology 6(3/4), 281–297 (1999)
Böcker, S.: A golden ratio parameterized algorithm for cluster editing. Journal of Discrete Algorithms 16, 79–89 (2012)
Böcker, S., Briesemeister, S., Bui, Q.B.A., Truß, A.: Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science 410(52), 5467–5480 (2009)
Böcker, S., Briesemeister, S., Klau, G.W.: Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica 60(2), 316–334 (2011)
Böcker, S., Damaschke, P.: Even faster parameterized cluster deletion and cluster editing. Information Processing Letters 111(14), 717–721 (2011)
Bodlaender, H.L., Fellows, M.R., Heggernes, P., Mancini, F., Papadopoulos, C., Rosamond, F.A.: Clustering with partial information. Theoretical Computer Science 411(7-9), 1202–1211 (2010)
Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: Fast branching algorithm for cluster vertex deletion. CoRR, abs/1306.3877 (2013)
Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58(4), 171–176 (1996)
Charikar, M., Wirth, A.: Maximizing quadratic programs: Extending Grothendieck’s inequality. In: Proceedings of FOCS 2004, pp. 54–60. IEEE Computer Society (2004)
Damaschke, P.: Fixed-parameter enumerability of cluster editing and related problems. Theory of Computing Systems 46(2), 261–283 (2010)
Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optimization 8(1), 2–17 (2011)
Fernau, H.: A top-down approach to search-trees: Improved algorithmics for 3-hitting set. Algorithmica 57(1), 97–118 (2010)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in theoretical computer science. Springer, Heidelberg (2010)
Fomin, F.V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., Villanger, Y.: Tight bounds for parameterized complexity of cluster editing. In: Proceedings of STACS 2013. LIPIcs, vol. 20, pp. 32–43. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Leibniz-Zentrum fuer Informatik (2013)
Giotis, I., Guruswami, V.: Correlation clustering with a fixed number of clusters. Theory of Computing 2(1), 249–266 (2006)
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)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Graph-modeled data clustering: Exact algorithms for clique generation. Theory of Computing Systems 38(4), 373–392 (2005)
Guo, J., Kanj, I.A., Komusiewicz, C., Uhlmann, J.: Editing graphs into disjoint unions of dense clusters. Algorithmica 61(4), 949–970 (2011)
Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM Journal of Discrete Mathematics 24(4), 1662–1683 (2010)
Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 711–722. Springer, Heidelberg (2008)
Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory of Computing Systems 47(1), 196–217 (2010)
Komusiewicz, C.: Parameterized Algorithmics for Network Analysis: Clustering & Querying. PhD thesis, Technische Universität Berlin (2011), http://fpt.akt.tu-berlin.de/publications/diss-komusiewicz.pdf
Komusiewicz, C., Uhlmann, J.: Alternative parameterizations for cluster editing. In: Černá, I., Gyimóthy, T., Hromkovič, J., Jefferey, K., Králović, R., Vukolić, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 344–355. Springer, Heidelberg (2011)
Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory of Computing Systems 44(1), 91–104 (2009)
Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters 32(4), 299–301 (2004)
Shamir, R., Sharan, R., Tsur, D.: Cluster graph modification problems. Discrete Applied Mathematics 144(1-2), 173–182 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M. (2014). A Fast Branching Algorithm for Cluster Vertex Deletion. In: Hirsch, E.A., Kuznetsov, S.O., Pin, JÉ., Vereshchagin, N.K. (eds) Computer Science - Theory and Applications. CSR 2014. Lecture Notes in Computer Science, vol 8476. Springer, Cham. https://doi.org/10.1007/978-3-319-06686-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-06686-8_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06685-1
Online ISBN: 978-3-319-06686-8
eBook Packages: Computer ScienceComputer Science (R0)