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.)
Maximum fractional packing of spanning trees.
ds.algorithms;graph theory;graph algorithms;polynomial time