The 4-Steiner Root Problem

The \(k^{th}\)-power of a graph G is obtained by adding an edge between every two distinct vertices at a distance \(\le k\) in G. We call G a k -Steiner power if it is an induced subgraph of the \(k^{th}\)-power of some tree \(T_{}\). In particular, G is a k -leaf power if all vertices in V(G) are leaf-nodes of \(T_{}\). 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\). As a byproduct, we give the first known polynomial-time recognition algorithm for 6-leaf powers. Our work combines several new algorithmic ideas that help us overcome the previous limitations on the usual dynamic programming approach for these problems.