License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.16
URN: urn:nbn:de:0030-drops-102179
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10217/
Go to the corresponding LIPIcs Volume Portal

Eppstein, David ; Havvaei, Elham

Parameterized Leaf Power Recognition via Embedding into Graph Products

pdf-format:
LIPIcs-IPEC-2018-16.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{eppstein_et_al:LIPIcs:2019:10217,
  author =	{David Eppstein and Elham Havvaei},
  title =	{{Parameterized Leaf Power Recognition via Embedding into Graph Products}},
  booktitle =	{13th International Symposium on Parameterized and Exact  Computation (IPEC 2018)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Christophe Paul and Michal Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10217},
  URN =		{urn:nbn:de:0030-drops-102179},
  doi =		{10.4230/LIPIcs.IPEC.2018.16},
  annote =	{Keywords: leaf power, phylogenetic tree, monadic second-order logic, Courcelle's theorem, strong product of graphs, fixed-parameter tractability}
}

Keywords: leaf power, phylogenetic tree, monadic second-order logic, Courcelle's theorem, strong product of graphs, fixed-parameter tractability
Collection: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Issue Date: 2019
Date of publication: 05.02.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI