Recognizing k -Leaf Powers in Polynomial Time, for Constant k

DOI10.1145/3614094MaRDI QIDQ6075860zbMATH OpenOpenAlexFDO

Authors Manuel Lafond

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.15421

zbMATH Keywords

algorithmsgraph theoryleaf powers

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: A graph $G$ is a $k$-leaf power if there exists a tree $T$ whose leaf set is $V(G)$, and such that $uvinE(G)$ if and only if the distance between $u$ and $v$ in $T$ is at most $k$. The graph classes of $k$-leaf powers have several applications in computational biology, but recognizing them has remained a challenging algorithmic problem for the past two decades. The best known result is that $6$-leaf powers can be recognized in polynomial time. In this paper, we present an algorithm that decides whether a graph $G$ is a $k$-leaf power in time $O(n^{f(k)})$ for some function $f$ that depends only on $k$ (but has the growth rate of a power tower function). Our techniques are based on the fact that either a $k$-leaf power has a corresponding tree of low maximum degree, in which case finding it is easy, or every corresponding tree has large maximum degree. In the latter case, large degree vertices in the tree imply that $G$ has redundant substructures which can be pruned from the graph. In addition to solving a longstanding open problem, we hope that the structural results presented in this work can lead to further results on $k$-leaf powers.

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
• A survey on pairwise compatibility graphs
• Algorithms and Computation
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Graph-Theoretic Concepts in Computer Science
• Kernelization. Theory of parameterized preprocessing
• Kernelization: new upper and lower bound techniques
• Linear-Time Algorithms for Tree Root Problems
• Mim-width. III. Graph powers and generalized distance domination problems
• On (k,ℓ)-Leaf Powers
• On graph powers for leaf-labeled trees
• On k- Versus (k + 1)-Leaf Powers
• On strongly chordal graphs that are not leaf powers
• On the domination number of $t$-constrained de Bruijn graphs
• Pairwise compatibility graphs: a survey
• Parameterized leaf power recognition via embedding into graph products
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Recognition of linear and star variants of leaf powers is in P
• Rooted directed path graphs are leaf powers
• Some remarks about leaf roots
• Statistical Inference of Phylogenies
• Strictly chordal graphs are leaf powers
• Structure and linear time recognition of 3-leaf powers
• Structure and linear-time recognition of 4-leaf powers
• The 3-Steiner Root Problem
• The 4-Steiner Root problem
• The NLC-width and clique-width for powers of graphs of bounded tree-width

Cited in

(5)

• Recognition of linear and star variants of leaf powers is in P
• Lower bounds for leaf rank of leaf powers
• Faster algorithms for 3-leaf power modification problems
• Structure and linear time recognition of 3-leaf powers
• Smaller kernels for 3-leaf power modifications problems

This page was built for publication: Recognizing k -Leaf Powers in Polynomial Time, for Constant k

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075860)