4.4. An MST ILP with Integrality Gap 1*

As an application of complementary slackness, let us return to the minimum spanning tree problem. Complementary slackness provides the tool to prove our claim that the LP relaxation of (2.16) has an integral optimal solution. For easier reference, here is the ILP formulation again:

\[\begin{gathered} \text{Minimize } \sum_{e \in E} w_e x_e\\ \begin{aligned} \text{s.t. } \sum_{e \in E} x_e &\ge n - 1\\ \sum_{\substack{(u,v) \in E\\u,v \in S}} x_{u,v} &\le |S| - 1 && \forall \emptyset \subset S \subseteq V\\ x_e &\in \{0, 1\} && \forall e \in E. \end{aligned} \end{gathered}\tag{4.14}\]

Lemma 4.6: The LP relaxation of the ILP (4.14) has an integral optimal solution.

Proof: This is in fact an alternate (and quite a bit less intuitive) correctness proof of Kruskal's algorithm. Recall how Kruskal's algorithm works: It initializes the MST to have no edges: \(T = (V, \emptyset)\). Then it sorts the edges in \(G\) by increasing weight and inspects them in order. For every edge \((u,v)\), if its endpoints belong to different components of \(T\) at the time this edge is inspected, the algorithm adds the edge \((u,v)\) to \(T\), thereby merging these two connected components; otherwise, it discards the edge \((u,v)\).

We can observe how the connected components of \(T\) change over the course of the algorithm. Let \(\langle e_1, \ldots, e_m \rangle\) be the sorted sequence of edges, let \(E_i = \{ e_1, \ldots, e_i \}\), let \(G_i = (V, E_i)\), and let \(T_i\) be the state of \(T\) after the \(i\)th iteration of the algorithm, that is, after the algorithm has inspected the edges \(e_1, \ldots, e_i\). Then the connected components of \(G_i\) and \(T_i\) have the same vertex sets.

For every subset \(S \subseteq V\) with \(|S| \ge 2\), let \(c_S\) be the minimal index and let \(d_S\) be the maximal index such that \(G_{c_S}, \ldots, G_{d_S - 1}\) have connected components with vertex set \(S\). In other words, \(c_S\) is the "creation time" of the first connected component with vertex set \(S\). The graphs \(G_{c_S+1}, \ldots, G_{d_S-1}\) may add more edges but no vertices to this component. \(d_S\) is the "destruction time" of the last connected component with vertex set \(S\). In \(G_{d_S}\), \(S\) becomes part of a larger connected component. For \(S = V\), \(d_V = \infty\). If \(|S| < 2\) or there exists no index \(1 \le i \le m\) such that \(S\) is the vertex set of a connected component of \(G_i\), then \(c_S = d_S = \infty\).

Intuitively, \(e_{c_S}\) is the last edge with both endpoints in \(S\) that is added to the MST \(T\), and \(e_{d_S}\) is the first edge with exactly one endpoint in \(S\) that is added to \(T\).

Now let us turn to the LP formulation. The primal LP is the LP relaxation of (4.14):

\[\begin{gathered} \text{Minimize } \sum_{e \in E} w_e x_e\\ \begin{aligned} \text{s.t. } \sum_{e \in E} x_e &\ge n - 1\\ \sum_{\substack{(u,v) \in E\\u,v \in S}} x_{u,v} &\le |S| - 1 && \forall \emptyset \subset S \subseteq V\\ x_e &\ge 0 && \forall e \in E. \end{aligned} \end{gathered}\tag{4.15}\]

Technically, the constraint \(x_e \in \{0, 1\}\) from (4.14) should become \(0 \le x_e \le 1\) in (4.15), but the \(x_e \le 1\) part is redundant and can be omitted: If \(e = (x, y)\), then the constraint

\[\sum_{\substack{(u,v) \in E\\u, v \in S}} x_{u,v} \le |S| - 1 \text{ for } S = \{x, y\}\]

already ensures that \(x_e \le 1\).

The dual of (4.15) is

\[\begin{gathered} \text{Maximize } (n - 1) y_0 - \sum_{\emptyset \subset S \subseteq V}\ (|S| - 1) y_S\\ \begin{aligned} \text{s.t. } y_0 - \sum_{\substack{\emptyset \subset S \subseteq V\\u, v \in S}} y_S &\le w_{u, v} && \forall (u, v) \in E\\ y_0 &\ge 0\\ y_S &\ge 0 && \forall \emptyset \subset S \subseteq V. \end{aligned} \end{gathered}\tag{4.16}\]

Here, \(y_0\) is the dual variable corresponding to the first constraint in (4.15) and for each \(\emptyset \subset S \subseteq V\), \(y_S\) is the dual variable corresponding to the constraint \(\sum_{(u,v) \in E; u, v \in S} x_{u,v} \le |S| - 1\).

Note that the dual is a maximization LP because the primal is a minimization LP, and the coefficients of \(y_S\) both in the dual objective function and in all dual constraints that involve \(y_S\) are negated because the primal constraint \(\sum_{(u,v) \in E; u, v \in S} x_{(u,v)} \le |S| - 1\) is an upper bound constraint but should be a lower bound constraint, given that the primal is a minimization LP. Section 4.5 discusses in greater detail how to deal with such deviations from LPs in canonical form when constructing their duals.

Now let \(T\) be the MST computed by Kruskal's algorithm. By Lemma 2.9, the vector \(\hat x\) defined as

\[\hat x_e = \begin{cases} 1 & \text{if } e \in T\\ 0 & \text{otherwise} \end{cases}\]

is a feasible solution of (4.15) (because it is a feasible solution of (4.14) and (4.15) is the LP relaxation of (4.14)). Next we show that the following is a feasible solution of (4.16) and that \(\hat x\) and \(\hat y\) satisfy complementary slackness:

\[\begin{aligned} \hat y_S &= \begin{cases} w_{e_{d_S}} - w_{e_{c_S}} & \text{if } d_S < \infty\\ -w_{e_{c_V}} & \text{if } S = V \text{ and } w_{e_{c_V}} \le 0\\ 0 & \text{otherwise} \end{cases}\\ \hat y_0 &= \begin{cases} \rlap{w_{e_{c_V}}}\phantom{w_{e_{d_S}} - w_{e_{c_S}}} & \text{if } w_{e_{c_V}} \ge 0\\ 0 & \text{otherwise} \end{cases} \end{aligned}\]

Thus, by Theorem 4.5 , \(\hat x\) and \(\hat y\) are optimal solutions of (4.15) and (4.16), respectively. Since \(\hat x\) is integral, this proves the lemma.

First we prove that \(\hat y\) is a feasible solution of (4.16).

The definitions of \(\hat y_0\) and \(\hat y_V\) explicitly ensure that \(\hat y_0 \ge 0\) and \(\hat y_V \ge 0\).

For \(\emptyset \subset S \subset V\), if \(\hat y_S \ne 0\), then \(\hat y_S = w_{e_{d_S}} - w_{e_{c_S}}\) and \(d_S < \infty\). By the definitions of \(c_S\) and \(d_S\), \(c_S < d_S\), so \(w_{e_{c_S}} \le w_{e_{d_S}}\), that is, \(w_{e_{d_S}} - w_{e_{c_S}} \ge 0\). This proves that all components of \(\hat y\) are non-negative.

Next consider any edge \((u,v) \in E\). Let \(\mathcal{S}\) be the set of all subsets \(S \subseteq V\) such that \(|S| \ge 2\) and \(S\) is the vertex set of a connected component of some graph \(G_i\), and let \(\mathcal{S}_{u,v} = \{ S \in \mathcal{S} \mid u, v \in S \}\). We have \(\hat y_S = 0\) for all \(S \notin \mathcal{S}\) (because \(d_S = \infty\) for any such set). Thus,

\[\hat y_0 - \sum_{\substack{S \subseteq V\\u, v \in S}} \hat y_S = \hat y_0 - \sum_{S \in \mathcal{S}_{u,v}} \hat y_S.\]

Let \(\mathcal{S}_{u,v} = \{ S_1, \ldots, S_k \}\) such that \(S_1 \subset \cdots \subset S_k = V\) and let \(f_i = e_{c_{S_i}}\) for all \(1 \le i \le k\). Then \(f_k = e_{c_V}\) and \(f_i = e_{d_{S_{i-1}}}\) for all \(1 < i < k\). Thus,

\[\begin{aligned} \sum_{i=1}^k \hat y_{S_i} &= \sum_{i=1}^{k-1} \hat y_{S_i} + \hat y_V\\ &= \sum_{i=1}^{k-1} \left(w_{e_{d_{S_i}}} - w_{e_{c_{S_i}}}\right) + \hat y_V\\ &= \sum_{i=1}^{k-1} \left(w_{f_{i+1}} - w_{f_i}\right) + \hat y_V\\ &= w_{f_k} - w_{f_1} + \hat y_V\\ \hat y_0 - \sum_{i=1}^k \hat y_{S_i} &= (\hat y_0 - \hat y_V) + w_{f_1} - w_{f_k}\\ &= w_{f_k} + w_{f_1} - w_{f_k}\\ &= w_{f_1}. \end{aligned}\]

Now let \(i\) be the index such that \(e_i = (u, v)\).

If \((u, v) \in T\), then \(c_{S_1} = i\) and \(f_1 = (u, v)\), so \(\hat y_0 - \sum_{i=1}^k \hat y_{S_i} = w_{u,v}\).

If \((u, v) \notin T\), then \(c_{S_1} < i\) because \(G_i\) has a connected component that includes both \(u\) and \(v\). Thus, \(w_{f_1} \le w_{e_i} = w_{u, v}\), that is, \(\hat y_0 - \sum_{i=1}^k \hat y_{S_i} \le w_{u,v}\).

In both cases, \(\hat y\) satisfies the constraint in (4.16) corresponding to the edge \((u, v)\). Since this argument holds for every edge \((u, v) \in E\), this shows that \(\hat y\) is a feasible solution of (4.16).

It remains to prove that \(\hat x\) and \(\hat y\) are optimal solutions of (4.15) and (4.16), respectively. To this end, it suffices to prove that they satisfy complementary slackness.

As just observed, if \((u, v) \in T\), that is, if \(\hat x_{u,v} \ne 0\), then \(\hat y_0 - \sum_{i=1}^k \hat y_{S_i} = w_{u,v}\). Thus, \(\hat x\) and \(\hat y\) satisfy primal complementary slackness.

Next consider dual complementary slackness. Since \(\hat x\) is a feasible solution of (4.15), we have \(\sum_{e \in E} \hat x_e \ge n - 1\) and \(\sum_{e \in E} \hat x_e \le n - 1\), that is, \(\sum_{e \in E} \hat x_e = n - 1\) and the primal constraints corresponding to both \(y_0\) and \(y_V\) are tight.

If \(\hat y_S \ne 0\) for some \(\emptyset \subset S \subset V\), then \(S\) is a connected component of some graph \(G_i\) and thus of \(T_i\) (because otherwise, \(d_S = \infty\) and, thus, \(\hat y_S = 0\)).

Since every connected graph on \(|S|\) vertices—\(T_i\) in this case—has at least \(|S| - 1\) edges this shows that

\[\sum_{\substack{(u, v) \in E\\u, v \in S}} \hat x_{u,v} \ge |S| - 1.\]

Since \(\hat x\) is a feasible solution of (4.15), we also have

\[\sum_{\substack{(u, v) \in E\\u, v \in S}} \hat x_{u,v} \le |S| - 1.\]

Thus,

\[\sum_{\substack{(u, v) \in E\\u, v \in S}} \hat x_{u,v} = |S| - 1,\]

and the primal constraint corresponding to \(y_S\) is tight. Thus, \(\hat x\) and \(\hat y\) satisfy dual complementary slackness.

Since \(\hat x\) and \(\hat y\) satisfy both primal and dual complementary slackness, Theorem 4.5 shows that they are optimal solutions of (4.15) and (4.16), respectively. ▨