13.1.2. Multiway Vertex Cut*

In the multiway cut problem, we are given a graph \(G\) and a set of terminals \(T\) we want to break it up into subgraphs, by removing vertices or edges, so that each subgraph contains at most one terminal in \(T\). The removed vertices or edges form the "cut" and have the properties that they separate the terminals from each other. In the multiway vertex cut problem, we aim to partition the graph by removing vertices. This is the problem we study in this section. In Section 13.2.3, we study an approximation algorithm based on randomized rounding for the multiway edge cut problem, where we want to partition the graph by removing edges. Formally, these two problems are defined as follows:

Multiway Vertex Cut Problem: Given a graph \(G = (V, E)\), a set of terminals \(T\), and a weight function \(w : V \rightarrow \mathbb{R}^+\), find a subset of vertices \(C \subseteq V \setminus T\) such that no connected component of \(G - C\) contains more than one vertex from \(T\) and such that \(C\) has minimum weight \(w(C) = \sum_{v \in C}w_v\) among all such subsets of \(V\).

Multiway Edge Cut Problem: Given a graph \(G = (V, E)\), a set of terminals \(T\), and a weight function \(w : E \rightarrow \mathbb{R}^+\), find a subset of edges \(C \subseteq E\) such that no connected component of \(G - C\) contains more than one vertex from \(T\) and such that \(C\) has minimum weight \(w(C) = \sum_{e \in C}w_e\) among all such subsets of \(E\).

Note that a multiway vertex cut \(C\) exists only if no two terminals in \(T\) are adjacent. We assume that this condition is satisfied for the remainder of this section. A multiway edge cut always exists because we can simply remove all edges from \(G\).

While we were able to prove that any extreme point solution of the LP relaxation of the vertex cover problem is half-integral, the same is not true for the multiway vertex cut problem. However, we are able to show that the LP relaxation of the multiway vertex cut problem has a half-integral optimal solution (which may not be an extreme-point solution) and that any optimal solution of the LP relaxation can be transformed into such a half-integral optimal solution in polynomial time. This is what we prove next. By rounding all variables in this half-integral solution up, we once again obtain a \(2\)-approximation of an optimal multiway vertex cut.

Let \(\mathcal{P}\) be the set of all paths in \(G\) between vertices in \(T\). Since each path in \(\mathcal{P}\) needs to contain a vertex in \(C\), the multiway vertex cut problem can be expressed as the following ILP:

\[\begin{gathered} \text{Minimize } \sum_{v \in V \setminus T} w_vx_v\\ \begin{aligned} \text{s.t. } \sum_{v \in P} x_v &\ge 1 && \forall P \in \mathcal{P}\\ x_v &\in \{0, 1\} && \forall v \in V \setminus T, \end{aligned} \end{gathered}\tag{13.3}\]

where \(x_v = 1\) indicates that \(x \in C\). The LP relaxation of this ILP is

\[\begin{gathered} \text{Minimize } \sum_{v \in V \setminus T} w_vx_v\\ \begin{aligned} \text{s.t. } \sum_{v \in P} x_v &\ge 1 && \forall P \in \mathcal{P}\\ x_v &\ge 0 && \forall v \in V \setminus T. \end{aligned} \end{gathered}\tag{13.4}\]

Consider an optimal solution \(\hat x\) of this LP. For each terminal \(t_i \in T\), we define its region \(R_i\) to be the set of vertices reachable from \(t_i\) via paths that do not include any vertex \(v \in V \setminus T\) with \(\hat x_v > 0\). Since every path \(P\) between two terminals \(t_i\) and \(t_j\) satisfies \(\sum_{v \in P} \hat x_v \ge 1\), each such region \(R_i\) contains only one vertex in \(T\), namely \(t_i\).

Let the boundary \(B_i\) of a region \(R_i\) be the set of vertices in \(V \setminus R_i\) adjacent to vertices in \(R_i\). Let \(Q_1\) be the set of vertices in \(V \setminus T\) that belong to exactly one such boundary \(B_i\), and let \(Q_2\) be the set of vertices in \(V \setminus T\) that belong to at least two such boundaries. We construct a solution \(\tilde x\) by setting

\[\tilde x_v = \begin{cases} 1 & \text{if } v \in Q_2\\ \frac{1}{2} & \text{if } v \in Q_1\\ 0 & \text{otherwise}. \end{cases}\]

Clearly, this vector \(\tilde x\) is half-integral. Next we show that it is an optimal solution of (13.4). First we prove feasibility.

Lemma 13.2: The vector \(\tilde x\) is a feasible solution of (13.4).

Proof: Consider any path \(P \in \mathcal{P}\) with endpoints \(t_i\) and \(t_j\). Since \(t_i \in R_i\), \(t_j \in R_j\), and \(R_i \cap R_j = \emptyset\), \(P\) contains a vertex \(u \in B_i\) and a vertex \(v \in B_j\). If \(u \ne v\), then observe that \(u, v \in Q_1 \cup Q_2\), so

\[\sum_{w \in P} \tilde x_w \ge \tilde x_u + \tilde x_v \ge \frac{1}{2} + \frac{1}{2} = 1.\]

If \(u = v\), then \(u \in B_i \cap B_j \subseteq Q_2\) and, thus, \(\tilde x_u = 1\). Therefore,

\[\sum_{w \in P} \tilde x_w \ge \tilde x_u = 1.\ \text{▨}\]

To prove that \(\tilde x\) is an optimal solution of (13.4), we use the dual of (13.4) and the corresponding complementary slackness conditions. The dual of (13.4) is

\[\begin{gathered} \text{Maximize } \sum_{P \in \mathcal{P}} y_P\\ \begin{aligned} \text{s.t. } \sum_{v \in P} y_P &\le w_v && \forall v \in V \setminus T\\ y_P &\ge 0 && \forall P \in \mathcal{P}. \end{aligned} \end{gathered}\tag{13.5}\]

Let \(\hat y\) be an optimal solution of (13.5). As optimal solutions of their respective LPs, \(\hat y\) and the optimal solution \(\hat x\) of (13.4) above satisfy the following complementary slackness conditions:

• Primal complementary slackness: For every vertex \(v \in V \setminus T\),

  \[\hat x_v = 0 \text{ or } \sum_{v \in P} \hat y_P = w_v.\]

• Dual complementary slackness: For every path \(P \in \mathcal{P}\),

  \[\hat y_P = 0 \text{ or } \sum_{v \in P} \hat x_v = 1.\]

We use these complementary slackness conditions to derive statements about the structure of the optimal solution \(\hat x\) of (13.4) that help us prove that the half-integral solution \(\tilde x\) is also optimal. We start with the following simple observation, which does not require complementary slackness to prove.

Observation 13.3: Every vertex \(v \in Q_2\) satisfies \(\hat x_v \ge 1\).

Proof: Since \(v \in Q_2\), there exist two boundaries \(B_i\) and \(B_j\) such that \(v \in B_i \cap B_j\). Since \(v \in B_i\), there exists a path \(P_1\) from \(t_i\) to \(v\) that contains no vertices \(w \ne v\) in \(V \setminus T\) such that \(\hat x_w > 0\). Since \(v \in B_j\), there exists a path \(P_2\) from \(v\) to \(t_j\) that contains no vertices \(w \ne v\) in \(V \setminus T\) such that \(\hat x_w > 0\). Thus, \(P = P_1 \circ P_2\) is a path in \(\mathcal{P}\) and \(\hat x_v = \sum_{w \in P} \hat x_w \ge 1\). ▨

Using this observation and complementary slackness, we can now prove that every path \(P \in \mathcal{P}\) with \(\hat y_P > 0\) has only limited interactions with the boundaries of the different regions:

Lemma 13.4: Every path \(P \in \mathcal{P}\) with \(\hat y_P > 0\) either contains exactly one vertex in \(Q_2\) and no vertices in \(Q_1\) or exactly two vertices in \(Q_1\) and no vertex in \(Q_2\).

