2
$\begingroup$

I suspect this problem is NP-complete but I couldn't prove it, if anyone can help I'll be very grateful:

Instance: undirected, unweighted, connected graph $G=(V,E)$, positive integer $K \in \mathbb{Z}^+$

Question: Is there a spanning tree $T$ of $G$ such that $$\sum_{e=(u,v) \in E-T}d_T(u,v) \leq K$$

where $d_T(u,v)$ is the length (ie: number of edges) of the path from $u$ to $v$ in $T$. Note that the sum ranges over the complementary edges of $T$.

There is a similiar problem in the book by Garey and Johnson, namely "Shortest Total Path Length Spanning Tree" which was proved to be NP-complete in the paper "The complexity of the network design problem" (by Johnson, Lenstra and Rinnooy Kan). The difference is that the sum ranges over all pair of vertices.

The only technique I know so far is to find a reduction, is there a more suitable technique in this case? Any comment, suggestion or bibliographic reference will be of invaluable help.

$\endgroup$
3
  • 2
    $\begingroup$ (1) note that the restriction of the sum to edges that are not in $T$ is irrelevant - since the graph is connected, $T$ always has exactly $n-1$ edges so that just adds $n-1$ to the sum; (2) fyi, the problem of finding a tree that minimizes the sum corresponds to finding a low-stretch spanning tree. $\endgroup$
    – smapers
    Apr 16 '20 at 7:15
  • $\begingroup$ Both observations are very useful, thank you very much. Finding a low-stretch spanning tree will lead to an approximate/heuristic algorithm for this problem, is this correct? $\endgroup$ Apr 16 '20 at 18:37
  • 1
    $\begingroup$ Using e.g. this work, you can always find a spanning tree such that K is $O(n(\log(n)\log(\log(n))))$, but it doesn’t really tell you something about what the optimal K is (not even approximately). $\endgroup$
    – smapers
    Apr 16 '20 at 19:08
8
$\begingroup$

You are asking for the minimum weight fundamental cycle basis (in an unweighted graph). I think the standard reference for its NP-hardness is:

Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (1982), "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software, 8 (1): 26–42, doi:10.1145/355984.355988.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.