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

<p>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, <a href="https://doi.org/10.1145/355984.355988" rel="noreferrer">doi:10.1145/355984.355988</a>.</p>

CC BY-SA 4.0
2020-04-16T05:41:25.143Z
2020-04-16T05:41:25.143Z
David Eppstein
<p>I suspect this problem is NP-complete but I couldn't prove it, if anyone can help I'll be very grateful:</p>

<p><strong>Instance</strong>: undirected, unweighted, connected graph <span class="math-container">$G=(V,E)$</span>, positive integer <span class="math-container">$K \in \mathbb{Z}^+$</span></p>

<p><strong>Question</strong>: Is there a spanning tree <span class="math-container">$T$</span> of <span class="math-container">$G$</span> such that 
<span class="math-container">$$\sum_{e=(u,v) \in E-T}d_T(u,v) \leq K$$</span></p>

<p>where <span class="math-container">$d_T(u,v)$</span> is the length (ie: number of edges) of the path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> in <span class="math-container">$T$</span>. Note that the sum ranges over the complementary edges of <span class="math-container">$T$</span>.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2020-04-16T07:15:12.753Z
(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*.
smapers
CC BY-SA 4.0
2020-04-16T18:37:46.487Z
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?
Manuel Dubinsky
CC BY-SA 4.0
2020-04-16T19:08:14.627Z
Using e.g. [this work](https://arxiv.org/abs/cs/0411064), 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).
smapers
<np-complete><spanning-tree>
NP-completeness: sum of "some" paths in a spanning tree
Manuel Dubinsky
# NP-completeness: sum of "some" paths in a spanning tree

(Asked by: username_0 on 2020-04-15)

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.

**Tags:** np-complete, spanning-tree

> **Comments:**
> **username_1**: (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*.  
> **username_0**: 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?  
> **username_1**: Using e.g. [this work](https://arxiv.org/abs/cs/0411064), 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).  

---

## 1 answers

### Answer by username_2 on 2020-04-16. Score: 8 | Accepted answer

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](https://doi.org/10.1145/355984.355988).


---

