Document Open Access Logo

Parameterized Leaf Power Recognition via Embedding into Graph Products

Authors David Eppstein, Elham Havvaei

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.16.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

David Eppstein
  • Computer Science Department, University of California, Irvine, USA
Elham Havvaei
  • Computer Science Department, University of California, Irvine, USA

Funding

  • Eppstein, David: Supported in part by NSF grants CCF-1618301 and CCF-1616248.

Cite As Get BibTex

David Eppstein and Elham Havvaei. Parameterized Leaf Power Recognition via Embedding into Graph Products. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.16

Abstract

The k-leaf power graph G of a tree T is a graph whose vertices are the leaves of T and whose edges connect pairs of leaves at unweighted distance at most k in T. Recognition of the k-leaf power graphs for k >= 6 is still an open problem. In this paper, we provide an algorithm for this problem for sparse leaf power graphs. Our result shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by k and by the degeneracy of the given graph. To prove this, we describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of k and the degeneracy of G. As a result, we can use methods based on monadic second-order logic (MSO_2) to recognize the existence of a leaf power as a subgraph of the product graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Fixed parameter tractability
Keywords
  • leaf power
  • phylogenetic tree
  • monadic second-order logic
  • Courcelle's theorem
  • strong product of graphs
  • fixed-parameter tractability

Metrics

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

References

  1. Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.6.
  2. Michael J Bannister and David Eppstein. Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In International Symposium on Graph Drawing, pages 210-221. Springer, 2014. Google Scholar
  3. Umberto Bertelé and Francesco Brioschi. Nonserial Dynamic Programming. Academic Press, 1972. Google Scholar
  4. Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybernet., 11(1-2):1-21, 1993. Google Scholar
  5. Andreas Brandstädt and Christian Hundt. Ptolemaic graphs and interval graphs are leaf powers. In Latin American Symposium on Theoretical Informatics, pages 479-491. Springer, 2008. Google Scholar
  6. Andreas Brandstädt, Christian Hundt, Federico Mancini, and Peter Wagner. Rooted directed path graphs are leaf powers. Discrete Math., 310(4):897-910, 2010. URL: http://dx.doi.org/10.1016/j.disc.2009.10.006.
  7. Andreas Brandstädt and Van Bang Le. Structure and linear time recognition of 3-leaf powers. Inform. Process. Lett., 98(4):133-138, 2006. URL: http://dx.doi.org/10.1016/j.ipl.2006.01.004.
  8. Andreas Brandstädt, Van Bang Le, and Dieter Rautenbach. A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. Discrete Math., 309(12):3843-3852, 2009. URL: http://dx.doi.org/10.1016/j.disc.2008.10.025.
  9. Andreas Brandstädt, Van Bang Le, and R. Sritharan. Structure and linear-time recognition of 4-leaf powers. ACM Trans. Algorithms, 5(1):A11:1-A11:22, 2009. URL: http://dx.doi.org/10.1145/1435375.1435386.
  10. Andreas Brandstädt and Peter Wagner. On k-versus (k+ 1)-leaf powers. In International Conference on Combinatorial Optimization and Applications, pages 171-179. Springer, 2008. Google Scholar
  11. Maw-Shang Chang and Ming-Tat Ko. The 3-Steiner root problem. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 109-120. Springer, 2007. Google Scholar
  12. Zhi-Zhong Chen, Tao Jiang, and Guohui Lin. Computing phylogenetic roots with bounded degrees and errors. SIAM J. Comput., 32(4):864-879, 2003. URL: http://dx.doi.org/10.1137/S0097539701389154.
  13. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  14. Bruno Courcelle. On the expression of graph properties in some fragments of monadic second-order logic. In Neil Immerman and Phokion G. Kolaitis, editors, Descriptive Complexity and Finite Models: Proceedings of a DIMACS Workshop, January 14-17, 1996, Princeton University, volume 31 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 33-62. American Mathematical Society, Providence, RI, 1997. Google Scholar
  15. Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. In Handbook of graph grammars and computing by graph transformation, Vol. 1, pages 313-400. World Scientific, River Edge, NJ, 1997. URL: http://dx.doi.org/10.1142/9789812384720_0005.
  16. Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg. Handle-rewriting hypergraph grammars. J. Comput. System Sci., 46(2):218-270, 1993. URL: http://dx.doi.org/10.1016/0022-0000(93)90004-G.
  17. Bruno Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: http://dx.doi.org/10.1007/s002249910009.
  18. Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Error compensation in leaf root problems. In International Symposium on Algorithms and Computation, pages 389-401. Springer, 2004. Google Scholar
  19. Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Extending the tractability border for closest leaf powers. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 397-408. Springer, 2005. Google Scholar
  20. David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, and Stephen Wismath. On the planar split thickness of graphs. Algorithmica, 80(3):977-994, 2018. URL: http://dx.doi.org/10.1007/s00453-017-0328-y.
  21. Walter M. Fitch and Emanuel Margoliash. Construction of phylogenetic trees. Science, 155(3760):279-284, 1967. URL: http://dx.doi.org/10.1126/science.155.3760.279.
  22. Martin Grohe. Computing crossing numbers in quadratic time. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pages 231-236, New York, 2001. ACM. URL: http://dx.doi.org/10.1145/380752.380805.
  23. Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs without K_n,n. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 196-205. Springer, 2000. Google Scholar
  24. Frank Gurski and Egon Wanke. The clique-width of tree-power and leaf-power graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 76-85. Springer, 2007. Google Scholar
  25. Rudolf Halin. S-functions for graphs. J. Geometry, 8(1-2):171-186, 1976. URL: http://dx.doi.org/10.1007/BF01917434.
  26. Petr Hliněný. Branch-width, parse trees, and monadic second-order logic for matroids. J. Combin. Theory Ser. B, 96(3):325-351, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.08.005.
  27. William Kennedy, Guohui Lin, and Guiying Yan. Strictly chordal graphs are leaf powers. J. Discrete Algorithms, 4(4):511-525, 2006. URL: http://dx.doi.org/10.1016/j.jda.2005.06.005.
  28. David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417-427, 1983. URL: http://dx.doi.org/10.1145/2402.322385.
  29. Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. On graph powers for leaf-labeled trees. J. Algorithms, 42(1):69-108, 2002. URL: http://dx.doi.org/10.1006/jagm.2001.1195.
  30. Dieter Rautenbach. Some remarks about leaf roots. Discrete Math., 306(13):1456-1461, 2006. URL: http://dx.doi.org/10.1016/j.disc.2006.03.030.
  31. Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309-322, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90023-4.
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