Translating Split-Graph Cuts into Vertex Separators

Why Split-Graph Cuts Need Careful Capacities

Vertex splitting turns the question of how many internally disjoint paths can join two terminals into a question about cuts in a directed network. The intended cut should pay one unit for each nonterminal vertex it separates through. But the network also contains arcs representing the original graph’s edges. If one of those arcs crosses the cut, its capacity must be large enough that the cut cannot be mistaken for a small vertex separator.

We make this correspondence precise. Throughout, \(G=(V,E)\) is a finite simple undirected graph, and \(s,t\in V\) are distinct, nonadjacent terminals. A set \(S\subseteq V\setminus\{s,t\}\) is an \(s\)-\(t\) vertex separator if \(G-S\) contains no \(s\)-\(t\) path. The nonadjacency assumption ensures that removing all vertices other than \(s,t\) separates them, so a separator exists.

Definition: The vertex-split network for \(G,s,t\) is a directed network constructed as follows. Keep each terminal as a single node, still called \(s\) or \(t\). Replace each other vertex \(v\) by two nodes \(v^-\) and \(v^+\), and add the directed arc \(v^-\to v^+\) with capacity \(1\). For every original edge \(uv\), add the directed arcs \(u^+\to v^-\) and \(v^+\to u^-\), each with capacity \(M\). In these arcs, a terminal’s minus and plus copies both mean its single node: \(s^-=s^+=s\), and \(t^-=t^+=t\).

The number \(M\) is a positive capacity assigned to every arc representing an original edge. The arcs \(v^-\to v^+\) represent the use of a nonterminal vertex; their unit capacity is what makes a cut through such an arc count that vertex once. The network is directed, even though the original graph is undirected: an original edge gives one network arc in each direction, and a cut’s capacity counts only arcs directed from its source side to its other side.

Definition: An \(s\)-\(t\) cut is a set \(A\) of network nodes with \(s\in A\) and \(t\notin A\). Its capacity is the sum of the capacities of all directed arcs whose tail is in \(A\) and whose head is outside \(A\).

When a Cut Must Be a Vertex Separator

Proposition: If an \(s\)-\(t\) cut has capacity less than \(M\), then the set of nonterminals whose split arcs leave the cut’s source side is an \(s\)-\(t\) vertex separator. Its size equals the cut’s capacity.

Proof. Let \(A\) be an \(s\)-\(t\) cut of capacity less than \(M\). Define \(S=\{v\in V\setminus\{s,t\}: v^-\in A,\ v^+\notin A\}\). No original-edge arc can leave \(A\): if one did, it alone would contribute \(M\), contradicting that the total cut capacity is less than \(M\). Thus every arc leaving \(A\) is a unit-capacity split arc. Exactly the vertices in \(S\) have such an arc leaving, so the cut capacity is \(|S|\).

It remains to show that \(S\) separates \(s\) from \(t\). Suppose instead that \(G-S\) contains an \(s\)-\(t\) path. Following that path in order gives a directed path in the split network: each original edge is followed by its corresponding directed arc, and each internal vertex \(v\) is traversed by the split arc \(v^-\to v^+\). The network path begins at \(s\in A\) and ends at \(t\notin A\), so it must use an arc leaving \(A\). It cannot use an original-edge arc leaving \(A\), because none exists. It cannot use a split arc leaving \(A\) either: every such arc belongs to a vertex in \(S\), whereas the path avoids \(S\). This contradiction proves that \(S\) is a separator. \(\square\)

The strict inequality matters: a cut of capacity \(M\) might cross an original-edge arc, so the proposition gives no separator conclusion for such a cut. To use the proposition for a minimum cut, we will choose \(M\) larger than the size of a known separator.

Constructing a Cut from a Separator

Proposition: If \(S\) is an \(s\)-\(t\) vertex separator, then the split network has an \(s\)-\(t\) cut of capacity \(|S|\), with no original-edge arc leaving the cut.

