Document Open Access Logo

A Branch-And-Bound Algorithm for Cluster Editing

Authors Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren , Michael Hamann , Tobias Heuer, Jonas Spinner, Christopher Weyand , Marcus Wilhelm

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.13.pdf
  • Filesize: 0.87 MB
  • 19 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Karlsruhe Institute of Technology, Germany
Philipp Fischbeck
  • Hasso Plattner Institute, Potsdam, Germany
Lars Gottesbüren
  • Karlsruhe Institute of Technology, Germany
Michael Hamann
  • Karlsruhe Institute of Technology, Germany
Tobias Heuer
  • Karlsruhe Institute of Technology, Germany
Jonas Spinner
  • Karlsruhe Institute of Technology, Germany
Christopher Weyand
  • Karlsruhe Institute of Technology, Germany
Marcus Wilhelm
  • Karlsruhe Institute of Technology, Germany

Funding

  • Hamann, Michael: This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under grant WA 654/22-2.

Acknowledgements

We thank Darren Strash for helpful discussions and literature research.

Cite AsGet BibTex

Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren, Michael Hamann, Tobias Heuer, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. A Branch-And-Bound Algorithm for Cluster Editing. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.13

Abstract

The cluster editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • cluster editing

Metrics

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

Supplementary Materials

References

  1. Diogo V. Andrade, Mauricio G. C. Resende, and Renato F. Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525-547, 2012. URL: https://doi.org/10.1007/s10732-012-9196-4.
  2. Lucas 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.
  3. Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren, Michael Hamann, Tobias Heuer, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. PACE solver description: KaPoCE: A heuristic cluster editing algorithm. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), pages 31:1-31:4, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.31.
  4. Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren, Michael Hamann, Tobias Heuer, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. PACE solver description: The KaPoCE exact cluster editing algorithm. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:3, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.27.
  5. Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. In 27th Annual European Symposium on Algorithms (ESA 2019), pages 21:1-21:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.21.
  6. Thomas Bläsius, Tobias Friedrich, David Stangl, and Christopher Weyand. An efficient branch-and-bound solver for hitting set. In 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 209-220, 2022. URL: https://doi.org/10.1137/1.9781611977042.17.
  7. 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.
  8. 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.
  9. 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.
  10. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theoretical Computer Science, 760:35-54, 2019. URL: https://doi.org/10.1016/j.tcs.2018.08.014.
  11. Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica, 64(1):152-169, 2012. URL: https://doi.org/10.1007/s00453-011-9595-1.
  12. Jianer Chen and Jie Meng. A 2k kernel for the cluster editing problem. Journal of Computer and System Sciences, 78(1):211-220, 2012. URL: https://doi.org/10.1016/j.jcss.2011.04.001.
  13. Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf. Engineering Exact Quasi-Threshold Editing. In 18th International Symposium on Experimental Algorithms (SEA 2020), volume 160, pages 10:1-10:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.10.
  14. 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.
  15. Sepp Hartung and Holger H. Hoos. Programming by optimisation meets parameterised algorithmics: A case study for cluster editing. In Learning and Intelligent Optimization, pages 43-58. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19084-6_5.
  16. 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), pages 26:1-26:18, 2021. URL: https://doi.org/10.4230/LIPIcs.IPEC.2021.26.
  17. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Physical Review E, 82(3), 2010. URL: https://doi.org/10.1103/physreve.82.036106.
  18. Mirko Křivánek and Jaroslav Morávek. NP-hard problems in hierarchical-tree clustering. Acta informatica, 23(3):311-323, 1986. URL: https://doi.org/10.1007/BF00289116.
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