Proof: Every path \(P \in \mathcal{P}\) contains at least one vertex in \(Q_1 \cup Q_2\). Thus, we only need to prove that \(P \cap Q_2 \ne \emptyset\) implies that \(|P \cap (Q_1 \cup Q_2)| = 1\) and that \(P \cap Q_2 = \emptyset\) implies that \(|P \cap (Q_1 \cup Q_2)| = 2\), provided that \(\hat y_P > 0\).

Since \(\hat y_P > 0\), dual complementary slackness states that \(\sum_{v \in P} \hat x_v = 1\). Since every vertex \(v \in Q_1 \cup Q_2\) satisfies \(\hat x_v > 0\) and every vertex \(v \in Q_2\) satisfies \(\hat x_v \ge 1\), by Observation 13.3, this immediately implies that \(P \cap (Q_1 \cup Q_2) = \{v\}\) if \(P\) contains a vertex \(v \in Q_2\).

If \(P \cap Q_2 = \emptyset\), then \(P\) contains two vertices \(u \in B_i\) and \(w \in B_j\), where \(t_i\) and \(t_j\) are the endpoints of \(P\). Since \(P \cap Q_2 = \emptyset\), we have \(u, w \in Q_1\), so \(u \notin B_j\) and \(w \notin B_i\). Thus, \(u \ne w\) and \(|P \cap (Q_1 \cup Q_2)| \ge 2\).

Now assume for the sake of contradiction that \(|P \cap (Q_1 \cup Q_2)| > 2\), that is, that there exists a third vertex \(v \notin \{u, w\}\) in \(P \cap Q_1\). We have \(v \in B_h\), for some \(1 \le h \le k\). (It is possible that \(h \in \{i, j\}\).) Since \(t_i \ne t_j\), we must have \(t_h \ne t_i\) or \(t_h \ne t_j\), possibly both. Assume w.l.o.g. that \(t_h \ne t_i\). Then let \(P_1\) be the subpath of \(P\) from \(t_i\) to \(v\) and let \(P_2\) be any path from \(v\) to \(t_h\) that contains no vertex \(z\) with \(\hat x_z > 0\) other than \(v\). This path \(P_2\) exists because \(v \in B_h\). The concatenation of \(P_1\) and \(P_2\) is a walk from \(t_i\) to \(t_h\).¹ By removing loops between multiple visits to the same vertex from this walk, we obtain a path \(P' \in \mathcal{P}\) from \(t_i\) to \(t_h\). The vertices \(z \in P'\) with \(\hat x_z > 0\) are a proper subset of the vertices \(z \in P\) with \(\hat x_z > 0\) because

