<p>Consider a graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$n$</span> vertices.</p>
<p>What do we know about packing of <span class="math-container">$k$</span> vertex trees, Both integral and fractional packing are interesting.</p>
<p><span class="math-container">$k=2$</span>, it is just the number of edges, hence trivial</p>
<p><span class="math-container">$k=3$</span>, it is packing of paths of length <span class="math-container">$2$</span>, which is NP-hard. It is probably hard for every fixed <span class="math-container">$k\geq 3$</span>. Fractional version is solvable in polynomial time, (in fact for all constant <span class="math-container">$k$</span>, since we can write out the entire linear program)</p>
<p><span class="math-container">$k=n$</span>, we obtain the maximum spanning tree packing problem.</p>
<p>What about when <span class="math-container">$k$</span> is very close to <span class="math-container">$n$</span>, so we are packing almost spanning trees. Say when <span class="math-container">$k=n-1$</span>?</p>

CC BY-SA 4.0
2022-10-02T18:30:13.053Z
The question is not quite clear. My understanding is the following. For a given parameter $k$ you want to call a set of edges $A$ feasible if $A$ induces a tree with $k-1$ edges. Now you want to find the maximum packing of such feasible sets.   Is this correct?
Chandra Chekuri
CC BY-SA 4.0
2022-10-02T22:27:33.900Z
Regarding computing (in poly-time) a fractional packing of subtrees with $k-1$ edges, I think that you can use Ellipsoid on the dual.  I think the separation oracle would be, given an assignment of non-negative weights to the edges, to decide whether there is a subtree with $k-1$ edges of total weight less than 1.  I think that problem is solvable in P by a variant of Prim's MST algorithm.  Similarly, you could compute a $(1+\epsilon)$-approximate fractional packing using MWU algorithms with that oracle.
Neal Young
CC BY-SA 4.0
2022-10-03T04:29:23.480Z
@ChandraChekuri yes, that is much more clear. Edited the problem.
Chao Xu
CC BY-SA 4.0
2022-10-03T04:38:15.887Z
@NealYoung Thank you. Indeed, $k$-minimum spanning tree problem for constant $k$ or when $k=n-c$ for some constant $c$ is both solvable in polynomial time. So only remaining question is the integral packing and when $k=n-c$.
Chao Xu
CC BY-SA 4.0
2022-10-03T11:34:03.303Z
I don't understand your comment exactly.  Regarding the first sentence in your comment, I think finding a minimum-weight subtree with k vertices is in P for any k, not just k = O(1) or n-O(1).  Regarding the second, are you saying that you are only interested in integral packing when k = n - O(1)?  (So you don't care about the complexity for other k?)
Neal Young
CC BY-SA 4.0
2022-10-03T11:50:31.057Z
The first part, finding $k$-minimum spanning tree is NP-hard if $k$ is part of the input. https://en.wikipedia.org/wiki/K-minimum_spanning_tree . second part: yes.
Chao Xu
CC BY-SA 4.0
2022-10-03T13:34:39.497Z
Oh, I was mistaken about the problem being in P!  Thinking more carefully I see why the variant of Prim's I had in mind fails.
Neal Young
<graph-theory><optimization><spanning-tree>
Packing k vertex trees
Chao Xu
# Packing k vertex trees

(Asked by: username_0 on 2022-10-02)

Consider a graph $G=(V,E)$ with $n$ vertices.

What do we know about packing of $k$ vertex trees, Both integral and fractional packing are interesting.

$k=2$, it is just the number of edges, hence trivial

$k=3$, it is packing of paths of length $2$, which is NP-hard. It is probably hard for every fixed $k\geq 3$. Fractional version is solvable in polynomial time, (in fact for all constant $k$, since we can write out the entire linear program)

$k=n$, we obtain the maximum spanning tree packing problem.

What about when $k$ is very close to $n$, so we are packing almost spanning trees. Say when $k=n-1$?

**Tags:** graph-theory, optimization, spanning-tree

> **Comments:**
> **username_1**: The question is not quite clear. My understanding is the following. For a given parameter $k$ you want to call a set of edges $A$ feasible if $A$ induces a tree with $k-1$ edges. Now you want to find the maximum packing of such feasible sets.   Is this correct?  
> **username_2**: Regarding computing (in poly-time) a fractional packing of subtrees with $k-1$ edges, I think that you can use Ellipsoid on the dual.  I think the separation oracle would be, given an assignment of non-negative weights to the edges, to decide whether there is a subtree with $k-1$ edges of total weight less than 1.  I think that problem is solvable in P by a variant of Prim's MST algorithm.  Similarly, you could compute a $(1+\epsilon)$-approximate fractional packing using MWU algorithms with that oracle.  
> **username_0**: @ChandraChekuri yes, that is much more clear. Edited the problem.  
> **username_0**: @NealYoung Thank you. Indeed, $k$-minimum spanning tree problem for constant $k$ or when $k=n-c$ for some constant $c$ is both solvable in polynomial time. So only remaining question is the integral packing and when $k=n-c$.  
> **username_2**: I don't understand your comment exactly.  Regarding the first sentence in your comment, I think finding a minimum-weight subtree with k vertices is in P for any k, not just k = O(1) or n-O(1).  Regarding the second, are you saying that you are only interested in integral packing when k = n - O(1)?  (So you don't care about the complexity for other k?)  
> **username_0**: The first part, finding $k$-minimum spanning tree is NP-hard if $k$ is part of the input. https://en.wikipedia.org/wiki/K-minimum_spanning_tree . second part: yes.  
> **username_2**: Oh, I was mistaken about the problem being in P!  Thinking more carefully I see why the variant of Prim's I had in mind fails.  

---

## 0 answers

