3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Feb 22 '12 at 17:36
  • $\begingroup$ 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 $\endgroup$ – Joe Feb 22 '12 at 20:28
  • $\begingroup$ $(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 . $\endgroup$ – Neal Young Jul 26 '18 at 16:46
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Feb 27 '12 at 20:59
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.