• \(P'\) visits only vertices in \(P \cup P_2\),
• \(P_2\) contains no vertex \(z\) with \(\hat x_z > 0\) and \(z \notin P\), and
• \(\hat x_w > 0\), \(w \in P\), but \(w \notin P'\).

Thus,

\[\sum_{z \in P'} \hat x_z < \sum_{z \in P} \hat x_z = 1\]

and \(\hat x\) is not a feasible solution of (13.4), a contradiction. ▨

We are now ready to prove that the half-integral solution \(\tilde x\) we constructed above is an optimal solution of (13.4).

Lemma 13.5: The vector \(\tilde x\) is an optimal solution of (13.4).

Proof: Since \(\tilde x\) is a feasible solution of (13.4), by Lemma 13.2, and \(\hat y\) is a feasible solution of its dual, \(\tilde x\) is an optimal solution of (13.4) if \(\tilde x\) and \(\hat y\) have the same objective function value, by Theorem 4.3. Thus, we need to prove that

\[\sum_{v \in V} w_v \tilde x_v = \sum_{P \in \mathcal{P}} \hat y_P.\]

Let \(\mathcal{P}'\) be the subset of paths \(P \in \mathcal{P}\) such that \(\hat y_P > 0\). By Lemma 13.4, every path in \(\mathcal{P}'\) contains either a single vertex in \(Q_2\) or two vertices in \(Q_1\), and no other vertices in \(Q_1 \cup Q_2\). Thus, we can partition \(\mathcal{P}'\) into two subsets \(\mathcal{P}_1'\) and \(\mathcal{P}_2'\) such that every path in \(\mathcal{P}_1'\) contains two vertices in \(Q_1\) and every path in \(\mathcal{P}_2'\) contains a single vertex in \(Q_2\).

By primal complementary slackness, every vertex in \(v \in Q_1 \cup Q_2\) satisfies \(\sum_{v \in P} \hat y_P = w_v\) because \(\hat x_v > 0\) for all \(v \in Q_1 \cup Q_2\). Thus,

\[\sum_{v \in Q_1} w_v = \sum_{v \in Q_1} \sum_{v \in P} \hat y_P\]

and

\[\sum_{v \in Q_2} w_v = \sum_{v \in Q_2} \sum_{v \in P} \hat y_P.\]

Evey path \(P \in \mathcal{P}'\) that contains a vertex in \(Q_2\) belongs to \(\mathcal{P}_2'\) and contains exactly one such vertex. Thus, every dual value \(\hat y_P\) with \(P \in \mathcal{P}_2'\) occurs exactly once in the sum \(\sum_{v \in Q_2} \sum_{v \in P} \hat y_P\), that is,

\[\sum_{v \in Q_2} w_v = \sum_{v \in Q_2} \sum_{\ v \in P} \hat y_P = \sum_{P \in \mathcal{P}_2'} \hat y_P.\]

Similarly, every path \(P \in \mathcal{P}'\) that contains a vertex in \(Q_1\) belongs to \(\mathcal{P}_1'\) and contains exactly two vertices in \(Q_1\). Thus, every dual value \(\hat y_P\) with \(P \in \mathcal{P}_1'\) occurs exactly twice in the sum \(\sum_{v \in Q_1} \sum_{v \in P} \hat y_P\), that is,

\[\sum_{v \in Q_1} w_v = \sum_{v \in Q_1} \sum_{v \in P} \hat y_P = 2 \sum_{P \in \mathcal{P}_1'} \hat y_P.\]

This shows that

\[\begin{aligned} \sum_{P \in \mathcal{P}} \hat y_P &= \sum_{P \in \mathcal{P}'} \hat y_P\\ &= \sum_{P \in \mathcal{P}_1'} \hat y_P + \sum_{P \in \mathcal{P}_2'} \hat y_P\\ &= \sum_{v \in Q_1} \frac{w_v}{2} + \sum_{v \in Q_2} w_v\\ &= \sum_{v \in Q_1 \cup Q_2} w_v \tilde x_v\\ &= \sum_{v \in V \setminus T} w_v \tilde x_v. \end{aligned}\]

The first equality holds because \(\hat y_P = 0\) for all \(P \in \mathcal{P} \setminus \mathcal{P}'\). Similarly, the last equality holds because \(\tilde x_v = 0\) for all \(v \in (V \setminus T) \setminus (Q_1 \cup Q_2)\). ▨

Our algorithm for the multiway vertex cut problem does not construct the half-integral solution \(\tilde x\): Given the fractional solution \(\hat x\), it computes the regions \(R_1, \ldots, R_k\) and their boundaries \(B_1, \ldots, B_k\) and returns \(C = B_1 \cup \cdots \cup B_k\). This clearly takes polynomial time.

This construction of \(C\) is equivalent to computing \(\tilde x\) and defining an integral solution \(\breve x\) as

\[\breve x_v = \begin{cases} 1 & \text{if } \tilde x > 0\\ 0 & \text{if } \tilde x = 0. \end{cases}\]

Since \(\tilde x_v \ge \frac{1}{2}\) whenever \(\breve x_v = 1\), we have \(\breve x_v \le 2 \tilde x_v\) for all \(v \in V \setminus T\). Thus,

\[w(C) = \sum_{v \in V \setminus T} w_v \breve x_v \le 2 \cdot \sum_{v \in V \setminus T} w_v \tilde x_v = 2 \cdot \mathrm{OPT}_f \le 2 \cdot \mathrm{OPT},\]

that is, \(C\) is a \(2\)-approximation of an optimal multiway vertex cut.