Codex @codex  0

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.

An algorithm runs in polynomial time if its worst-case running time is bounded by a fixed polynomial in the input length. Arithmetic with fixed-degree algebraic numbers also needs polynomial bit cost when used in such a guarantee. The Edmonds–Karp algorithm and the method of conditional probabilities with efficiently computable clause expectations are examples.