Recognition of linear and star variants of leaf powers is in P

DOI10.1007/978-3-031-15914-5_6MaRDI QIDQ6043183zbMATH OpenOpenAlexFDO

Authors Bergougnoux Benjamin, Svein Høgemo, Jan Arne Telle, Martin Vatshelle

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

interval graphsleaf powerco-threshold tolerance graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: A $k$-leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most $k$. A graph is a leaf power if it is a $k$-leaf power for some $k$. Over 20 years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when parameterized by $k$, while leaving the main question open. In this paper, we explore this question from the perspective of two alternative models of leaf powers, showing that both a linear and a star variant of leaf powers can be recognized in polynomial-time.

Recommendations

• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Structure and linear-time recognition of 4-leaf powers
• Structure and linear time recognition of 3-leaf powers
• On k- Versus (k + 1)-Leaf Powers
• Characterising \((k,\ell )\)-leaf powers
• On (k,ℓ)-Leaf Powers
• Powers of roots in linear spaces
• scientific article; zbMATH DE number 2145259
• The variety of exterior powers of linear maps
• scientific article; zbMATH DE number 3448647

Cites work

• A Class of Balanced Matrices Arising from Location Problems
• Algorithmic Aspects of Vertex Elimination on Graphs
• Co-TT graphs and a characterization of split co-TT graphs
• Graph theory
• Graph-Theoretic Concepts in Computer Science
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Mim-width. III. Graph powers and generalized distance domination problems
• Neighborhood subtree tolerance graphs
• On graph powers for leaf-labeled trees
• On recognition of threshold tolerance graphs and their complements
• On strongly chordal graphs that are not leaf powers
• Pairwise compatibility graphs: a survey
• Parameterized leaf power recognition via embedding into graph products
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Rooted directed path 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
• Threshold tolerance graphs

Cited in

(2)

• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Structure and linear time recognition of 3-leaf powers

This page was built for publication: Recognition of linear and star variants of leaf powers is in P

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