Document Open Access Logo

Engineering Exact Quasi-Threshold Editing

Authors Lars Gottesbüren , Michael Hamann , Philipp Schoch, Ben Strasser , Dorothea Wagner , Sven Zühlsdorf

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.10.pdf
  • Filesize: 1.05 MB
  • 14 pages

Document Identifiers

Author Details

Lars Gottesbüren
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Michael Hamann
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Philipp Schoch
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Ben Strasser
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Dorothea Wagner
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Sven Zühlsdorf
  • Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany

Funding

This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under grants WA654/19-2 and WA654/22-2. The authors acknowledge support by the state of Baden-Württemberg through bwHPC.

Acknowledgements

We thank James Nastos and Mark Ortmann for helpful discussions.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SEA.2020.10

Abstract

Quasi-threshold graphs are {C₄, P₄}-free graphs, i.e., they do not contain any cycle or path of four nodes as an induced subgraph. We study the {C₄, P₄}-free editing problem, which is the problem of finding a minimum number of edge insertions or deletions to transform an input graph into a quasi-threshold graph. This problem is NP-hard but fixed-parameter tractable (FPT) in the number of edits by using a branch-and-bound algorithm and admits a simple integer linear programming formulation (ILP). Both methods are also applicable to the general ℱ-free editing problem for any finite set of graphs ℱ. For the FPT algorithm, we introduce a fast heuristic for computing high-quality lower bounds and an improved branching strategy. For the ILP, we engineer several variants of row generation. We evaluate both methods for quasi-threshold editing on a large set of protein similarity graphs. For most instances, our optimizations speed up the FPT algorithm by one to three orders of magnitude. The running time of the ILP, that we solve using Gurobi, becomes only slightly faster. With all optimizations, the FPT algorithm is slightly faster than the ILP, even when listing all solutions. Additionally, we show that for almost all graphs, solutions of the previously proposed quasi-threshold editing heuristic QTM are close to optimal.

Subject Classification

ACM Subject Classification
  • Information systems → Clustering
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Branch-and-bound
Keywords
  • Edge Editing
  • Integer Linear Programming
  • FPT algorithm
  • Quasi-Threshold Editing

Metrics

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

Related Versions

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. Sebastian Böcker and Jan Baumbach. Cluster Editing. In Proceedings of the 9th Conference on Computability in Europe (CiE'13), volume 7921 of Lecture Notes in Computer Science, pages 33-44. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39053-1_5.
  3. 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), volume 6, pages 211-220, 2008. URL: https://doi.org/10.1142/9781848161092_0023.
  4. 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.
  5. Felix Bohlmann. Graphclustern durch Zerstören langer induzierter Pfade. Bachelor thesis, TU Berlin, 2015. URL: http://fpt.akt.tu-berlin.de/publications/theses/BA-felix-bohlmann.pdf.
  6. Ulrik Brandes, Michael Hamann, Ben Strasser, and Dorothea Wagner. Fast Quasi-Threshold Editing. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), volume 9294 of Lecture Notes in Computer Science, pages 251-262. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_22.
  7. Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters, 58(4):171-176, May 1996. URL: https://doi.org/10.1016/0020-0190(96)00050-6.
  8. Frank Pok Man Chu. A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements. Information Processing Letters, 107(1):7-12, June 2008. URL: https://doi.org/10.1016/j.ipl.2007.12.009.
  9. Peter Damaschke. Fixed-Parameter Enumerability of Cluster Editing and Related Problems. Theory of Computing Systems, 46(2):261-283, 2008. URL: https://doi.org/10.1007/s00224-008-9130-1.
  10. Hassan Ali Dawah, Bradford A. Hawkins, and Michael F. Claridge. Structure of the Parasitoid Communities of Grass-Feeding Chalcid Wasps. Journal of Animal Ecology, 64(6):708-720, 1995. URL: https://doi.org/10.2307/5850.
  11. Pål Grønås Drange and Michał Pilipczuk. A Polynomial Kernel for Trivially Perfect Editing. Algorithmica, 80(12):3481-3524, December 2017. URL: https://doi.org/10.1007/s00453-017-0401-6.
  12. Michelle Girvan and Mark E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Science of the United States of America, 99(12):7821-7826, 2002. URL: https://doi.org/10.1073/pnas.122653799.
  13. Lars Gottesbüren, Michael Hamann, Philipp Schoch, Ben Strasser, Dorothea Wagner, and Sven Zühlsdorf. Engineering exact quasi-threshold editing. arXiv e-prints, 2020. URL: http://arxiv.org/abs/2003.14317.
  14. 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.
  15. Gurobi Optimization, LLC. Gurobi optimizer reference manual, 2020. URL: http://www.gurobi.com.
  16. 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, Lecture Notes in Computer Science, pages 43-58. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19084-6_5.
  17. Marc Hellmuth, Nicolas Wieseke, Marcus Lechner, Hans-Peter Lenhof, Martin Middendorf, and Peter F. Stadler. Phylogenomics with paralogs. Proceedings of the National Academy of Science of the United States of America, 112(7):2058-2063, 2015. URL: https://doi.org/10.1073/pnas.1412770112.
  18. Donald E. Knuth. The Stanford GraphBase : a platform for combinatorial computing. Addison-Wesley, 1993. Google Scholar
  19. Yunlong Liu, Jianxin Wang, Jie You, Jianer Chen, and Yixin Cao. Edge deletion problems: Branching facilitated by modular decomposition. Theoretical Computer Science, 573:63-70, 2015. URL: https://doi.org/10.1016/j.tcs.2015.01.049.
  20. David Lusseau, Karsten Schneider, Oliver Boisseau, Patti Haase, Elisabeth Slooten, and Steve Dawson. The Bottlenose Dolphin Community of Doubtful Sound Features a Large Proportion of Long-Lasting Associations. Behavioral Ecology and Sociobiology, 54(4):396-405, September 2004. URL: https://doi.org/10.1007/s00265-003-0651-y.
  21. James Nastos. Utilizing graph classes for community detection in social and complex networks. PhD thesis, University of British Columbia, 2015. URL: https://doi.org/10.14288/1.0074429.
  22. James Nastos and Yong Gao. A Novel Branching Strategy for Parameterized Graph Modification Problems. In Proceedings of the 4th International Conference on Combinatorial Optimization and Applications, volume 2 of Lecture Notes in Computer Science, pages 332-346. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17461-2_27.
  23. James Nastos and Yong Gao. Familial groups in social networks. Social Networks, 35(3):439-450, July 2013. URL: https://doi.org/10.1016/j.socnet.2013.05.001.
  24. Sven Rahmann, Tobias Wittkop, Jan Baumbach, Marcel Martin, Anke Truß, and Sebastian Böcker. Exact and Heuristic Algorithms for Weighted Cluster Editing. In Proceedings of the 6th Annual International Conference on Computational Systems Bioinformatics (CSB 2007), volume 6, pages 391-401, 2007. URL: https://doi.org/10.1142/9781860948732_0040.
  25. Wayne W. Zachary. An Information Flow Model for Conflict and Fission in Small Groups. Journal of Anthropological Research, 33:452-473, 1977. URL: https://doi.org/10.1086/jar.33.4.3629752.
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