# Edge-disjoint spanning trees and paths

From Egres Open

When does an undirected graph, with given nodes *s* and *t*, contain *k* spanning trees and *l* *s-t* paths, all of which are edge-disjoint?

The problem is NP-complete even for *k=l=*1. The proof can be found in ^{[1]}, see also ^{[2]}.

## Remarks

The existence of *k* edge-disjoint spanning trees is characterized by Tutte's disjoint tree theorem, while the existence of *l* edge-disjoint *s-t* paths is characterized by Menger's theorem.

The problem is a very special case of the more difficult Steiner tree packing problem with different terminal sets, discussed by Grötschel, Martin and Weismantel ^{[3]}.

## References

- ↑ A. Bernáth, Z. Király,
*Finding edge-disjoint subgraphs in graphs*, EGRES Quick Proofs QP-2010-04 - ↑ A. Bernáth, Z. Király,
*On the tractability of some natural packing, covering and partitioning problems*, EGRES Technical Report no. 2011-05, arXiv link - ↑ M. Grötschel, A. Martin, R. Weismantel,
*Packing Steiner trees: polyhedral investigations*, DOI link