Document Open Access Logo

The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing

Authors Leon Kellerhals , Tomohiro Koana , André Nichterlein , Philipp Zschoche

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.26.pdf
  • Filesize: 1.28 MB
  • 18 pages

Document Identifiers

Author Details

Leon Kellerhals
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany
Tomohiro Koana
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany
André Nichterlein
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany
Philipp Zschoche
  • Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, Germany

Funding

This work has been partially supported by the DFG project FPTinP (NI 369/18). The publication of the proceedings of PACE 2021 has been supported by the Algorithmics and Computational Complexity group at Technische Universität Berlin.
  • Koana, Tomohiro: Supported by the DFG project DiPa (NI 369/21)

Acknowledgements

The PACE challenge was supported by Networks and Technische Universität Berlin. The prize money (€4000) was generously provided by the Networks, an NWO Gravitation project of the University of Amsterdam, Eindhoven University of Technology, Leiden University and the Center for Mathematics and Computer Science (CWI). We are grateful to the whole optil.io team, led by Szymon Wasik, and especially to Jan Badura and Artur Laskowski for the fruitful collaboration and for hosting the competition at the optil.io online judge system. We thank Aleksander Figiel (Technische Universität Berlin) for supporting us with scripts in the data collection process.

Cite As Get BibTex

Leon Kellerhals, Tomohiro Koana, André Nichterlein, and Philipp Zschoche. The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.26

Abstract

The Parameterized Algorithms and Computational Experiments challenge (PACE) 2021 was devoted to engineer algorithms solving the NP-hard Cluster Editing problem, also known as Correlation Clustering: Given an undirected graph the task is to compute a minimum number of edges to insert or remove in a way that the resulting graph is a cluster graph, that is, a graph in which each connected component is a clique.
Altogether 67 participants from 21 teams, 11 countries, and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances, and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Correlation Clustering
  • Cluster Editing
  • Algorithm Engineering
  • FPT
  • Kernelization
  • Heuristics

Metrics

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

Supplementary Materials