Proof. Let \(R\) be the set of vertices reachable from \(s\) in \(G-S\), including \(s\). Since \(S\) separates \(s\) and \(t\), \(t\notin R\). Define the network source side \(A\) by putting \(s\) and both copies \(v^-,v^+\) in \(A\) for every \(v\in R\setminus\{s\}\). For each \(v\in S\), put \(v^-\) in \(A\) and leave \(v^+\) outside. Put both copies of every vertex in \(V\setminus(R\cup S\cup\{t\})\) outside \(A\), and leave \(t\) outside. Thus \(s\in A\) and \(t\notin A\).

A split arc leaves \(A\) exactly when it is \(v^-\to v^+\) for some \(v\in S\). Now consider an original-edge arc leaving \(A\), say \(u^+\to v^-\). Its tail can be in \(A\) only if \(u\in R\): copies \(u^+\) for \(u\in S\) and for vertices outside \(R\cup S\) are outside \(A\). Its head can be outside \(A\) only if \(v\notin R\cup S\) or \(v=t\), since the minus copies of vertices in \(S\) and \(R\) are in \(A\). But an edge from \(u\in R\) to such a vertex \(v\) would make \(v\) reachable from \(s\) in \(G-S\); this would put \(v\) in \(R\), including if \(v=t\). That is a contradiction. Therefore no original-edge arc leaves \(A\). The only arcs leaving are the \(|S|\) unit-capacity split arcs, so the cut capacity is \(|S|\). \(\square\)

Theorem: If \(s,t\) are distinct and nonadjacent and \(M=n=|V|\), the minimum \(s\)-\(t\) cut capacity in the vertex-split network equals the minimum size of an \(s\)-\(t\) vertex separator in \(G\).

Proof. Removing all \(n-2\) nonterminals separates \(s\) and \(t\), because they are nonadjacent. By the construction just proved, there is a cut of capacity \(n-2\). Hence a minimum cut has capacity at most \(n-2\), which is less than \(M=n\). The first proposition therefore converts a minimum cut into a separator of exactly the same size. Conversely, applying the second proposition to a minimum-size separator produces a cut of that size, so the minimum cut cannot be larger than the minimum separator. Together, these inequalities give equality. \(\square\)

Worked Examples

Worked Example: A Single Vertex Separates the Terminals

Let \(G=(V,E)\) have \(V=\{s,a,b,c,t\}\) and \(E=\{sa,ab,sc,cb,bt\}\). Choose \(M=n=5\). The two routes from \(s\) toward \(t\) meet at \(b\), and \(b\) is the only neighbor of \(t\), so \(S=\{b\}\) separates \(s\) and \(t\).

After deleting \(b\), the vertices reachable from \(s\) are \(R=\{s,a,c\}\). The cut constructed from \(S\) has source side \(A=\{s,a^-,a^+,c^-,c^+,b^-\}\); the nodes \(b^+\) and \(t\) are outside. Its split arcs leaving \(A\) consist of \(b^-\to b^+\), with capacity \(1\).

Check the original-edge arcs. For \(sa\), the arc \(s\to a^-\) stays inside \(A\), and \(a^+\to s\) also stays inside. The arcs for \(sc\) likewise stay inside. For \(ab\) and \(cb\), arcs from \(a^+\) or \(c^+\) to \(b^-\) stay inside, while the reverse-direction arcs have tails \(b^+\) outside. For \(bt\), the arc with tail \(b^+\) is outside, and the arc \(t\to b^-\) enters \(A\), so neither leaves it. Thus the cut capacity is exactly \(1=|S|\).

Check: every \(s\)-\(t\) path must use the edge \(bt\), so it must visit \(b\). The set \(\{b\}\) is therefore a separator, and the displayed cut crosses only its unit split arc.

Worked Example: Two Separate Internal Vertices Are Needed

Let \(V=\{s,a,b,t\}\) and \(E=\{sa,at,sb,bt\}\), with \(M=n=4\). The two \(s\)-\(t\) paths are \(s,a,t\) and \(s,b,t\). Removing \(S=\{a,b\}\) separates the terminals.

