Document Open Access Logo

Finding Optimal Triangulations Parameterized by Edge Clique Cover

Author Tuukka Korhonen

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.22.pdf
  • Filesize: 0.56 MB
  • 18 pages

Document Identifiers

Author Details

Tuukka Korhonen
  • Department of Computer Science, University of Helsinki, Finland

Funding

This work has been financially supported by Academy of Finland (grant 322869).

Acknowledgements

I wish to thank Matti Järvisalo, Mikko Koivisto, Andreas Niskanen, and Juha Harviainen for helpful comments.

Cite As Get BibTex

Tuukka Korhonen. Finding Optimal Triangulations Parameterized by Edge Clique Cover. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.IPEC.2020.22

Abstract

Many graph problems can be formulated as a task of finding an optimal triangulation of a given graph with respect to some notion of optimality. In this paper we give algorithms to such problems parameterized by the size of a minimum edge clique cover (cc) of the graph. The parameter cc is both natural and well-motivated in many problems on this setting. For example, in the perfect phylogeny problem cc is at most the number of taxa, in fractional hypertreewidth cc is at most the number of hyperedges, and in treewidth of Bayesian networks cc is at most the number of non-root nodes of the Bayesian network.
Our results are based on the framework of potential maximal cliques. We show that the number of minimal separators of graphs is at most 2^cc and the number of potential maximal cliques is at most 3^cc. Furthermore, these objects can be listed in times O^*(2^cc) and O^*(3^cc), respectively, even when no edge clique cover is given as input; the O^*(⋅) notation omits factors polynomial in the input size. Using these enumeration algorithms we obtain O^*(3^cc) time algorithms for problems in the potential maximal clique framework, including for example treewidth, minimum fill-in, and feedback vertex set. We also obtain an O^*(3^m) time algorithm for fractional hypertreewidth, where m is the number of hyperedges. In the case when an edge clique cover of size cc' is given as an input we further improve the time complexity to O^*(2^cc') for treewidth, minimum fill-in, and chordal sandwich. This implies an O^*(2^n) time algorithm for perfect phylogeny, where n is the number of taxa. We also give polynomial space algorithms with time complexities O^*(9^cc') and O^*(9^(cc + O(log^2 cc))) for problems in this framework.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Treewidth
  • Minimum fill-in
  • Perfect phylogeny
  • Fractional hypertreewidth
  • Potential maximal cliques
  • Edge clique cover

Metrics

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

Related Versions

References

  1. Anne Berry, Jean Paul Bordat, and Olivier Cogis. Generating all the minimal separators of a graph. International Journal of Foundations of Computer Science, 11(3):397-403, 2000. URL: https://doi.org/10.1142/S0129054100000211.
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 67-74. ACM, 2007. URL: https://doi.org/10.1145/1250790.1250801.
  3. Hans L Bodlaender, Leizhen Cai, Jianer Chen, Michael R. Fellows, Jan Arne Telle, and Dániel Marx. Open problems in parameterized and exact computation - IWPEC 2006. Technical Report UU-CS-2006-052, Department of Information and Computing Sciences, Utrecht University, 2006. URL: https://dspace.library.uu.nl/handle/1874/22186.
  4. Magnus Bordewich, Katharina T. Huber, and Charles Semple. Identifying phylogenetic trees. Discrete Mathematics, 300(1-3):30-43, 2005. URL: https://doi.org/10.1016/j.disc.2005.06.015.
  5. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212-232, 2001. URL: https://doi.org/10.1137/S0097539799359683.
  6. Vincent Bouchitté and Ioan Todinca. Listing all potential maximal cliques of a graph. Theoretical Computer Science, 276(1-2):17-32, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00007-X.
  7. Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca, and Yngve Villanger. Treewidth and pathwidth parameterized by the vertex cover number. Discrete Applied Mathematics, 216:114-129, 2017. URL: https://doi.org/10.1016/j.dam.2014.12.012.
  8. Cristina Conati, Abigail S. Gertner, Kurt VanLehn, and Marek J. Druzdzel. On-line student modeling for coached problem solving using Bayesian networks. In User Modeling, volume 383 of CISM, pages 231-242. Springer, 1997. URL: https://doi.org/10.1007/978-3-7091-2670-7_24.
  9. Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing, 45(1):67-83, 2016. URL: https://doi.org/10.1137/130947076.
  10. Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In 12th International Symposium on Parameterized and Exact Computation, 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.
  11. Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, and Reinhard Pichler. HyperBench: A benchmark and tool for hypergraphs and empirical findings. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 464-480, 2019. URL: https://doi.org/10.1145/3294052.3319683.
  12. Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler. General and fractional hypertree decompositions: Hard and easy cases. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 17-32, 2018. URL: https://doi.org/10.1145/3196959.3196962.
  13. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. Algorithmica, 2020. URL: https://doi.org/10.1007/s00453-020-00692-9.
  14. Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger. Exact algorithms for treewidth and minimum fill-in. SIAM Journal on Computing, 38(3):1058-1079, 2008. URL: https://doi.org/10.1137/050643350.
  15. Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, and Ioan Todinca. Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica, 80(4):1146-1169, 2018. URL: https://doi.org/10.1007/s00453-017-0297-1.
  16. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54-87, 2015. URL: https://doi.org/10.1137/140964801.
  17. Masanobu Furuse and Koichi Yamazaki. A revisit of the scheme for computing treewidth and minimum fill-in. Theoretical Computer Science, 531:66-76, 2014. URL: https://doi.org/10.1016/j.tcs.2014.03.013.
  18. Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers. ACM Transactions on Algorithms, 11(1):4:1-4:20, 2014. URL: https://doi.org/10.1145/2636918.
  19. Rob Gysel. Minimal triangulation algorithms for perfect phylogeny problems. In Language and Automata Theory and Applications - 8th International Conference, volume 8370 of LNCS, pages 421-432. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-04921-2_34.
  20. Masami Hasegawa, Hirohisa Kishino, and Taka-aki Yano. Dating of the human-ape splitting by a molecular clock of mitochondrial dna. Journal of Molecular Evolution, 22(2):160-174, 1985. Google Scholar
  21. Pinar Heggernes, Federico Mancini, Jesper Nederlof, and Yngve Villanger. A parameterized algorithm for chordal sandwich. In Proceedings of 7th International Conference on Algorithms and Complexity, volume 6078 of LNCS, pages 120-130. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13073-1_12.
  22. Finn V. Jensen and Frank Jensen. Optimal junction trees. In Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence, pages 360-366. Morgan Kaufmann, 1994. URL: https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=524&proceeding_id=10.
  23. Finn V. Jensen and Thomas D. Nielsen. Bayesian networks and decision graphs. Springer, 2007. URL: https://doi.org/10.1007/978-0-387-68282-2.
  24. Sampath Kannan and Tandy Warnow. A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM Journal on Computing, 26(6):1749-1763, 1997. URL: https://doi.org/10.1137/S0097539794279067.
  25. Tuukka Korhonen. Finding optimal tree decompositions. Master’s thesis, University of Helsinki, 2020. URL: http://urn.fi/URN:NBN:fi:hulib-202006173010.
  26. Tuukka Korhonen, Jeremias Berg, and Matti Järvisalo. Solving graph problems via potential maximal cliques: An experimental evaluation of the Bouchitté-Todinca algorithm. ACM Journal of Experimental Algorithmics, 24(1):1.9:1-1.9:19, 2019. URL: https://doi.org/10.1145/3301297.
  27. Tuukka Korhonen and Matti Järvisalo. Finding most compatible phylogenetic trees over multi-state characters. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 1544-1551. AAAI Press, 2020. URL: https://doi.org/10.1609/aaai.v34i02.5514.
  28. Mathieu Liedloff, Pedro Montealegre, and Ioan Todinca. Beyond classes of graphs with "few" minimal separators: FPT results through potential maximal cliques. Algorithmica, 81(3):986-1005, 2019. URL: https://doi.org/10.1007/s00453-018-0453-2.
  29. Daniel Lokshtanov. On the complexity of computing treelength. Discrete Applied Mathematics, 158(7):820-827, 2010. URL: https://doi.org/10.1016/j.dam.2009.10.007.
  30. Lukas Moll, Siamak Tazari, and Marc Thurley. Computing hypergraph width measures exactly. Information Processing Letters, 112(6):238-242, 2012. URL: https://doi.org/10.1016/j.ipl.2011.12.002.
  31. Noam Ravid, Dori Medini, and Benny Kimelfeld. Ranked enumeration of minimal triangulations. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 74-88. ACM, 2019. URL: https://doi.org/10.1145/3294052.3319678.
  32. Don Ringe, Tandy Warnow, and Ann Taylor. Indo-european and computational cladistics. Transactions of the Philological Society, 100(1):59-129, 2002. URL: https://doi.org/10.1111/1467-968X.00091.
  33. Marco Scutari. Learning Bayesian networks with the bnlearn R package. Journal of Statistical Software, 35(3):1-22, 2010. URL: https://doi.org/10.18637/jss.v035.i03.
  34. Charles Semple and Mike Steel. Phylogenetics. Oxford University Press, 2003. Google Scholar
  35. Ken Takata. Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph. Discrete Applied Mathematics, 158(15):1660-1667, 2010. URL: https://doi.org/10.1016/j.dam.2010.05.013.
  36. Hisao Tamaki. Computing treewidth via exact and heuristic lists of minimal separators. In Proceedings of the Special Event on Analysis of Experimental Algorithms, volume 11544 of LNCS, pages 219-236. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-34029-2_15.
  37. Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. Journal of Combinatorial Optimization, 37(4):1283-1311, 2019. URL: https://doi.org/10.1007/s10878-018-0353-z.
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