Polynomial-time Recognition of 4-Steiner Powers

Abstract

The $k^{th}$-power of a given graph $G=(V,E)$ is obtained from $G$ by adding an edge between every two distinct vertices at a distance at most $k$ in $G$. We call $G$ a $k$-Steiner power if it is an induced subgraph of the $k^{th}$-power of some tree. Our main contribution is a polynomial-time recognition algorithm of $4$-Steiner powers, thereby extending the decade-year-old results of (Lin, Kearney and Jiang, ISAAC'00) for $k=1,2$ and (Chang and Ko, WG'07) for $k=3$. A graph $G$ is termed $k$-leaf power if there is some tree $T$ such that: all vertices in $V(G)$ are leaf-nodes of $T$, and $G$ is an induced subgraph of the $k^{th}$-power of $T$. As a byproduct of our main result, we give the first known polynomial-time recognition algorithm for $6$-leaf powers.