135 Graph Theory — Karger Min Cut Trace
135.1 Overview
This chapter documents the algorithmic trace layer for Karger’s contraction algorithm: adaptive contraction runs of a multigraph together with a distinguished cut carried along the contractions, a finite edge-occurrence sampling model, and the resulting survival probability lower bound \(2/(n(n-1))\) for a fixed min-cut. It builds on the local contraction facts (cut size preservation, min-cut preservation, degree and handshaking bounds) proved for multigraphs elsewhere, and packages them both recursively and as a telescoping product along an indexed trace.
135.2 Declarations
A state consists of a multigraph \(G\) over \(\alpha \) together with a distinguished cut \(C\) of \(G\). It records the current graph of the algorithm and the cut whose survival is being tracked.
Given a state \(s\), an edge \(e\) of \(s.G\) that does not cross the distinguished cut \(s.C\), the contracted state has graph \(s.G\) contracted along \(e\) and cut the corresponding contracted cut.
The relation asserting that state \(t\) arises from state \(s\) by contracting some edge \(e\) of \(s.G\) that does not cross the distinguished cut of \(s\).
The inductively defined relation of \(n\) consecutive surviving steps leading from a state \(s\) to a state \(t\): the empty run has \(n = 0\) and \(t = s\), and a run of length \(n+1\) is a run of length \(n\) followed by one surviving step.
If \(e\) is an edge of a multigraph \(G\), then \(G\) has positive edge count.
If \(t\) is obtained from \(s\) by a surviving step, then the distinguished cuts have the same size: \(t.C.\mathrm{size} = s.C.\mathrm{size}\).
If \(t\) is obtained from \(s\) by a surviving step and \(s.C\) is a min-cut of \(s.G\), then \(t.C\) is a min-cut of \(t.G\).
If \(t\) is obtained from \(s\) by a surviving step, then \(t.G\) has exactly one vertex fewer than \(s.G\).
If some state \(t\) is reachable from \(s\) by a surviving step, then \(s.G\) has positive edge count.
If \(t\) is reachable from \(s\) by a surviving run of any length, then \(t.C.\mathrm{size} = s.C.\mathrm{size}\).
If \(t\) is reachable from \(s\) by a surviving run and \(s.C\) is a min-cut, then \(t.C\) is a min-cut.
If \(t\) is reachable from \(s\) by a surviving run of \(n\) steps, then \(t.G.\mathrm{vertexCount} = s.G.\mathrm{vertexCount} - n\) (truncated subtraction on \(\mathbb {N}\)).
If \(t\) is reachable from \(s\) by a surviving run and \(s.C\) is a min-cut, then the graph reached after the run still satisfies the handshaking lower bound
The same invariant, with the vertex count after \(n\) contractions written explicitly: for a surviving run of \(n\) steps from \(s\) to \(t\) with \(s.C\) a min-cut,
For naturals \(c, n, m\) with \(2 \le n\), \(0 \lt m\) and \(c\, n \le 2m\), the survival probability \(1 - c/m\) satisfies
If a surviving step is possible from \(s\), the distinguished cut \(s.C\) is a min-cut, and \(s.G\) has at least two vertices, then writing \(n = s.G.\mathrm{vertexCount}\),
If \(t\) is reached from \(s\) by a surviving run of \(i\) steps, a further surviving step is possible from \(t\), \(s.C\) is a min-cut, and \(t.G\) has at least two vertices, then with \(n_t = t.G.\mathrm{vertexCount}\),
The sub-multiset of edges of \(s.G\) that do not cross the distinguished cut \(s.C\); these are exactly the edge choices that keep the cut alive.
The cardinality (with multiplicity) of the multiset of non-crossing edges of a state.
The real number obtained as the number of non-crossing edge choices divided by the total edge count of \(s.G\), i.e. the probability that a uniformly chosen edge occurrence does not cross the cut.
For every state \(s\), the number of non-crossing edge choices equals \(s.G.\mathrm{edgeCount} - s.C.\mathrm{size}\).
For every state \(s\), \(s.C.\mathrm{size} \le s.G.\mathrm{edgeCount}\).
If \(s.G\) has at least one edge, the uniform survival probability of \(s\) equals \(\mathrm{survivalProb}(s.C.\mathrm{size},\, s.G.\mathrm{edgeCount}) = 1 - c/m\) with \(c = s.C.\mathrm{size}\) and \(m = s.G.\mathrm{edgeCount}\).
The finite set of pairs (edge, occurrence index) obtained from the edge multiset of \(s.G\); the second coordinate distinguishes parallel copies of the same edge, so that a uniform choice on this set is a uniform choice of an edge occurrence.
The predicate on an edge occurrence saying that its underlying edge does not cross the distinguished cut of \(s\).
The occurrence sample space of a state has cardinality \(s.G.\mathrm{edgeCount}\).
For a multiset \(m\) and a decidable predicate \(p\), the number of enumerated occurrences of \(m\) whose first coordinate satisfies \(p\) equals the cardinality of the sub-multiset of \(m\) filtered by \(p\).
The number of surviving edge occurrences of a state equals its number of non-crossing edge choices.
The ratio of the number of surviving edge occurrences to the total number of edge occurrences, i.e. the concrete one-step survival probability of the finite sampling model.
For every state, the occurrence-space survival ratio coincides with the uniform survival probability.
The first projection of any element of the occurrence sample space of \(s\) is an edge of \(s.G\).
If an edge occurrence of \(s\) survives, then its underlying edge is not a crossing edge of the distinguished cut \(s.C\).
Given a state \(s\) and a sampled edge occurrence that does not cross the distinguished cut, this is the state obtained by contracting \(s\) along the underlying edge.
For any surviving edge occurrence at \(s\), the pair consisting of \(s\) and the resulting successor state is a surviving step.
The finite probability that the distinguished cut survives the next given number of random edge-occurrence choices, defined by recursion on the number of steps: zero steps have probability \(1\), and one further step averages over all edge occurrences, contributing \(0\) for occurrences that cross the cut and the recursive value at the contracted state otherwise.
With no remaining contractions the survival probability is \(1\).
The unfolding equation: the survival probability for \(\text{steps}+1\) contractions at \(s\) is the average over all edge occurrences of \(s\) of the survival probability for \(\text{steps}\) contractions at the contracted state, with crossing occurrences contributing \(0\).
Counting surviving occurrences in the attached (subtype) version of the sample space gives the same number as counting them in the sample space itself.
Let \(S\) be a finite set, \(p\) a decidable predicate, \(f : S \to \mathbb {R}\) and \(B \in \mathbb {R}\) with \(B \le f(x)\) for every \(x \in S\) satisfying \(p\). Then
where terms failing \(p\) contribute \(0\).
If the occurrence sample space of \(s\) is nonempty and every surviving branch has recursive survival probability at least \(B\), then the averaged survival probability for one more step satisfies
If \(s.C\) is a min-cut of positive size and \(s.G\) has at least two vertices, then with \(n = s.G.\mathrm{vertexCount}\),
For every \(n\) and every state \(s\) whose distinguished cut is a min-cut of positive size, if \(2 \le n\) and \(s.G\) has exactly \(n\) vertices, then the recursive sampling model survives \(n-2\) contractions with probability at least
For a state \(s\) whose distinguished cut is a min-cut of positive size and whose graph has at least two vertices, writing \(n = s.G.\mathrm{vertexCount}\),
Human-facing form of the previous statement: a fixed min-cut of positive size in a graph with \(n \ge 2\) vertices survives the \(n-2\) random contractions with probability at least \(2/(n(n-1))\).
The finite set of edge occurrences of a multigraph \(G\), the same construction as the state-level sample space but without reference to a distinguished cut.
For every state \(s\), the graph-only occurrence space of \(s.G\) equals the occurrence space of \(s\).
The first projection of any element of the graph-only occurrence space of \(G\) is an edge of \(G\).
The multigraph obtained by contracting \(G\) along the edge underlying a sampled edge occurrence.
Contracting along any sampled edge occurrence decreases the vertex count by exactly one.
The graph of the successor state after a surviving occurrence equals the graph obtained by contracting \(s.G\) along the same occurrence viewed in the graph-only occurrence space.
The inductive relation asserting that \(H\) is reachable from \(G\) by a given number of successive arbitrary edge-occurrence contractions. It models the actual graph evolution of the algorithm without tracking any distinguished cut.
If \(H\) is reachable from \(G\) by a graph run of \(\text{steps}\) contractions, then \(H.\mathrm{vertexCount} = G.\mathrm{vertexCount} - \text{steps}\).
If \(G\) has at least two vertices and \(H\) is reachable from \(G\) by \(G.\mathrm{vertexCount} - 2\) contractions, then \(H\) has exactly two vertices.
Under the same hypotheses, the terminal graph \(H\) is a valid Karger output, i.e. a two-vertex multigraph.
If \(e\) is an edge of \(G\), then the occurrence \((e, 0)\) belongs to the graph-only occurrence space of \(G\).
If \(t\) arises from \(s\) by a surviving step, then there is an edge occurrence of \(s.G\) whose contraction produces exactly \(t.G\).
A surviving run of \(\text{steps}\) steps from \(s\) to \(t\) induces a graph-only Karger run of the same length from \(s.G\) to \(t.G\).
If \(s.G\) has at least two vertices and \(t\) is reached from \(s\) by a surviving run of \(s.G.\mathrm{vertexCount} - 2\) steps, then \(t.G\) is a Karger output.
An explicit indexed execution of the contraction loop: a family of graphs indexed by \(\mathbb {N}\), an edge occurrence of the graph at each index below \(\text{steps}\), and the requirement that the next graph is the contraction of the current one along that occurrence. The choice type depends on the current graph, matching the adaptive nature of the process.
For \(i \le \text{steps}\), the first \(i\) stages of an adaptive graph trace form a graph run from the initial graph to the graph at index \(i\).
For \(i \le \text{steps}\), the graph at index \(i\) of an adaptive trace has vertex count equal to the initial vertex count minus \(i\).
If \(2 \le n\) and an adaptive graph trace of \(n-2\) steps starts from a graph with \(n\) vertices, then its final graph is a Karger output.
Human-facing termination statement: every adaptive graph trace of \(n-2\) contractions starting from an \(n\)-vertex graph with \(n \ge 2\) ends with a two-vertex graph.
For a state \(s\) whose distinguished cut is a min-cut of positive size and whose graph has \(n = s.G.\mathrm{vertexCount} \ge 2\) vertices, both of the following hold: the recursive sampling model survives \(n-2\) contractions with probability at least \(2/(n(n-1))\), and every adaptive graph trace of \(n-2\) contractions starting from \(s.G\) ends with a Karger output.
Human-facing name for the previous conjunction: the survival lower bound \(2/(n(n-1))\) together with termination of every adaptive graph trace of \(n-2\) contractions.
A family of states indexed by \(\mathbb {N}\) such that consecutive states at indices below \(\text{steps}\) are related by a surviving step. This is the product-friendly counterpart of a surviving run: it exposes the state present at each index.
The adaptive graph trace obtained from an indexed surviving trace by forgetting the distinguished cuts and choosing, at each step, an occurrence realizing the surviving step.
For \(i \le \text{steps}\), the first \(i\) stages of an indexed surviving trace form a surviving run from the initial state to the state at index \(i\).
For \(i \le \text{steps}\), the graph at index \(i\) of a surviving trace has vertex count equal to the initial vertex count minus \(i\).
If the initial cut of an indexed surviving trace is a min-cut, \(i \lt \text{steps}\), and the graph at index \(i\) has at least two vertices, then with \(n_i\) its vertex count,
If the initial cut is a min-cut and every graph along the first \(\text{steps}\) indices has at least two vertices, then
where \(n_i\) is the vertex count at index \(i\).
If a surviving trace has \(\text{steps} = n-2\) and starts from a graph with \(n\) vertices, then
For an indexed surviving trace of \(n-2\) steps starting from an \(n\)-vertex graph with \(n \ge 2\), initial min-cut, and at least two vertices at every step,
The product over \(i \lt \text{steps}\) of the uniform one-step survival probabilities of the states of an indexed surviving trace.
The uniform survival product of a trace equals the product over \(i \lt \text{steps}\) of \(\mathrm{survivalProb}\) applied to the cut size and edge count at index \(i\).
The same product may be written using the initial cut size at every index, since cut size is invariant along a surviving trace.
Under the same hypotheses as the product-level bound, the product of the concrete uniform one-step survival probabilities along the trace is at least \(2/(n(n-1))\).
The product over \(i \lt \text{steps}\) of the finite sample-space survival ratios of the states of an indexed surviving trace.
For every indexed surviving trace, the product of occurrence-space survival ratios equals the product of uniform survival probabilities.
For an indexed surviving trace of \(n-2\) steps starting from an \(n\)-vertex graph with \(n \ge 2\), initial min-cut, and at least two vertices at every step, the product of the finite uniform edge-choice survival ratios is at least \(2/(n(n-1))\).