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
