# Kriesell's conjecture

Let *G=(V,E)* be a graph, and [math]T \subseteq V[/math]. Is it true that if *T* is *2k*-edge-connected in *G* (i.e. there are *2k* edge-disjoint paths between any two nodes of *T*), then *G* contains *k* edge-disjoint Steiner trees for *T*?

## Remarks

This conjecture was proposed by Matthias Kriesell ^{[1]}. It follows from Mader's splitting-off theorem ^{[2]} that the conjecture holds if the degree of every node in *V-T* is even. In ^{[3]} it was shown that if *G* is *3k*-edge-connected and *V-T* is stable, then *G* contains *k* edge-disjoint Steiner trees for *T*. Other bounds have been proved by Petingi and Rodriguez ^{[4]}, and Jain et al.^{[5]}; the latter implies that the conjecture is true if [math]|T| \leq 5[/math].

A breakthrough result by Lau ^{[6]} was that if *T* is *26k*-edge-connected in *G* then it has *k* edge-disjoint Steiner trees. This gave the first constant-factor approximation result for the edge-disjoint Steiner trees problem. Petingi and Talafha ^{[7]} showed that the conjecture is true if the edge set of *G* can be partitioned into Steiner trees, and for general graphs they obtained that [math](2k+1+|V-T|)[/math]-edge-connectivity is sufficient.

### Hardness results

Cheriyan and Salavatipour ^{[8]} proved that the problem of finding maximum number of edge-disjoint (or vertex-disjoint) Steiner trees is APX-hard even if there are only 4 terminals. They also showed that the directed version is hard to approximate within factor of [math]O(n^{\frac{1}{3}-\epsilon})[/math] for any [math]\epsilon\gt0[/math], and gave an algorithm with approximation guarantee of [math]O(n^{\frac{1}{2}+\epsilon})[/math]. Kaski ^{[9]} proved that it is NP-complete to decide whether a graph contains 2 edge-disjoint Steiner trees for *T*.

### Recent developments

West and Wu ^{[10]} improved Lau's result ^{[6]} by showing that there are *k* edge-disjoint Steiner trees if *G* is [math]6.5 k[/math]-edge-connected in *T*. They also formulated a related conjecture on edge-disjoint T-connectors. The value [math]6.5 k[/math] has been improved to [math]5k+4[/math] by DeVos, McDonald, and Pivotto ^{[11]}.

## References

- ↑ M. Kriesell,
*Edge disjoint trees containing some given vertices in a graph*, Journal of Combinatorial Theory B 88 (2003), 53-65. DOI link. - ↑ W. Mader,
*A reduction method for edge-connectivity in graphs*, Ann. Discrete Math. 3 (1978), 145-164. Google Books link. - ↑ A. Frank, T. Király, M. Kriesell,
*On decomposing a hypergraph into k connected sub-hypergraphs*, Discrete Applied Mathematics 131 (2003), 373-383, DOI link. Preliminary version: EGRES Technical Report no. 2001-02. - ↑ L. Petingi, J. Rodriguez,
*Bounds on the maximum number of edge-disjoint Steiner trees of a graph*, Congressus Numerantium 145 (2000) 43-52. Citeseer link. - ↑ K. Jain, M. Mahdian, M.R. Salavatipour,
*Packing Steiner Trees*, SODA 2003, ACM link, author link - ↑
^{6.0}^{6.1}L. C. Lau,*An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*, Combinatorica 27 (2007), 71-90. DOI link, Author link. - ↑ L. Petingi, M. Talafha,
*Packing the Steiner trees of a graph*, Networks 54 (2009), 90-94, DOI link. - ↑ J. Cheriyan, M.R. Salavatipour,
*Hardness and Approximation Results for Packing Steiner Trees*, Algorithmica 45 (2006), 21-43. DOI link, manuscript. Author link. - ↑ P. Kaski,
*Packing Steiner trees with identical terminal sets*, Information Processing Letters 91 (2004), 1-5, DOI link. - ↑ D.B. West, H. Wu,
*Packing of Steiner trees and S-connectors in graphs*, Journal of Combinatorial Theory B 102 (2012), 186–205, DOI link, Author link. - ↑ M. DeVos, J. McDonald, I. Pivotto,
*Packing Steiner Trees*, arXiv link, DOI link