TY - JOUR
AU - Le, Van Bang
AU - Rosenke, Christian
PY - 2024/06/20
Y2 - 2024/11/08
TI - Computing Optimal Leaf Roots of Chordal Cographs in Linear Time
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 28
IS - 1
SE -
DO - 10.7155/jgaa.v28i1.2942
UR - https://jgaa.info/index.php/jgaa/article/view/2942
SP - 243-274
AB - <pre>A graph $G$ is a <em>$k$-leaf power</em>, for an integer $k \geq 2$, if there is a tree $T$ with leaf set $V(G)$ such that, for all distinct vertices $x, y \in V(G)$, the edge $xy$ exists in $G$ if and only if the distance between $x$ and $y$ in $T$ is at most $k$.</pre><pre>Such a tree $T$ is called a <em>$k$-leaf root</em> of $G$.</pre><pre> </pre><pre>The computational problem of constructing a $k$-leaf root for a given graph $G$ and an integer $k$, if any, is motivated by the challenge from computational biology to reconstruct phylogenetic trees.</pre><pre>For fixed $k$, Lafond [SODA 2022] recently solved this problem in polynomial time.</pre><pre> </pre><pre>In this paper, we propose to study <em>optimal leaf roots</em> of graphs $G$, that is, the $k$-leaf roots of $G$ with <em>minimum</em> $k$ value.</pre><pre>Thus, all $k'$-leaf roots of $G$ satisfy $k \leq k'$.</pre><pre>In terms of computational biology, seeking optimal leaf roots is more justified as they yield more probable phylogenetic trees.</pre><pre>Lafondâ€™s result does not imply polynomial-time computability of optimal leaf roots, because, even for optimal $k$-leaf roots, $k$ may (exponentially) depend on the size of $G$.</pre><pre> </pre><pre>This paper presents a linear-time construction of optimal leaf roots for chordal cographs (also known as trivially perfect graphs).</pre><pre>Additionally, it highlights the importance of the parity of the parameter $k$ and provides a deeper insight into the differences between optimal $k$-leaf roots of even versus odd $k$.</pre>
ER -