# Tree packing duality

Consider the following two maximazation problem for tree-packing.

Let ${\cal T}$ be the set of all spanning trees of $G$.

---
**P1.** $\phi_{frac} = \max \sum_{T \in {\cal T}} y_T$ such that
* $\sum_{T:e \in T} y_T \leq 1$ for all $e \in E$,
* $y_T \geq 0$ for all $T \in {\cal T}$.

Let the integral solution to this is $\phi_{int}$.

We are also interested in the dual (D1) of P1. We call it *covering LP*.

**D1.** $\psi_{frac}= \min \sum_{e \in E} z_e$ such that
* $\sum_{e \in T} z_e \geq 1$ for all $T \in {\cal T}$,
* $z_e \geq 0$ for all $e \in E$.

**To interpret the integral solution of D1 ($\psi_{int}$):** Define a tree $T$ is *covered* by an edge $e$ if $e \in E(T)$. ==Pick the minimal set of edges $S$ such that each tree $T \in {\cal T}$ is covered by at least one edge from $S$.==

**To interpret the fractional solution of D1:** Assign weights to edges in $E$ such that total weight of each tree $T \in {\cal T}$ is at least 1.

**Claim.** $\psi_{int} = \lambda$. ==(i.e., integral D1 is also a cut minimizer)==

*Proof.* ($\lambda \geq \psi_{int}$) Consider a mincut $C$. Each $T \in {\cal T}$ must have at least one edge in $C$ and hence $C$ is a valid covering. Hence, $\lambda \geq \psi_{int}$.

Suppose $\lambda > \psi_{int}$. Consider the edge $e \in C$ which is not in the arg max of $\psi_{int}$, the set $S$. The goal is to exhibit a $T$ which is not coverted by $S$. We do the following procedure to construct such a tree:
1. Start with $U = v$ and $U' = V - v$ for some vertex $v$.
2. For $n-1$ rounds, do the following:
2a. Find an edge not in $S$ which connects $U$ and $U'$. Let $v'$ be the end point of that edge in $U'$
2b. $U = U \cup v'$ and $U' = U' - v'$.

The step (2a) always succeds as the number of edges going from $U$ to $U'$ is at least $\lambda > \psi_{int}$. This is a contradiction. :black_small_square:

**$k$-cut.** We change D1 in the following way:

**k-D1.** $\psi_{frac}^{(k)}= \min \sum_{e \in E} z_e$ such that
* $\sum_{e \in T} z_e \geq (k-1)$ for all $T \in {\cal T}$,
* $z_e \geq 0$ for all $e \in E$.

**Claim.** Let $\lambda^{(k)}$ denote the minimum $k$-way cut. Then $\psi_{int}^{(k)} = \lambda^{(k)}$. ==(i.e., integral k-D1 is also a $k$-cut minimizer)==

*Proof.* As before, any tree must have at least $k-1$ edges in any $k$-cut. Hence a $k$-cut is a valid $(k-1)$-cover and $\psi_{int}^{(k)} \leq \lambda^{(k)}$.

Suppose $\psi_{int}^{(k)} < \lambda^{(k)}$. The idea is as before but this time we proceed with forest construction which resembles the spanning tree construction of Kruskal. Start with any arbitrary $k$-partition. There is an edge in the cut which is not a covering edge. Next time put that edge in a component. The invariant we maintain is the following: Each connected component thus formed is contained in a part and we grow the forest by one edge at a time.

Towards the end, when there are $k-1$ trees in the forest, we cannot maintain the invariant. We then connect the forest by any available edge (non necessary a non-covering edge). Thus we will use at most $k-2$ covering edge. This is a contradiction. :black_small_square:

---

Let $\hat T$ be a subset of ${\cal T}$ and can be a multiset.

**P2.** $\rho_{frac} = \max_{\hat T \subseteq {\cal T}} \frac{|\hat T|}{\max_e |L^{\hat T}(e)|}$ where $L^{\hat T}(e) = \{T \in {\cal T} \mid e \in T\}$.

Let the maximizer when $\hat T$ is edge-disjoint is $\rho_{int}$.

**Claim.** $\phi_{frac} \geq \rho_{frac}$.

*Proof.* Given a $\hat T$, set $y_T$ as follows: $y_T = \frac 1 {\max_e |L^{\hat T}(e)|}$ if $T \in \hat T$, otherwise $y_T = 0$. This assignment of $\bar y$ achieves $\sum_T y_T = \rho_{frac}$. As $\phi_{frac}$ can only be larger, the claim follows.

**Conjecture.** $\phi_{frac} \leq \rho_{frac}$. ==Check!==

---

We know from Nash-Williams:

**Theorem (NW).** $\rho_{int} = \phi_{int} = \min_{\cal P}\frac{E(G/\cal P)}{|{\cal P}| -1}$.

## Application in short tree packing

**Definition.** Consider a graph $G$ with diameter $D$. The minimum $\epsilon$-diameter-increasing cut $\hat \lambda_\epsilon$ is the minimum number of edges which needs to be removed from $G$ in order to increase the diameter to at least $(1 + \epsilon)D$.

**Observation.** $\hat \lambda_\epsilon \leq \hat \lambda_{\epsilon'}$ for any $\epsilon \leq \epsilon'$.

We look at the variant of L1 and D1 for short trees. Here $\hat{\cal T}$ is the set of all trees with diamter $D$. We will also use the notation $\hat {\cal T}_\epsilon$ to be the set of all trees with diameter at most $D(1 + \epsilon)$. Here $\hat {\cal T}_0 = \hat {\cal T}$.

**short-P1.** $\hat \phi_{frac} = \max \sum_{T \in \hat{\cal T}} y_T$ such that
* $\sum_{T:e \in T} y_T \leq 1$ for all $e \in E$,
* $y_T \geq 0$ for all $T \in \hat{\cal T}$.

Let the integral solution to this is $\hat \phi_{int}$.

**short-D1.** $\hat \psi_{frac}^\epsilon= \min \sum_{e \in E} z_e$ such that
* $\sum_{e \in T} z_e \geq 1$ for all $T \in \hat{\cal T}_\epsilon$,
* $z_e \geq 0$ for all $e \in E$.

**Claim.** $D \leq n/\lambda$.

**Claim.** $\hat \psi_{int}^\epsilon = \hat \lambda_\epsilon$.

*Proof.* ($\hat \psi_{int}^\epsilon \leq \hat \lambda_\epsilon$ for all $\epsilon \geq 0$) The edge set $S$ achievng $\hat \lambda_\epsilon$ is a valid cover. Each short tree (of diameter $D(1 + \epsilon)$ must share at least one edge from $S$.

($\hat \psi_{int}^\epsilon \geq \hat \lambda_\epsilon$) Suppose $\hat \psi_{int}\epsilon < \hat \lambda_\epsilon$. Remove the set $S$ from $G$. By definition and minimality of $\hat \lambda_\epsilon$, the graph $G$ still has diameter at most $D(1 + \epsilon)$. By doing an appropriate BFS in $G - S$, we get a tree of depth at most $D(1 + \epsilon)$. This is a contradiction. :black_small_square:

**Claim.** $\lambda \geq \hat \lambda_\epsilon \geq \frac \epsilon {1+\epsilon} \cdot \lambda$ for any $\epsilon \geq 0$.

*Proof.* Showing $\lambda \geq \hat \lambda_\epsilon$ is trivial. This is because any min-cut is also a min diameter-increasing cut.

($\hat \lambda_\epsilon \geq \frac \epsilon {1+\epsilon} \cdot \lambda$) Suppose not. Consider the graph $G$ with connectivity $\lambda$ such that $D = n/\lambda$. Let $S$ is the set of edges achieving $\hat \lambda_\epsilon$ in $G$. After removing $S$ from $G$, the residual graph $G - S$ has degree at least $\lambda - \hat \lambda_\epsilon = \frac \lambda {1 + \epsilon}$ which implies that the diameter is at most $\frac n \lambda (1 + \epsilon)$. So there must exist a short tree in the residual graph. This is a contradiction. :black_small_square:

**Claim.** $\hat \psi_{int}^\epsilon \geq \hat \psi_{frac}^\epsilon \geq \frac 1 2 \hat \psi_{int}^\epsilon$.

*Proof.* First, let's assume that $z_e >0$ for all $e \in E$ in the optimal $z$ for short-D1. By complementary slackness condition, we have that $\sum_{T:e \in T} y_T = 1$ for all $e \in E$. Now,

$\sum_e \sum_{T:e \in T} y_T = \sum_T \sum_{e \in T} y_T = (n-1) \sum_T y_T = m$.

Also, mindeg (G) $\leq \frac {2m} n = 2(1 - \frac 1 n) \sum_T y_T \leq 2 \hat \psi_{frac}^\epsilon$. Hence, the integral solution where $z_e = 1$ for the edges incident on the node with mindegree and 0 otherwise is at most twice the fractional minimum.

Now, let's consider a general case where we allow some $z_e = 0$. The idea is to contract the vertices $u$ and $v$ where $e = (u,v)$. The minimizer $z'$ of the resulting graph is also a valid solution to the original graph with the same cost. ==Complete the argument==

<!---Combining, we get $\hat \phi_{int}^\epsilon \geq \hat \phi_{frac}^\epsilon = \hat \psi_{frac}^\epsilon \geq \hat \psi_{int}^\epsilon = \hat \lambda_\epsilon \geq \frac \epsilon {1+\epsilon} \cdot \lambda$ for any $\epsilon \geq 0$.--->