# Kriesell's conjecture

Let G=(V,E) be a graph, and $T \subseteq V$. 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 $|T| \leq 5$.

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 $(2k+1+|V-T|)$-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 $O(n^{\frac{1}{3}-\epsilon})$ for any $\epsilon\gt0$, and gave an algorithm with approximation guarantee of $O(n^{\frac{1}{2}+\epsilon})$. 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 $6.5 k$-edge-connected in T. They also formulated a related conjecture on edge-disjoint T-connectors. The value $6.5 k$ has been improved to $5k+4$ by DeVos, McDonald, and Pivotto [11].

## References

1. M. Kriesell, Edge disjoint trees containing some given vertices in a graph, Journal of Combinatorial Theory B 88 (2003), 53-65. DOI link.
2. W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978), 145-164. Google Books link.
3. 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.
4. 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.
5. K. Jain, M. Mahdian, M.R. Salavatipour, Packing Steiner Trees, SODA 2003, ACM link, author link
6. L. C. Lau, An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem, Combinatorica 27 (2007), 71-90. DOI link, Author link.
7. L. Petingi, M. Talafha, Packing the Steiner trees of a graph, Networks 54 (2009), 90-94, DOI link.
8. J. Cheriyan, M.R. Salavatipour, Hardness and Approximation Results for Packing Steiner Trees, Algorithmica 45 (2006), 21-43. DOI link, manuscript. Author link.
9. P. Kaski, Packing Steiner trees with identical terminal sets, Information Processing Letters 91 (2004), 1-5, DOI link.
10. 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.
11. M. DeVos, J. McDonald, I. Pivotto, Packing Steiner Trees, arXiv link, DOI link