Document Open Access Logo

Clustering to Given Connectivities

Authors Petr A. Golovach , Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.18.pdf
  • Filesize: 0.67 MB
  • 17 pages

Document Identifiers

Author Details

Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Dimitrios M. Thilikos
  • AlGCo project-team, LIRMM, Université de Montpellier, CNRS, Montpellier, France

Funding

  • Golovach, Petr A.: Supported by the Research Council of Norway via the projects CLASSIS and MULTIVAL. Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.
  • Thilikos, Dimitrios M.: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

Cite AsGet BibTex

Petr A. Golovach and Dimitrios M. Thilikos. Clustering to Given Connectivities. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2019.18

Abstract

We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an n-vertex graph G, an integer k, and a sequence Lambda=<lambda_{1},...,lambda_{t}> of positive integers and we ask whether it is possible to remove at most k edges from G such that the resulting connected components are exactly t and their corresponding edge connectivities are lower-bounded by the numbers in Lambda. We prove that this problem, parameterized by k, is fixed parameter tractable, i.e., can be solved by an f(k)* n^{O(1)}-step algorithm, for some function f that depends only on the parameter k. Our algorithm uses the recursive understanding technique that is especially adapted so to deal with the fact that we do not impose any restriction to the connectivity demands in Lambda.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • graph clustering
  • edge connectivity
  • parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nir Ailon, Moses Charikar, and Alantha Newman. Proofs of Conjectures in "Aggregating Inconsistent Information: Ranking and Clustering". Technical Report TR-719-05, Department of Computer Science, Princeton University, USA, 2005. Google Scholar
  2. Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Inventiones mathematicae, 163(3):499-522, March 2006. Google Scholar
  3. Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. On Non-Approximability for Quadratic Programs. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 206-215, 2005. Google Scholar
  4. Balabhaskar Balasundaram, Sergiy Butenko, and Illya V. Hicks. Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem. Operations Research, 59(1):133-142, 2011. URL: https://doi.org/10.1287/opre.1100.0851.
  5. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation Clustering. Machine Learning, 56(1):89-113, July 2004. Google Scholar
  6. Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering Gene Expression Patterns. Journal of Computational Biology, 6(3/4):281-297, 1999. Google Scholar
  7. Pavel Berkhin. A Survey of Clustering Data Mining Techniques. In Grouping Multidimensional Data - Recent Advances in Clustering, pages 25-71. Springer, 2006. Google Scholar
  8. Nadja Betzler, Jiong Guo, Christian Komusiewicz, and Rolf Niedermeier. Average parameterization and partial kernelization for computing medians. Journal of Computer and System Sciences, 77(4):774-789, 2011. Google Scholar
  9. Ivan Bliznets and Nikolay Karpov. Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, pages 6:1-6:14, 2017. Google Scholar
  10. S. Böcker, S. Briesemeister, Q.B.A. Bui, and A. Truss. Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science, 410(52):5467-5480, 2009. Google Scholar
  11. Sebastian Böcker. A golden ratio parameterized algorithm for Cluster Editing. Journal of Discrete Algorithms, 16:79-89, 2012. Selected papers from the 22nd International Workshop on Combinatorial Algorithms (IWOCA 2011). URL: https://doi.org/10.1016/j.jda.2012.04.005.
  12. Sebastian Böcker and Jan Baumbach. Cluster Editing. In Paola Bonizzoni, Vasco Brattka, and Benedikt Löwe, editors, The Nature of Computation. Logic, Algorithms, Applications, pages 33-44, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  13. Sebastian Böcker, Sebastian Briesemeister, Quang Bao Anh Bui, and Anke Truß. A Fixed-Parameter Approach for Weighted Cluster Editing. In Proceedings of the 6th Asia-Pacific Bioinformatics Conference, APBC 2008, 14-17 January 2008, Kyoto, Japan, pages 211-220, 2008. Google Scholar
  14. Sebastian Böcker and Peter Damaschke. Even faster parameterized cluster deletion and cluster editing. Information Processing Letters, 111(14):717-721, 2011. Google Scholar
  15. Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, and Frances Rosamond. Clustering with partial information. Theoretical Computer Science, 411(7):1202-1211, 2010. Google Scholar
  16. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. In IWPEC, volume 4169 of Lecture Notes in Computer Science, pages 239-250. Springer, 2006. URL: https://doi.org/10.1007/11847250_22.
  17. Yixin Cao and Jianer Chen. Cluster Editing: Kernelization Based on Edge Cuts. Algorithmica, 64(1):152-169, September 2012. Google Scholar
  18. Jianer Chen and Jie Meng. A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences, 78(1):211-220, 2012. JCSS Knowledge Representation and Reasoning. URL: https://doi.org/10.1016/j.jcss.2011.04.001.
  19. Rajesh Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT Algorithms for Cut Problems Using Randomized Contractions. SIAM J. Comput., 45(4):1171-1229, 2016. URL: https://doi.org/10.1137/15M1032077.
  20. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  21. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  22. Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. Clique Cover and Graph Separation: New Incompressibility Results. TOCT, 6(2):6:1-6:19, 2014. Google Scholar
  23. Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed parameter tractable. In STOC 2014, pages 323-332. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591852.
  24. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  25. Martin Dörnfelder, Jiong Guo, Christian Komusiewicz, and Mathias Weller. On the parameterized complexity of consensus clustering. Theor. Comput. Sci., 542:71-82, 2014. Google Scholar
  26. Rodney G. Downey, Vladimir Estivill-Castro, Michael R. Fellows, Elena Prieto, and Frances A. Rosamond. Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems. Electr. Notes Theor. Comput. Sci., 78:209-222, 2003. URL: https://doi.org/10.1016/S1571-0661(04)81014-4.
  27. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  28. Jubin Edachery, Arunabha Sen, and Franz J. Brandenburg. Graph Clustering Using Distance-k Cliques. In Jan Kratochvíyl, editor, Graph Drawing, pages 98-106, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. Google Scholar
  29. Michael Fellows, Michael Langston, Frances Rosamond, and Peter Shaw. Efficient Parameterized Preprocessing for Cluster Editing. In Erzsébet Csuhaj-Varjú and Zoltán Ésik, editors, Fundamentals of Computation Theory, 2007. Google Scholar
  30. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  31. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Spanning Circuits in Regular Matroids. CoRR, abs/1607.05516, 2016. URL: http://arxiv.org/abs/1607.05516.
  32. Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. J. Comput. Syst. Sci., 80(7):1430-1447, 2014. Google Scholar
  33. Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1419-1432, 2017. Google Scholar
  34. Fedor V. Fomin and Yngve Villanger. Treewidth computation and extremal combinatorics. Combinatorica, 32(3):289-308, 2012. URL: https://doi.org/10.1007/s00493-012-2536-z.
  35. Ioannis Giotis and Venkatesan Guruswami. Correlation Clustering with a Fixed Number of Clusters. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 1167-1176, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1109557.1109686.
  36. Olivier Goldschmidt and Dorit S. Hochbaum. A Polynomial Algorithm for the k-cut Problem for Fixed k. Math. Oper. Res., 19(1):24-37, 1994. URL: https://doi.org/10.1287/moor.19.1.24.
  37. Petr A. Golovach, Pinar Heggernes, Paloma T. Lima, and Pedro Montealegre. Finding Connected Secluded Subgraphs. CoRR, abs/1710.10979, 2017. To appear in IPEC 2017. URL: http://arxiv.org/abs/1710.10979.
  38. Petr A. Golovach and Dimitrios M. Thilikos. Clustering to Given Connectivities. CoRR, abs/1803.09483, 2018. Google Scholar
  39. Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Graph-Modeled Data Clustering: Exact Algorithms for Clique Generation. Theory of Computing Systems, 38(4):373-392, July 2005. Google Scholar
  40. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Proceedings of the 43rd ACM Symposium on Theory of Computing, (STOC 2011), pages 479-488, 2011. URL: https://doi.org/10.1145/1993636.1993700.
  41. Jiong Guo. A more effective linear kernelization for cluster editing. Theoretical Computer Science, 410(8):718-726, 2009. URL: https://doi.org/10.1016/j.tcs.2008.10.021.
  42. Jiong Guo, Iyad A. Kanj, Christian Komusiewicz, and Johannes Uhlmann. Editing Graphs into Disjoint Unions of Dense Clusters. Algorithmica, 61(4):949-970, 2011. Google Scholar
  43. Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann. A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing. SIAM J. Discrete Math., 24(4):1662-1683, 2010. URL: https://doi.org/10.1137/090767285.
  44. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth. J. Comput. Syst. Sci., 57(3):366-375, 1998. URL: https://doi.org/10.1006/jcss.1998.1592.
  45. Erez Hartuv and Ron Shamir. A clustering algorithm based on graph connectivity. Inf. Process. Lett., 76(4-6):175-181, 2000. Google Scholar
  46. Pinar Heggernes, Daniel Lokshtanov, Jesper Nederlof, Christophe Paul, and Jan Arne Telle. Generalized Graph Clustering: Recognizing (p, q)-Cluster Graphs. In Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers, pages 171-183, 2010. Google Scholar
  47. Falk Hüffner, Christian Komusiewicz, Adrian Liebtrau, and Rolf Niedermeier. Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage. IEEE/ACM Trans. Comput. Biology Bioinform., 11(3):455-467, 2014. Google Scholar
  48. Falk Hüffner, Christian Komusiewicz, and Manuel Sorge. Finding Highly Connected Subgraphs. In SOFSEM 2015: Theory and Practice of Computer Science - 41st International Conference on Current Trends in Theory and Practice of Computer Science, Pec pod Sněžkou, Czech Republic, January 24-29, 2015. Proceedings, pages 254-265, 2015. Google Scholar
  49. Ken-ichi Kawarabayashi and Mikkel Thorup. The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. In FOCS 2011, pages 160-169. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.53.
  50. Arindam Khan and Prasad Raghavendra. On mimicking networks representing minimum terminal cuts. Inf. Process. Lett., 114(7):365-371, 2014. URL: https://doi.org/10.1016/j.ipl.2014.02.011.
  51. Arindam Khan and Prasad Raghavendra. On mimicking networks representing minimum terminal cuts. Information Processing Letters, 114(7):365-371, 2014. Google Scholar
  52. Eun Jung Kim, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. Parameterized algorithms for min-max multiway cut and list digraph homomorphism. J. Comput. Syst. Sci., 86:191-206, 2017. Google Scholar
  53. Christian Komusiewicz and Johannes Uhlmann. Alternative Parameterizations for Cluster Editing. In SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings, pages 344-355, 2011. Google Scholar
  54. H. W. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Quart., 2:83-97, 1955. URL: https://doi.org/10.1002/nav.3800020109.
  55. H. W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Res. Logist. Quart., 3:253-258 (1957), 1956. URL: https://doi.org/10.1002/nav.3800030404.
  56. Daniel Lokshtanov and Dániel Marx. Clustering with Local Restrictions. Inf. Comput., 222:278-292, January 2013. Google Scholar
  57. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Reducing CMSO Model Checking to Highly Connected Graphs. In ICALP 2018, volume 107 of LIPIcs, pages 135:1-135:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  58. Hannes Moser, Rolf Niedermeier, and Manuel Sorge. Exact combinatorial algorithms and experiments for finding maximum k-plexes. J. Comb. Optim., 24(3):347-373, 2012. URL: https://doi.org/10.1007/s10878-011-9391-5.
  59. Rolf Niedermeier. Invitation to fixed-parameter algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  60. Jeffrey Pattillo, Alexander Veremyev, Sergiy Butenko, and Vladimir Boginski. On the maximum quasi-clique problem. Discrete Applied Mathematics, 161(1):244-257, 2013. URL: https://doi.org/10.1016/j.dam.2012.07.019.
  61. Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. On clique relaxation models in network analysis. European Journal of Operational Research, 226(1):9-18, 2013. URL: https://doi.org/10.1016/j.ejor.2012.10.021.
  62. Fábio Protti, Maise Dantas da Silva, and Jayme Luiz Szwarcfiter. Applying Modular Decomposition to Parameterized Cluster Editing Problems. Theory of Computing Systems, 44(1):91-104, January 2009. Google Scholar
  63. Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007. URL: https://doi.org/10.1016/j.cosrev.2007.05.001.
  64. Shahram Shahinpour and Sergiy Butenko. Distance-Based Clique Relaxations in Networks: s-Clique and s-Club. In Boris I. Goldengorin, Valery A. Kalyagin, and Panos M. Pardalos, editors, Models, Algorithms, and Technologies for Network Analysis, pages 149-174, New York, NY, 2013. Springer New York. Google Scholar
  65. Ron Shamir, Roded Sharan, and Dekel Tsur. Cluster graph modification problems. Discrete Appl. Math., 144(1-2):173-182, 2004. URL: https://doi.org/10.1016/j.dam.2004.01.007.
  66. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. J. ACM, 44(4):585-591, 1997. URL: https://doi.org/10.1145/263867.263872.
  67. René van Bevern, Hannes Moser, and Rolf Niedermeier. Approximation and Tidying - A Problem Kernel for s-Plex Cluster Vertex Deletion. Algorithmica, 62(3-4):930-950, 2012. Google Scholar
  68. Ka-Chun Wong. A Short Survey on Data Clustering Algorithms. CoRR, abs/1511.09123, 2015. URL: http://arxiv.org/abs/1511.09123.
  69. Bang Ye Wu and Jia-Fen Chen. Balancing a Complete Signed Graph by Editing Edges and Deleting Nodes. In Ruay-Shiung Chang, Lakhmi C. Jain, and Sheng-Lung Peng, editors, Advances in Intelligent Systems and Applications - Volume 1, pages 79-88, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  70. Dongkuan Xu and Yingjie Tian. A Comprehensive Survey of Clustering Algorithms. Annals of Data Science, 2(2):165-193, June 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact