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.

Improve this question
$\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
    Commented Apr 16, 2020 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$
    – Manuel Dubinsky
    Commented Apr 16, 2020 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
    Commented Apr 16, 2020 at 19:08

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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