An "edge-spanning-tree" of minimum height

Question

Given any connected undirected graph, we can convert it into a tree by "detaching" some edges from one of their endpoints. For example, consider the graph with the following edges: $$ (1) ~~~~~~~~~~~~~ a-b, b-c, c-a, c-d, d-e $$ We can detach the edge b-c from the vertex c (adding a new vertex c' of degree 1), and get the graph: $$ (2) ~~~~~~~~~~~~~ a-b, b-c', c-a, c-d, d-e $$ which is a tree (a path of length 5). We can call it an "edge-spanning-tree", as it is a tree that spans all edges of the graph.

Among all edge-spanning-trees, I would like to find the one with minimum possible height (minimum among all possible roots). The height of graph (2) is 3, e.g. when the root is c. However, starting from the original graph (1), we can detach the edge b-c from the vertex b instead, to get the following tree: $$ (3) ~~~~~~~~~~~~~ a-b, b'-c, c-a, c-d, d-e $$ the height of this tree is 2 (when the root is c).

QUESTION: Is there a polynomial-time algorithm that finds an "edge-spanning-tree" of minimum height?

Answer 1

Here is an idea. The root of your desired tree should be one of the centers (a vertex with minimum eccentricity) of the graph $G$. You run BFS from each of the nodes in $G$ and observe the resulting BFS tree. We pick the tree $T$ that has the lowest height. There will be some missing edges that were present in $G$ but have not been selected in $T$. For all such edges, $(u,v) \notin T$, We augment an edge $(u,v')$ into $T$ if $u$ is closer to the root than $v$ in $T$; otherwise, we augment an edge $(u',v)$ into $T$. This may increase the height of $T$ by at most one (when both $u$ and $v$ are leaves in $T$).

In the case of the graph having multiple centers, we may try other BFS trees $T'$ rooted at other centers (all of which are of the same height as $T$), to see whether they remain at the same height even after these augmentations. Finally, report the optimal one.

• codeR: A formal proof of correctness should be possible to derive. I also expect more efficient solutions to exist as well. :)