Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 37 / 3

Use safety for failure counts within the available components, equivalently tolerance of up to that many failures. An exact-count condition with more failures than components would otherwise be vacuous. Assume the client is not itself a server; that exceptional case needs no network connection.

Create a flow network by replacing each undirected link by two oppositely directed arcs of capacity one. Add a new sink $z$ and arcs from every server to $z$, each of capacity $B=|E|+1$. Find a maximum flow from $c$ to $z$ with the Edmonds–Karp algorithm. By the max-flow min-cut theorem, its value $\lambda$ is the minimum cut capacity. A cut using a server-to-sink arc costs at least $B$, whereas cutting all original links costs at most $|E|$, so a minimum cut uses none of the added arcs.

A source-side cut therefore contains no server. Each original undirected edge crossing it contributes exactly one of its two arcs, so its capacity is the number of original links separating the client from every server. Conversely, if a set of failed links disconnects all servers, the vertices still reachable from $c$ define a cut contained in that failed set. Thus $\lambda$ is exactly the minimum number of links whose failure can disconnect the client from all servers. This is server connectivity under component failures.

Deleting fewer than $\lambda$ links leaves some connection, while deleting a minimum cut destroys every connection. ThereforeIf $\lambda =0$, the network is already disconnected and has no nonnegative safe failure count. The transformed graph has $|V|+1$ vertices and $2|E|+|S|$ arcs. The Edmonds–Karp algorithm runs in $O(|V^{\prime }||E^{\prime }{|}^2)$ steps, so both the construction and computation are polynomial in the original graph size.

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.

Name the outer pentagon vertices, in order from the client clockwise, $c,T,R,B,L$. Name the upper inner vertex $U$, the left inner vertex $A$, and the lower-right inner vertex $D$. The two remaining inner vertices are the labelled servers $s_1,s_2$.

Four edge-disjoint server paths areEach uses different links, although some intermediary vertices are shared. Any three failed links therefore leave at least one path intact. The client has exactly four incident links; failing those four disconnects it. Thus the minimum link cut has size four, givingFor mixed failures use the three paths $c-A-s_1$, $c-U-s_2$ and $c-T-R-B-D-s_1$. Their internal vertices are disjoint, as are their links. One failed link or intermediary node can destroy at most one of these paths, so any two failures leave a path intact. Failing the three intermediary nodes $A,U,D$ disconnects both servers: $s_1$ has neighbors $A,D$, and $s_2$ has neighbors $U,D$. ThereforeThe two certificates distinguish edge-disjoint paths from internally vertex-disjoint paths, exactly the distinction needed between the two failure models.