References

  1. Networks project, 2017. URL: http://www.thenetworkcenter.nl.
  2. Sachin Agarwal, Sahil Bajaj, Ojasv Singh, and Srinibas Swain. Cluster editing using ILP (CLIP): An exact solver for cluster editing, 2021. URL: https://github.com/sachin-4099/PACE_2021_Cluster_Editing.
  3. Sachin Agarwal, Sahil Bajaj, Ojasv Singh, and Srinibas Swain. Conflict reduced best-fit cluster (CoRBeC): A heuristic solver for cluster editing, 2021. URL: https://github.com/sahilbajaj82/PACE-2021-Cluster-Editing.
  4. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56:89-113, 2004. URL: https://doi.org/10.1023/B:MACH.0000033116.57574.95.
  5. Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE 2021 kernelization track, 2021. URL: https://doi.org/10.5281/zenodo.4947841.
  6. Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. Pace 2021 muSolver, 2021. URL: https://doi.org/10.5281/zenodo.4947325.
  7. Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. valbart/pace-2021: PACE 2021 exact track, 2021. URL: https://doi.org/10.5281/zenodo.4935569.
  8. Moritz Beck, Timon Behr, Johannes Blum, Sabine Cornelsen, and Sabine Storandt. Super Cereal, 2021. URL: https://doi.org/10.5281/zenodo.4892806.
  9. Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering gene expression patterns. Journal of Computational Biology, 6(3-4):281-297, 1999. URL: https://doi.org/10.1089/106652799318274.
  10. Matthias Bentert, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Parameterized aspects of triangle enumeration. Journal of Computer and System Sciences, 103:61-77, 2019. URL: https://doi.org/10.1016/j.jcss.2019.02.004.
  11. René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modification problems above lower bounds. Theory of Computing Systems, 62(3):739-770, 2018. URL: https://doi.org/10.1007/s00224-016-9746-5.
  12. Alexander Bille, Dominik Brandenstein, and Emanuel Herrendorf. PACE 2021 exact track submission, 2021. URL: https://doi.org/10.5281/zenodo.4889012.
  13. Václav Blažej, Radovan Červený, Dušan Knop, Jan Pokorný, Šimon Schierreich, and Ondřej Suchý. GOAT, 2021. URL: https://gitlab.fit.cvut.cz/pace-challenge/2021/goat/exact.
  14. Václav Blažej, Radovan Červený, Dušan Knop, Jan Pokorný, Šimon Schierreich, and Ondřej Suchý. GOAT, 2021. URL: https://gitlab.fit.cvut.cz/pace-challenge/2021/goat/heuristic.
  15. Václav Blažej, Radovan Červený, Dušan Knop, Jan Pokorný, Šimon Schierreich, and Ondřej Suchý. GOAT, 2021. URL: https://gitlab.fit.cvut.cz/pace-challenge/2021/goat/kernelization.
  16. Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: Theory and Experiment, 10, 2008. URL: https://doi.org/10.1088/1742-5468/2008/10/P10008.
  17. Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing. Journal of Discrete Algorithms, 16:79-89, 2012. URL: https://doi.org/10.1016/j.jda.2012.04.005.
  18. Sebastian Böcker and Jan Baumbach. Cluster editing. In Proceedings of the 9th Conference on Computability in Europe (CiE 2013), volume 7921 of LNCS, pages 33-44. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39053-1_5.
  19. Sebastian Böcker, Sebastian Briesemeister, Quang Bao Anh Bui, and Anke Truß. Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science, 410(52):5467-5480, 2009. URL: https://doi.org/10.1016/j.tcs.2009.05.006.
  20. Sebastian Böcker, Sebastian Briesemeister, and Gunnar W. Klau. Exact algorithms for cluster editing: Evaluation and experiments. Algorithmica, 60(2):316-334, 2011. URL: https://doi.org/10.1007/s00453-009-9339-7.
  21. Édouard Bonnet and Florian Sikora. The PACE 2018 parameterized algorithms and computational experiments challenge: The third iteration. In Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC '18), volume 115 of LIPIcs, pages 26:1-26:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.26.
  22. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
  23. Yixin Cao and Jianer Chen. Cluster Editing: Kernelization based on edge cuts. Algorithmica, 64(1):152-169, 2012. Google Scholar
  24. Jianer Chen and Jie Meng. A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences, 78(1):211-220, 2012. Google Scholar
  25. Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer. Paradigms for parameterized enumeration. Theory of Computing Systems, 60(4):737-758, 2017. URL: https://doi.org/10.1007/s00224-016-9702-4.
  26. Lucas de O. Bastos, Luiz Satoru Ochi, Fábio Protti, Anand Subramanian, Ivan César Martins, and Rian Gabriel S. Pinheiro. Efficient algorithms for cluster editing. Journal of Combinatorial Optimization, 31(1):347-371, 2016. URL: https://doi.org/10.1007/s10878-014-9756-7.
  27. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The first parameterized algorithms and computational experiments challenge. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC '16), volume 63 of LIPIcs, pages 30:1-30:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.IPEC.2016.30.
  28. Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC '17), volume 89 of LIPIcs, pages 30:1-30:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.30.
  29. Emir Demirović. Kanpai: A bottom-up approach for cluster editing (PACE 2021), 2021. URL: https://bitbucket.org/EmirD/pace-2021/.
  30. Kenneth Dietrich, Mario Grobler, Ozan Heydt, Roman Rabinovich, Sebastian Siebertz, Nick Siering, Leon Stichternath, and Julian Tat. PACA-RUST, 2021. URL: https://doi.org/10.5281/zenodo.4884693.
  31. Jona Dirks, Mario Grobler, Tobias Meis, Roman Rabinovich, Yannik Schnaubelt, Sebastian Siebertz, and Maximilian Sonneborn. PACA-JAVA, 2021. URL: https://doi.org/10.5281/zenodo.4884681.
  32. M. Ayaz Dzulfikar, Johannes Klaus Fichte, and Markus Hecher. The PACE 2019 parameterized algorithms and computational experiments challenge: The fourth iteration (invited paper). In Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC '19), volume 148 of LIPIcs, pages 25:1-25:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.25.
  33. Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Peter Shaw. Efficient parameterized preprocessing for Cluster Editing. In Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT '07), volume 4639 of LNCS, pages 312-321. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74240-1_27.
  34. Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Yngve Villanger. Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters. Journal of Computer and System Sciences, 80(7):1430-1447, 2014. Google Scholar
  35. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  36. Thorben Freese, Jakob Gahde, Mario Grobler, Roman Rabinovich, Fynn Sczuka, and Sebastian Siebertz. PACA-PYTHON, 2021. URL: https://doi.org/10.5281/zenodo.4884234.
  37. Martin Josef Geiger. Source code for PACE 2021, 2021. URL: https://doi.org/10.5281/zenodo.4891323.
  38. Lars Gottesbüren, Tobias Heuer, Thomas Bläsius, Philipp Fischbeck, Michael Hamann, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. KaPoCE - an exact and heuristic solver for the cluster editing problem, 2021. URL: https://doi.org/10.5281/zenodo.4892524.
  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, 2005. Google Scholar
  40. Mario Grobler, Roman Rabinovich, and Sebastian Siebertz. PACE 2021 - cluster editing, c++, 2021. URL: https://doi.org/10.5281/zenodo.4889505.
  41. Martin Grötschel and Yoshiko Wakabayashi. A cutting plane algorithm for a clustering problem. Mathematical Programming, 45(1-3):59-96, 1989. URL: https://doi.org/10.1007/BF01589097.
  42. Jiong Guo. A more effective linear kernelization for cluster editing. Theoretical Computer Science, 410(8-10):718-726, 2009. URL: https://doi.org/10.1016/j.tcs.2008.10.021.
  43. Joshua Harmsen and A.J. Zuckerman. Cluster editing with existing cliques, 2021. URL: https://github.com/joshuaharmsen845/PACE-Challenge/tree/sol1.
  44. Sepp Hartung and Holger H. Hoos. Programming by optimisation meets parameterised algorithmics: a case study for cluster editing. In Proceedings of the 9th International Conference on Learning and Intelligent Optimization, LION 2015, volume 8994 of LNCS, pages 43-58. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19084-6_5.
  45. Christian Komusiewicz and Johannes Uhlmann. Cluster editing with locally bounded modifications. Discrete Applied Mathematics, 160(15):2259-2270, 2012. Google Scholar
  46. Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki. The PACE 2020 parameterized algorithms and computational experiments challenge: Treedepth. In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC '20), volume 180 of LIPIcs, pages 37:1-37:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.37.
  47. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection, June 2014. URL: http://snap.stanford.edu/data/index.html.
  48. Shaohua Li, Marcin Pilipczuk, and Manuel Sorge. Cluster editing parameterized above modification-disjoint P₃-packings. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS '21), volume 187 of LIPIcs, pages 49:1-49:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.49.
  49. Moritz Lichter, Oliver Bachtler, Tim Bergner, Irene Heinrich, and Alexander Schiewe. PACE solver description - Alphabetic, 2021. URL: https://gitlab.rlp.net/aschiewe/alphabetic.
  50. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC '17), pages 224-237. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  51. Yosuke Mizutani. PACE 2021 - exact, 2021. URL: https://doi.org/10.5281/zenodo.4877899.
  52. OECD. Technical report of the survey of adult skills (PIAAC). Technical report, Paris, France, 2013. URL: https://www.oecd.org/skills/piaac/_Technical%20Report_17OCT13.pdf.
  53. Sebastian Paarmann. Pandora cluster editing solver, 2021. URL: https://doi.org/10.5281/zenodo.4964394.
  54. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011. Google Scholar
  55. Sven Rahmann, Tobias Wittkop, Jan Baumbach, Marcel Martin, Anke Truss, and Sebastian Böcker. Exact and heuristic algorithms for weighted cluster editing. In Proceedings of the 6th Computational Systems Bioinformatics Conference (CSB '07), pages 391-401. World Scientific, 2007. URL: https://doi.org/10.1142/9781860948732_0040.
  56. Terry Regier, Paul Kay, and Naveen Khetarpal. Color naming reflects optimal partitions of color space. Proceedings of the National Academy of Sciences, 104(4):1436-1441, 2007. URL: https://doi.org/10.1073/pnas.0610341104.
  57. Angus Ritossa, Paula Tennent, Tiana Tsang Ung, and Akshay Valluru. PACE challenge 2021 solver description, from the random sampling group of the UNSW GraphAbility VIP project, 2021. URL: https://doi.org/10.5281/zenodo.4946084.
  58. Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007. URL: https://doi.org/10.1016/j.cosrev.2007.05.001.
  59. Ron Shamir, Roded Sharan, and Dekel Tsur. Cluster graph modification problems. Discrete Applied Mathematics, 144(1-2):173-182, 2004. URL: https://doi.org/10.1007/3-540-36379-3_33.
  60. Ben Strasser. CELMEC: Cluster editing pace 2021, 2021. URL: https://github.com/ben-strasser/cluster-editing-pace2021.
  61. Sylwester Swat. CluES - a heuristic solver for the cluster editing problem, 2021. URL: https://github.com/swacisko/pace-2021.
  62. Tomoki Takayama. SatoxaSolver: A submission for PACE 2021, 2021. URL: https://doi.org/10.5281/zenodo.4941172.
  63. Erik Thiel, Morteza Haghir Chehreghani, and Devdatt P. Dubhashi. A non-convex optimization approach to correlation clustering. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI '19), the 31st Innovative Applications of Artificial Intelligence Conference (IAAI '19), and the 9th AAAI Symposium on EducationalAdvances in Artificial Intelligence (EAAI '19), pages 5159-5166. AAAI Press, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33015159.
  64. Esther Ulitzsch, Qiwei He, Vincent Ulitzsch, Hendrik Molter, André Nichterlein, Rolf Niedermeier, and Steffi Pohl. Combining clickstream analyses and graph-modeled data clustering for identifying common response processes. Psychometrika, 86(1):190-214, 2021. URL: https://doi.org/10.1007/s11336-020-09743-0.
  65. Szymon Wasik, Maciej Antczak, Jan Badura, Artur Laskowski, and Tomasz Sternal. Optil.io: Cloud based platform for solving optimization problems using crowdsourcing approach. In Proceedings of the 19th ACM Conference on Computer Supported Cooperative Work and Social Computing Companion, CSCW '16 Companion, pages 433-436. ACM, 2016. URL: https://doi.org/10.1145/2818052.2869098.
  66. Tobias Wittkop, Jan Baumbach, Francisco P. Lobo, and Sven Rahmann. Large scale clustering of protein sequences with force - a layout based heuristic for weighted cluster editing. BMC Bioinformatics, 8(396), 2007. URL: https://doi.org/10.1186/1471-2105-8-396.
  67. Tobias Wittkop, Dorothea Emig, Sita Lange, Sven Rahmann, Mario Albrecht, John H Morris, Sebastian Böcker, Jens Stoye, and Jan Baumbach. Partitioning biological data with transitivity clustering. Nature Methods, 7(6):419-420, 2010. URL: https://doi.org/10.1038/nmeth0610-419.
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 About DROPS Imprint Privacy Contact