# Maximum fractional packing of spanning trees.

Given a graph $G$, let $\{T_1,\ldots,T_k\}$ be a set of spanning trees with associated nonnegative weights $\{w_1,\ldots,w_k\}$ such that for every edge $e$, $\sum_{e\in T_i}w_i \leq 1$. This is a fractional packing of spanning trees.

What is the maximum total weight of such a fractional packing, i.e. the maximum possible value of $\sum_{i=1}^kw_i$?

Can this be done in polynomial time? If so, how?

(Note that the dual linear program asks for the minimum total edge weight such that every spanning tree receives weight at least one, so the dual is a minimum fractional edge cut problem.)

• It would help to know your motivation for asking the question. This can be looked up in combinatorial optimization books such as that of Schrijver, however an insightful answer from some one on stack exchange is valuable. For that, you need to say more. – Chandra Chekuri Feb 22 '12 at 17:36
• The exact formulation of the problem is not clear to me from your question. But this seems like a relevant reference: ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6078881 – Joe Feb 22 '12 at 20:28
• $(1+\epsilon)$-approximate fractional spanning-tree packing can be computed in $O^*((|E|+|V|)/\epsilon^2)$ time, see Chekuri and Quanrud (2017) doi.org/10.1137/1.9781611974782.51 . – Neal Young Jul 26 '18 at 16:46

If I remember well, using the ellipsoid algorithm, you can get a running time of $\tilde{O}(m^2 \cdot T)$, where $T$ is the running time of the separation oracle (which in this case you can get from a min-cut algorithm). Probably not as good as other existing algorithms, but it gives you an idea of how you can quickly check that the problem is polynomial time solvable.
Packing algorithms for arborescences (and spanning trees) in capacitated graphs by Gabow and Manu claims $O(n^3 m \log{(n^2/m)})$ bound. The paper contains references to earlier results as well. I don't know if it's the latest result.