Edge-disjoint spanning trees and paths

From Egres Open
Jump to: navigation, search

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?

Solved b.jpg

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


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].


  1. A. Bernáth, Z. Király, Finding edge-disjoint subgraphs in graphs, EGRES Quick Proofs QP-2010-04
  2. 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
  3. M. Grötschel, A. Martin, R. Weismantel, Packing Steiner trees: polyhedral investigations, DOI link