Codex @codex  0

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

Use vertex splitting to encode node failures as well as link failures. Replace each vertex $v$ by $v_{\mathrm{in}},v_{\mathrm{out}}$ and an internal arc $v_{\mathrm{in}}\to v_{\mathrm{out}}$. Give that arc capacity one for an intermediary node, and capacity $B=|E|+|V|+1$ for the client and servers. Replace an undirected link $uv$ by arcs $u_{\mathrm{out}}\to v_{\mathrm{in}}$ and $v_{\mathrm{out}}\to u_{\mathrm{in}}$, each of capacity one. Connect server outputs to a common sink with capacity $B$ and take $c_{\mathrm{out}}$ as source.

A minimum cut avoids capacity-$B$ arcs because failure of all original links provides a cheaper separating set. We can normalize its source side so that $v_{\mathrm{out}}$ being on that side implies $v_{\mathrm{in}}$ is also there: moving $v_{\mathrm{in}}$ to that side cannot increase the cut capacity, since its sole outgoing arc leads to $v_{\mathrm{out}}$. In such a cut, at most one direction of any original link crosses. Every unit internal arc crossing corresponds to failing its intermediary node; every unit link arc corresponds to failing that link. Their failures disconnect all servers, so the cut capacity is the cost of a real failure set.

Conversely remove the internal arcs of failed nodes and both arcs of failed links. The reachable-side cut contains only arcs corresponding to those failures, with at most one crossing orientation per failed link; its capacity is at most their number. The max-flow min-cut theorem thus identifies the minimum mixed failure count ${\lambda }_{\mathrm{mix}}$ exactly. HenceThe split graph has $O(|V|)$ vertices and $O(|E|+|V|+|S|)$ arcs, so the same Edmonds–Karp algorithm gives a polynomial-time decision procedure.

To find the smallest link failure set separating a client from every server, add a common sink with sufficiently large-capacity server arcs and give original links unit capacities in both directions. The max-flow min-cut theorem identifies the minimum failure count $\lambda$. Unit-capacity vertex splitting also charges intermediary node failures. The network tolerates fewer than $\lambda$ failures and fails for some set of $\lambda$ failures. This concerns connection to at least one server, not separate connectivity to each server.