In \(G-S\), the only vertex reachable from \(s\) is \(s\), so \(R=\{s\}\). The construction gives \(A=\{s,a^-,b^-\}\). The split arcs \(a^-\to a^+\) and \(b^-\to b^+\) leave \(A\), contributing \(1+1=2\). Each original-edge arc leaving \(s\) has its head in \(A\), and arcs whose tails are \(a^+\) or \(b^+\) have tails outside \(A\). Hence no original-edge arc leaves, and the cut capacity is \(2=|S|\).

Check: a separator must contain \(a\), because the path \(s,a,t\) would otherwise remain, and it must contain \(b\), because \(s,b,t\) would otherwise remain. Thus every separator has size at least \(2\); the exhibited set has size \(2\), so it is minimum. The cut capacity agrees with this independent separator check.

Worked Example: A Cut Through an Original Edge Is Too Expensive

Let \(V=\{s,a,t\}\) and \(E=\{sa,at\}\), with \(M=n=3\). The split network has nodes \(s,a^-,a^+,t\). Its arcs are \(s\to a^-\) and \(a^+\to s\), each of capacity \(3\); \(a^+\to t\) and \(t\to a^+\), each of capacity \(3\); and \(a^-\to a^+\), of capacity \(1\).

For the cut \(A=\{s\}\), the only arc leaving \(A\) is \(s\to a^-\), so its capacity is \(3\). The reverse arc \(a^+\to s\) crosses the boundary in the other direction, but it does not leave \(A\), so it is not counted. By contrast, for \(A=\{s,a^-\}\), the only arc leaving \(A\) is the unit split arc \(a^-\to a^+\); this cut has capacity \(1\).

Check: the vertex \(a\) is the only nonterminal, and deleting it separates \(s\) from \(t\). The cut of capacity \(1\) records that separator. The cut of capacity \(3=M\) crosses an original-edge arc and is not a low-capacity cut to which the first proposition applies.

Choosing the Large Capacity and Avoiding a Common Error

The purpose of “large” is not to make an original-edge arc infinite. It is to choose a finite capacity strictly larger than the size of some available separator. With distinct nonadjacent terminals, \(V\setminus\{s,t\}\) is a separator of size \(n-2\), so \(M=n\) is a convenient choice. The minimum cut is then at most \(n-2\), while any cut using an original-edge arc has capacity at least \(M=n\). Therefore no minimum cut can use such an arc.

Common mistake: counting arcs that cross in either direction. Cut capacity is not the sum of all arcs whose endpoints lie on opposite sides. It counts only arcs directed from \(A\) to its complement. In the path example, for \(A=\{s\}\), the arcs \(s\to a^-\) and \(a^+\to s\) have capacity \(3\) and cross the boundary in opposite directions. The cut capacity is \(3\), not \(3+3=6\), because only \(s\to a^-\) leaves \(A\). Counting both directions would use the wrong definition and could invalidate the correspondence.

A second error is to infer a separator from an arbitrary cut without checking its capacity. A cut of capacity at least \(M\) may cross an original-edge arc, and its capacity need not equal the number of split arcs crossing it. The safe procedure is to establish a cut of capacity below \(M\), then identify its crossing split arcs. The two propositions explain why this procedure works in both directions: low cuts yield separators, and separators yield cuts of equal capacity.

This translation is the structural step that allows a path-packing question to be studied with cut methods. The capacities encode which objects are allowed to be “paid for”: unit cost for removing a nonterminal vertex, and a prohibitive cost for cutting through an original edge. The later proof of vertex Menger uses this encoding together with a flow argument; the correspondence itself does not require that argument.

Check Your Understanding

Use the definitions and propositions above to answer these questions.

Why must an \(s\)-\(t\) cut of capacity less than \(M\) contain no original-edge arc leaving its source side?
In the separator-to-cut construction, why are both copies of every vertex reachable in \(G-S\) placed in \(A\)?
For \(V=\{s,a,b,t\}\) and \(E=\{sa,ab,bt\}\), describe the cut obtained from the separator \(\{a\}\) when \(M=4\), and compute its capacity.
Explain why \(M=n\) is strictly larger than the size of \(V\setminus\{s,t\}\).
For a directed network cut, which arcs contribute to its capacity: all arcs crossing the partition, or only arcs leaving the source side?