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
