# 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 . It follows from Mader's splitting-off theorem  that the conjecture holds if the degree of every node in V-T is even. In  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 , and Jain et al.; the latter implies that the conjecture is true if $|T| \leq 5$.

A breakthrough result by Lau  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  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  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  proved that it is NP-complete to decide whether a graph contains 2 edge-disjoint Steiner trees for T.

### Recent developments

West and Wu  improved Lau's result  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 .