<p>The problem gets very easy if you look at the feasible space, which is simply the spanning tree polytope, intersected with a linear number of half-spaces, one for each packing constraint. </p>

<p>The spanning tree polytope has a separation oracle (check <a href="http://www.cs.washington.edu/education/courses/cse522/09au/rravi-fsttcs09.pdf" rel="nofollow">this</a> for example), therefore since you only have an additional linear number of constraints, it carries over to yield a separation oracle for your problem. Using this oracle, you can optimize any linear functional of the polytope in polynomial time.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-27T20:59:09.783Z
I am not sure I understand your answer. The spanning tree polytope is defined over variables, one for each edge of the graph. What does it mean to say linear # of half-spaces one for each packing constraint? The packing constraints are on the edges and if we look at the primal the variables are on the trees. The right way to look at this is to write a primal with one variable for each tree and packing constraints on the edges. Then take the dual and observe that the separation oracle for the dual is simply the problem of solving the minimum spanning tree problem.
Chandra Chekuri
CC BY-SA 3.0
2012-02-25T20:41:39.097Z
2012-02-25T20:41:39.097Z
zotachidil
<p><a href="http://scholar.google.com/scholar?q=%22Packing+Algorithms+for+Arborescences+%28and+Spanning+Trees%29+in+Capacitated+Graphs.%22" rel="nofollow">Packing algorithms for arborescences (and spanning trees) in capacitated graphs</a> 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.</p>

CC BY-SA 3.0
2012-02-22T09:09:43.363Z
2012-02-22T09:09:43.363Z
Dmytro Korduban
<p>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 <em>fractional packing of spanning trees.</em></p>

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

<p>Can this be done in polynomial time?  If so, how?</p>

<p>(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.)</p>

CC BY-SA 3.0
2012-02-22T17:36:43.407Z
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
CC BY-SA 3.0
2012-02-22T20:28:58.317Z
The exact formulation of the problem is not clear to me from your question. But this seems like a relevant reference: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6078881
Joe
CC BY-SA 4.0
2018-07-26T16:46:24.410Z
$(1+\epsilon)$-approximate fractional spanning-tree packing can be computed in $O^*((|E|+|V|)/\epsilon^2)$ time, see Chekuri and Quanrud  (2017) https://doi.org/10.1137/1.9781611974782.51 .
Neal Young
<ds.algorithms><graph-theory><graph-algorithms><polynomial-time>
Maximum fractional packing of spanning trees.
com
# Maximum fractional packing of spanning trees.

(Asked by: username_0 on 2012-02-22)

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.)

**Tags:** ds.algorithms, graph-theory, graph-algorithms, polynomial-time

> **Comments:**
> **username_1**: It would help to know your motivation for asking the question. This can be looked up in username_0binatorial 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.  
> **username_2**: The exact formulation of the problem is not clear to me from your question. But this seems like a relevant reference: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6078881  
> **username_3**: $(1+\epsilon)$-approximate fractional spanning-tree packing can be username_0puted in $O^*((|E|+|V|)/\epsilon^2)$ time, see Chekuri and Quanrud  (2017) https://doi.org/10.1137/1.9781611974782.51 .  

---

## 2 answers

### Answer by username_4 on 2012-02-25. Score: 3

The problem gets very easy if you look at the feasible space, which is simply the spanning tree polytope, intersected with a linear number of half-spaces, one for each packing constraint.

The spanning tree polytope has a separation oracle (check [this](http://www.cs.washington.edu/education/courses/cse522/09au/rravi-fsttcs09.pdf) for example), therefore since you only have an additional linear number of constraints, it carries over to yield a separation oracle for your problem. Using this oracle, you can optimize any linear functional of the polytope in polynomial time.

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.

> **Comments:**
> **username_1**: I am not sure I understand your answer. The spanning tree polytope is defined over variables, one for each edge of the graph. What does it mean to say linear # of half-spaces one for each packing constraint? The packing constraints are on the edges and if we look at the primal the variables are on the trees. The right way to look at this is to write a primal with one variable for each tree and packing constraints on the edges. Then take the dual and observe that the separation oracle for the dual is simply the problem of solving the minimum spanning tree problem.  

---

### Answer by username_5 on 2012-02-22. Score: 2

[Packing algorithms for arborescences (and spanning trees) in capacitated graphs](http://scholar.google.username_0/scholar?q=%22Packing+Algorithms+for+Arborescences+%28and+Spanning+Trees%29+in+Capacitated+Graphs.%22) 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.


---

