IMPROVED BOUNDS AND ALGORITHMS FOR GRAPH CUTS AND NETWORK
RELIABILITY1

arXiv:1602.08730v5 [cs.DS] 4 Aug 2017

DAVID G. HARRIS2 AND ARAVIND SRINIVASAN3

Abstract. Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation
scheme to estimate the probability that a graph G becomes disconnected, given that its edges are removed
independently with probability p. This algorithm runs in n5+o(1) ǫ−3 time to obtain an estimate within
relative error ǫ.
We improve this run-time through algorithmic and graph-theoretic advances. First, there is a certain
key sub-problem encountered by Karger, for which a generic estimation procedure is employed; we show
that this has a special structure for which a much more efficient algorithm can be used. Second, we show
better bounds on the number of edge cuts which are likely to fail. Here, Karger’s analysis uses a variety
of bounds for various graph parameters; we show that these bounds cannot be simultaneously tight. We
describe a new graph parameter, which simultaneously influences all the bounds used by Karger, and obtain
much tighter estimates of the cut structure of G. These techniques allow us to improve the runtime to
n3+o(1) ǫ−2 ; our results also rigorously prove certain experimental observations of Karger & Tai (Proc.
ACM-SIAM Symposium on Discrete Algorithms, 1997). Our rigorous proofs are motivated by certain nonrigorous differential-equation approximations which, however, provably track the worst-case trajectories of
the relevant parameters.
A key driver of Karger’s approach (and other cut-related results) is a bound on the number of small cuts:
we improve these estimates when the min-cut size is “small” and odd, augmenting, in part, a result of Bixby
(Bulletin of the AMS, 1974).
KEYWORDS: Graph reliability, graph cuts, contraction algorithm
AMS Classification: 05C31, 05C40, 05C85.

1. Introduction
Let G be a connected undirected multi-graph with vertex set V ; as usual, we let |V | = n. Unless stated
otherwise, the graphs we deal with will be multi-graphs with no self-loops, presented in adjacency-matrix format. We define R(p), the reliability polynomial of G, to be the probability that the graph remains connected
when edges are removed independently with probability p. One can verify that this is a polynomial in p. This
polynomial has various physical applications, for example determining the reliability of a computer network
or power grid. Although there is no currently known algorithm for estimating R(p), the complementary
probability U (p) = 1 − R(p), which we call the unreliability of the graph, can be estimated in polynomial
time. In a breakthrough paper ([8], see also [9]), Karger developed the first fully-polynomial randomized
approximation scheme (FPRAS) to estimate U (p) up to relative error ǫ in time polynomial in n and 1/ǫ;
even a constant-factor approximation was not known prior to his work.
We let exp(x) denote ex ; all logarithms are to base e unless indicatedq
otherwise. With an appropri√
ate choice of parameters, Karger’s algorithm can run in time exp 3 log n + log n(4 log n + 2 log(1/ǫ)) +

o(log n) . In particular, if ǫ = Θ(1), this is n5+o(1) . (We assume that ǫ ≤ O(1), say ǫ ≤ 1/2, throughout.)
Karger’s algorithm is based on an algorithm for finding graphs cuts which have close to minimal weight. This
algorithm is the Contraction Algorithm, first introduced by [7]. This algorithm has emerged as an important
1

A preliminary version of this work appeared in the Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported in part by NSF
Awards CNS-1010789 and CCF-1422569. Email: davidgharris29@gmail.com.
3
Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park,
MD 20742. Research supported in part by NSF Awards CNS-1010789 and CCF-1422569, and a research award by Adobe, Inc.
Email: srin@cs.umd.edu.
2

1

building block for many graph algorithms. Just as importantly, it can be viewed as a stochastic process
which provides structural results about the graph cuts, for example, a bound on the number of small cuts.
In this paper, we provide a more detailed analysis of the Contraction Algorithm and its consequences.
This enables us to show a variety of improved bounds and algorithms for graph problems. The focus of this
paper is on improving the algorithm for estimating U (p).
The following definition will be useful:
Definition 1.1. The minimum cut-size in G, also known as the edge-connectivity of G, will be denoted by
c. Given α ≥ 1, an “α-cut” in G is a cut with at most αc edges.
Our results.
The main focus of our analysis is a much faster algorithm for estimate U (p):
Theorem 1.2. There is an algorithm to estimate U (p) in time n3+o(1) ǫ−2 .
Our analysis of the Contraction Algorithm will also allow purely structural bounds on the cut structure
of certain graphs:
c

Theorem 1.3. Suppose c is odd and α ≥ 1. Then there are at most O(n2α c+1 ) α-cuts. This exponent is
2c
.
optimal, in the sense that there are counter-examples to bounds of the form O(nαx ) for any x < c+1
In [12], an algorithm called the Recursive Contraction Algorithm was developed for finding all α-cuts. We
obtain a small improvement to this algorithm for the general problem of finding α-cuts. Unlike the previous
improvements, this only reduces the logarithmic terms:
Theorem 1.4. There is an algorithm that accepts as input a graph G and a real number α ≥ 1. This
algorithm succinctly enumerates, with high probability, all α-cuts of G in time O(n2α log n).
By contrast, the algorithm of [12] requires time O(n2α log2 n).
We note that our algorithm focuses on estimating the parameter U (p), but there are other connectivity
measures for which a strategy of enumerating “representative” cuts may be used. [8] gives a similar type
of algorithm for estimating multi-way connectivity and [4] discusses an algorithm for estimating parameters
related to clustering. Obtaining an FPRAS – or even a constant-factor approximation – for R(p) remains a
very intriguing open problem.
1.1. Overview of Karger’s algorithm, and our improvements. Karger’s algorithm for estimating U (p)
essentially consists of two separate algorithms, depending on the size of U (p). When U (p) > n−2−δ , where
δ is some constant, then Monte Carlo sampling provides an accurate estimate. As the samples are unbiased
with relative variance 1/U (p), then after n2+δ ǫ−2 samples we estimate U (p) accurately. Naively, it might
appear to require O(m) time per sample (one must process each edge). A clever sparsification strategy
described in Karger [8] reduces this to n1+o(1) time per sample. We will not modify Karger’s algorithm for
Monte Carlo sampling.
When U (p) is small, Monte Carlo sampling no longer can produce an accurate estimate in reasonable
time. In the regime U (p) < n−2−δ , Karger develops an alternative algorithm. In this case, Karger shows
that the event of graph failure is dominated by the event that a small cut of G has failed. This is done
by analyzing the number of cuts of small weight. In particular, there is some α∗ such that U (p) is closely
approximated by the probability that an α∗ -cut has failed. Karger provides an upper bound on the critical
value α∗ ; for example, when ǫ = Θ(1), we have α∗ ≤ 1 + 2/δ = O(1).
This significantly simplifies the problem, because instead of having to consider the exponentially large
collection of all cuts of G, we can analyze only the polynomial-size collection of α∗ -cuts. Using an algorithm
developed in [12], the Recursive Contraction Algorithm, Karger’s algorithm can catalogue all such α∗ -cuts
∗
in time n2α +o(1) . We refer to this as the cut-enumeration phase of Karger’s algorithm. Note that there is
a tradeoff between the Monte Carlo phase and cut-enumeration phase, depending on the size of δ.
Having catalogued all such small cuts, we need to piece them together to estimate the probability that
one of them has failed. For this, Karger uses as a subroutine a statistical procedure developed by Karp,
Luby, Madras [14]. This procedure can examine any collection of partially overlapping clauses, to provide
an unbiased estimate with relative error O(1) that one such clause is satisfied. By running ǫ−2 iterations of
this, we achieve the desired error bounds for U (p). The running time is linear in the size of the collection of
clauses. We refer to this as statistical sampling phase of Karger’s algorithm.
2

We will improve both the cut-enumeration phase and statistical sampling phase of Karger’s algorithm.
To improve the cut-enumeration phase, we will show a tighter bound on α∗ . In [13], a version of Karger’s
algorithm was programmed and tested on real graphs. This found experimentally that the average number
of cuts needed to accurately estimate the graph failure probability was about n3 , not the worst case n5 as
predicted by [8]. In this paper, we show this fact rigorously. We will show that the number of small graph
cuts in reliable graphs is far smaller than in general graphs.
The basic idea is to analyze the dynamics of the Contraction Algorithm, and to show that any small cut C
has a large probability of being selected by this algorithm. This analysis is quite difficult technically, because
it requires analyzing the three-way interconnections between the number of α-cuts of G, the effectiveness of
the Contraction Algorithm, and the value of U (p). The critical parameter that ties these three together is
the expected number of failed graph cuts.
Our improvement to the statistical sampling phase is more straightforward. The algorithm of [14] is
able to handle very general collections of clauses, which can overlap in complicated ways. However, this is
unnecessary for our purposes. We will show that the collection of cuts produced by the cut-enumeration
phase has a simple distribution, both statistically and computationally. This allows us to use a faster and
simpler statistical procedure to piece together the α∗ -cuts. As a result, the running time of each sample
reduces to about n2 ; in particular, we do not need to read the entire collection of α∗ -cuts for each sample.
In total, we reduce the running time of Karger’s algorithm to about n3+o(1) ǫ−2 . Obtaining faster runtimes with Karger’s recipe appears to be quite difficult; for if c is the size of the min-cut, then in the regime
where pc ≥ n−2+Ω(1) , it is not clear how to stop only at “small” cuts, and one appears to need Monte-Carlo
sampling – which requires a runtime that matches ours.
We note that another approach to estimating U (p) has been discussed in [17]. This algorithm finds a
pair of minimal cuts which are mostly disjoint, and hence there is a negligible probability that both cuts
fail simultaneously. By continuing this process, it is found in [17] experimentally that a branching process
can efficiently enumerate the probability that some small cut fails. While this algorithm is promising, the
analysis of [17] is fully experimental, and it appears that in the worst case this approach might require
super-polynomial time.
Around the time of our finalizing the published version of this work, a newer algorithm by Karger was
developed for estimating U (p), which is not based on cut-enumeration [11]. This algorithm has a run-time
of O(n3 polylog(n)/ǫ2 ), which is strictly better than ours.
1.2. Analyzing the trajectory of stochastic processes. The Contraction Algorithm is at the heart of
our algorithm, and our main contribution is giving an improved and tighter analysis of it. This is a complex
stochastic process, which applies a sequence of random transformations to the graph G. A single step can
radically alter the trajectory of this process. In the original paper [12] which introduced this algorithm, very
simple and elementary methods were used to bound its behavior. These bounds can be tight for general
graphs, but for other types of graphs these bounds are not accurate. However the analysis has not been
improved since [12].
To analyze the Contraction Algorithm, we introduce a new methodology for approximating stochastic
systems by continuous, deterministic dynamical systems. We believe this method may have applications to
other types of systems, and we will describe it here at a high level of generality.
Suppose we want to upper-bound E[f (G)], where f is some function of the stochastic process we are
interested in (for us, essentially f counts the number of edges found in the graphs produced at intermediate
stages of the Contraction Algorithm). We begin by making any number of heuristic guesses as to the behavior
of the process. These guesses can be totally unjustified and are often nothing more than wishful thinking.
For example, we may assume that any or all random variables are deterministic; we may assume that certain
parameters are as large as possible; we replace the discrete time intervals with continuous time. In this
way, we develop a dynamical system which we believe should approximate the behavior of E[f (G)]. This
dynamical system can be solved to produce some function f˜(G); we guess (hope) that E[f (G)] ≤ f˜(G) for
all graphs G.
So far, our approach mirrors that of [18], which gave general strategies for analyzing stochastic systems.
According to [18], the next stage of the solution would be to prove that our assumptions were approximately
correct. For example, instead of treating a random variable as deterministic, we may use concentration
inequalities to prove that it is centered around its mean (and thus is nearly deterministic). In the case of
3

the Contraction Algorithm, this approach does not seem to work; we are not able to show concentration
inequalities for the relevant random variables. The reason is that a single step of the Contraction Algorithm,
namely contracting an edge, can change the graph in a far-reaching way; this makes it hard to show the type
of “local effect” required for a concentration inequality.
By contrast, we will prove that any violation of these heuristic assumptions will only help us; we do not
necessarily show that the heuristic assumptions are true or approximately true. We will use induction on G
to prove that for any graph G we have E[f (G)] ≤ f˜(G).
To explain how this works, for expository purposes suppose that the function f˜ only depends on the final
stage of the stochastic process and that f˜ is a function not of the full graph G but only a single, simple-tocompute parameter φ(G), so that f˜(G) = g(φ(G)) (for example, φ(G) is the number min-cuts of G). Now,
after the initial time-step of the stochastic process, the graph G transforms into the graph H (where now H
is a random variable). Thus, we now have E[f (G)] = EH [E[f (H)]]; here we are splitting the expectation into
two pieces — the random choice for the first time-step, and the random choices for the remaining time-steps.
We will now use our induction hypothesis applied to the subgraph H; this gives us that E[f (H)] ≤ f˜(H).
Thus, so far we have shown that E[f (G)] ≤ EH [f˜(φ(H))].
Now, suppose that the function g(x) happens to be an increasing, concave-down function of x. In this
case, we can apply Jensen’s inequality to this expression, deriving EH [f˜(H)] ≤ g(E[φ(H)]), and hence that
E[f (G)] ≤ g(E[φ(H)]).
Thus, in order to continue the induction proof, we merely need to show that
g(E[φ(H)]) ≤ g(φ(G))
We have thus reduced our trajectory analysis to computing E[φ(H)] (which involves only a single timestep of the stochastic process and the relatively simple function φ) and a simple inequality for a concrete
function g.
Overall, this process depends very heavily on the concavity and monotonicity properties of the function
˜
f . This is very similar to how one can apply Jensen’s inequality to interchange the expectation of a function
with the function of its expectation. So, in a sense we can view our method as a “generalized Jensen’s
inequality” for stochastic systems.
1.3. Outline. In Sections 2 and 3, we begin by reviewing some key results and definitions concerning graph
cuts. Most of these results are recapitulations of Karger [8].
In Section 4, we describe a new statistical sampling algorithm for the following problem: given a fixed
collection A of cuts, what is the probability that at least one cut from A fails? We show that this algorithm
has a faster running time, and is just as accurate, compared to the algorithm of [14] used in [8, 9]. Although
this sampling algorithm is the final part of our overall algorithm to estimate U (p), we will discuss it first
because it is relatively self-contained and because it is less technically challenging than the rest of the paper.
In Section 5, we introduce the Contraction Algorithm, an algorithm described by [12]. This algorithm
provides an efficient randomized procedure for finding small-weight cuts in G. It also can be viewed as a
probabilistic process which can provide purely structural bounds on G. We will be interested in the following
question, which is more general than that considered by [12]: suppose we are given a fixed target cut C of G.
Under what circumstances does the Contraction Algorithm select C? What can we say about the dynamics
of the Contraction Algorithm in those cases in which C will ultimately be selected ? We will prove a series of
technical Lemmata which describe these dynamics. Roughly speaking, we “factor out” C to show that the
Contraction Algorithm has a uniform behavior regardless of which target cut C (if any) we are interested in.
In Section 6 we apply this machinery to analyze the Contraction Algorithm in the case in which the
(unweighted) graph G has c an odd number. These results are not necessary for our analysis of Karger’s
algorithm. We include them here for two reasons. First, the number of small cuts is basically known in the
case of even c — the worst case behavior comes from a cycle graph, in which there are n vertices in a ring
with c/2 edges between successive vertices. The case of odd c has been mostly overlooked in the literature.
Second, the case of small odd c provides an easier warm-up exercise for the analysis in Section 7. In Section 6,
we keep track of the number of min-cuts remaining in G during the evolution of the Contraction Algorithm;
in Section 7 we must keep track of the number of cuts of all sizes. Section 7 analyzes how the dynamics of
the Contraction Algorithm are affected by the magnitude of U (p). The critical parameter is Z̄, the expected
4

number of failed cuts in G. We show how Z̄ affects the number of edges which are available in any round of
the Contraction Algorithm, and we show how Z̄ itself changes during the execution.
The proof method used in Sections 6 and 7 follows the outline of Section 1.2. We give a function f˜,
and prove by induction that the probability of a cut surviving the Contraction Algorithm is at least f˜.
This function f˜ is very complicated and could not have been guessed from first principles. Instead, we
first simplify our stochastic process using unwarranted independence and monotonicity assumptions (for
example, we assume that the subgraphs produced during the Contraction Algorithm have as few edges
as possible subject to the minimum-cut condition), and then translate the stochastic time-steps into a
differential equation which can be solved in closed form. This heuristic analysis gives us the mysterious
function f˜, which we then rigorously prove correct. In particular, these “unwarranted independence and
monotonicity assumptions” actually correspond to the worst-case behavior of our stochastic process!
In Section 8, we apply the analysis of Section 7 to show that α∗ , which is the bound of the size of the
cuts necessary to approximate U (p), is smaller than the bound given by Karger. We note that while Karger
gave a simple bound which could be computed explicitly, our bound depends on the graph parameter Z̄
which we cannot determine easily. However, using this formula, one can determine an upper bound on the
total number of iterations of the Contraction Algorithm that are needed to find the α∗ -cuts; this bound is
irrespective of Z̄.
In Section 9, we analyze the Recursive Contraction Algorithm. This is an algorithm which allows us
to run the Contraction Algorithm “in bulk”. If we are interested in finding many graph cuts, we must
run the Contraction Algorithms multiple times. However, most of the work for processing the graph can
be amortized across these multiple runs. In particular, we can essentially reduce the running time for the
Contraction Algorithm from n2 (dominated by reading the original graph) to na where a is a small constant.
In Section 10, we describe how to combine all the pieces and obtain a full algorithm. This includes deciding
when to use Monte Carlo sampling and when to enumerate the small cuts, a detail omitted in Karger [8].
Finally, Section 11 concludes.
2. Preliminaries
For a multi-graph G, we define a cut of G to be a partition of the vertices into two classes V = A ⊔ A′ ,
with A, A′ 6= ∅. The sets A, A′ are the shores of the cut. We distinguish this from an edge-cut, which is
a subset E ′ of the edges of G such that removal of E ′ disconnects G. Every cut of G induces an edge-cut
of G, namely the edges crossing from A to A′ . The weight or size of an edge-cut is the number of edges it
contains. We say an edge-cut is minimum if it has the smallest size of all edge-cuts, and we denote by c the
size of the smallest edge-cut. We say an edge-cut is minimal if no proper subset is an edge-cut.
We will often abuse notation so that a cut C may refer to either the vertex-partition or the edge-cut it
induces. Unless stated otherwise, whenever we refer to a cut C, we view C as a set of edges.
As mentioned before, for any α ≥ 1 we define an α-cut to be a cut (not necessarily minimal) whose
corresponding edge-cut has at most αc edges, and we define a min-cut to be a 1-cut, i.e. a cut of weight c
exactly.
In this paper, we seek to estimate the probability that the graph becomes disconnected when edges are
removed independently with probability p. When edges are removed in this way, we say that an edge-cut
fails if and only if all the corresponding edges are removed. In this case, we may concern ourselves solely
with cuts. The reason for this is that graph G becomes disconnected if and only if some cut of G fails.
This method can be generalized to allow each edge to have its own independent failure probability pe . As
described in [8], given a graph G with non-uniform edge failure probabilities, one can transform this to a
multi-graph G′ with uniform edge failure probabilities by replacing each edge of G with a bundle of edges,
and setting p appropriately.
We will assume that the graph G is presented as an adjacency matrix with n2 words. Each word records
the number of edges that are present between the indicated vertices. As described in [7], it is possible to
transform an arbitrary graph, in which the number of edges may be unbounded, into one with cells of size
O(log(1/ǫ) + log n) with similar reliability; hence the arithmetic operations will take polylogarithmic time
in any computational model. This transformation may have a running time which is super-polynomial in
n, although it is close to linear time as a function of the input data size. We will ignore these issues, and
simply assume that we can perform arithmetic operations to precision ǫ and random number generation of
an entire word in a single time step.
5

As our algorithm closely parallels Karger’s, we use the notation of [8] wherever possible. Recall that c
is the size of the smallest edge-cut. As in [8], we let pc = n−2−δ , with δ > 0 being the case of primary
interest (the complementary case can be handled by simple Monte-Carlo sampling). We note that δ can be
determined in time n2+o(1) , simply by finding the size of the minimum cut. Hence we can assume δ is known.
Often we will derive estimates assuming δ ≥ δ0 ; here δ0 can be an arbitrarily small positive constant. This
assumption allows us to simplify many of the asymptotic notations, whose constant terms may depend on
δ0 . In fact, our algorithm is best balanced when δ → 0. It is not hard to see that all of our asymptotic
bounds when δ ≥ δ0 can be relaxed to allow δ → 0 sufficiently slowly, for example as δ = 1/ log log log log n.
When we analyze α-cuts, we are primarily interested in the case when α is a slow-growing function. (In
fact, the case where α = O(1) would be basically sufficient to analyze all of our algorithmic improvements.)
We will show how to bound the number of such cuts.
The following is a well-known theorem of [6], and indeed, the rest of this section is basically a recapitulation
of Karger’s work from [6].
Theorem 2.1. ([6]) The number of α-cuts is at most n2α .
The following combinatorial principle, which is basically a form of integration by parts, will be used in a
variety of contexts.
Proposition 2.2. Let F : R → [0, ∞) be any increasing function with distributional derivative dF (x) and
with the property that, for any α ≥ 1, the number of α-cuts is at most F (α). Let g : R → [0, ∞) be any
continuous decreasing function. Then
Z ∞
X
g(|C|/c) ≤ F (α)g(α) +
g(x)dF (x)
x=α

Cuts C of weight
|C|≥αc

Proof. Enumerate the weights of all cuts whose weight is at least αc in sorted order as αc ≤ r1 ≤ r2 ≤ · · · ≤
rk . Observe that for any i = 1, . . . , k the definition of F implies that i ≤ F (ri /c).
Then
X

g(|C|/c) =

Cuts C of weight
|C|≥αc

k
X

g(ri /c) = kg(rk /c) +

k−1
X
i=1

i=1

≤ F (rk /c)g(rk /c) +



i g(ri /c) − g(ri+1 /c)

k−1
X



F (ri /c) g(ri /c) − g(ri+1 /c)

k
X



g(ri /c) F (ri /c) − F (ri−1 /c)

i=1

as i ≤ F (ri /c) and g(ri /c) − g(ri+1 /c) ≥ 0
= g(r1 /c)F (r1 /c) +

i=2

Z

= g(r1 /c) F (α) +

r1 /c

x=α

= F (α)g(r1 /c) +

Z

r1 /c

Z
k
 X
g(ri /c)
dF (x) +

Z

r1 /c

g(r1 /c)dF (x) +

Z

rk /c

= F (α)g(α) +

x=α

x=α

k Z
X
i=2

g(x)dF (x) +

k Z
X
i=2

dF (x)

x=ri−1 /c

i=2

x=α

≤ F (α)g(α) +

ri /c

ri /c

g(ri /c)dF (x)

x=ri−1 /c

ri /c

g(x)dF (x)

as g is decreasing

x=ri−1 /c

g(x)dF (x) ≤ F (α)g(α) +

Z

∞

g(x)dF (x)

x=α


Combining Proposition 2.2 and Theorem 2.1, gives a simple proof of the following result from [8]:
6

Corollary 2.3. Let 0 < q < n−2−Ω(1) , α ≥ 1. Then
X
q |C|/c = O((n2 q)α )
Cuts C of weight
|C|≥αc

Proof. Apply Proposition 2.2, using F (x) = n2x and g(x) = q x . We have
Z ∞
X
q |C|/c ≤ q α n2α +
q x × 2n2x log n dx
Cuts C of weight
|C|≥αc

x=α


2(n2 q)α log n
log n2 
2 α
1
−
=
(n
q)
log(n2 q)
log(n2 q)


2
log n
≤ (n2 q)α 1 −
log(n2 n−2−Ω(1) )
= (n2 q)α −

= O((n2 q)α )


The following result is as example of this principle; it will later be strengthened in Proposition 8.1.
Corollary 2.4. ([8]) Suppose δ ≥ δ0 for some constant δ0 > 0. Then the probability that a cut of weight
≥ αc fails is at most O(n−αδ ).
Proof. By the union-bound,
P(Cut of weight ≥ αc fails) ≤

X

(pc )|C|/c .

Cuts C of weight
|C|≥αc

Now apply Corollary 2.3.



This leads to one of the key theorems of Karger’s original work:
Theorem 2.5. ([8]) Suppose δ ≥ δ0 for some constant δ0 > 0. Then U (p) can be approximated, up to
relative error O(ǫ), by the probability that a cut of weight ≤ α∗ c fails, where
α∗ = 1 + 2/δ −

log ǫ
δ log n

Proof. The absolute error committed by ignoring cuts of weight ≥ α∗ c is at most the probability that such
∗
a cut fails; by Corollary 2.4 it is at most O(n−α δ ).
The minimum cut of G fails with probability pc = n−2−δ , so U (p) ≥ pc = n−2−δ .
Hence the relative error committed by ignoring cuts of weight ≥ α∗ c is at most
∗

Rel err = O(

n−α δ
) = O(ǫ)
n−2−δ


We do not want to get ahead of ourselves, but one of the main goals of this paper will be to improve on
the estimate of Theorem 2.5. In proving Theorem 2.5, we used two quite different bounds. These bounds
are tight separately, but for very different kinds of graphs. In estimating the absolute error, we bound the
number of α-cuts that may appear in G by O(n2α ). This is tight for cycle graphs, as discussed in Lemma 3.2,
which have a very large number of cuts. On the other hand, when we estimate U (p) ≥ pc , we are assuming
that the graph has just a single small cut. As we will show, no graph can have both bounds be simultaneously
tight.
7

3. The total number of failed cuts
We define the random variable Z to be the number of cuts of G which fail when edges are removed
independently with probability p. The expectation of Z, also known as the partition function is
X
Z̄ =
p|C| .
cuts C

This is an overestimate of the graph failure probability which ignores the overlap between the cuts. The
number of failed cuts Z, and its expectation Z̄, will play crucial roles in our estimates. We take here an
approach based on [1], inspired by establishing a connection between the number of failed cuts and an
appropriately scaled binomial random variable.

Proposition 3.1. Suppose we remove a subset L of edges from G, and the resulting graph H has R connected
components. Then L causes exactly 2R−1 − 1 cuts of G to fail.
Proof. Any partition of the R components corresponds to a failed cut.



Lemma 3.2. Let pc = n−2−δ for δ ≥ δ0 > 0. Suppose we remove edges from G with probability p. Let H
denote the resulting graph and let R be its number of connected components. Then for n sufficiently large
and r ≥ 1 we have
P(R ≥ r) ≤ 1.01n−rδ/2 /r!
Proof. As shown in [15], [16], [8], the probability that H has ≥ r connected components under edge-failure
probability p, is at most the probability that the graph C has ≥ r connected components under edge failure
q = pc/2 , where C is the cycle graph which contains n vertices and a single edge between successive vertices
in the cycle. If r edges fail in C, then the resulting number of distinct components is max(1, r). Hence the
probability that C results in r distinct components is the probability that a binomial random variable, with
n trials and success probability q, is at least r:
n
n  
X
X
n(δ/2)(1−r)
n i
n−i
ni (ni(−2−δ)/2 /r!) ≤
q (1 − q)
≤
P(≥ r connected components) ≤
i
r!(nδ/2 − 1)
i=r
i=r
As δ > δ0 > 0, then nδ/2 ≥ 1000 for n ≥ Ω(1). Thus nδ/2 − 1 ≥ 0.999nδ/2 and we have
P(≥ r connected components) ≤

n(δ/2)(1−r)
≤ 1.01n−δr/2 /r!
0.999r!nδ/2


Thus Z̄ is bounded within a relatively small range:
Corollary 3.3. For δ ≥ δ0 > 0 and for n sufficiently large,

n−2−δ ≤ Z̄ ≤ n−δ

Proof. The lower bound Z̄ ≥ n−2−δ follows since the probability that any one min-cut fails is n−2−δ .
To show the upper bound, we have
X
Z̄ = E[Z] = E[2R−1 − 1] =
P(R ≥ r)2r−2
r≥2

≤ 1.01

X 2r−2 n−rδ/2

r≥2

r!

by Lemma 3.2



−δ/2
≤ 0.26 −2n−δ/2 + e2n
−1

For n sufficiently large, the exponent 2n−δ/2 approaches 0. As ex ≤ 1 + x + 0.51x2 for x sufficiently close
to 0, it follows that

Z̄ ≤ 0.26 −2n−δ/2 + (1 + 2n−δ/2 + 0.51 × 4n−δ ) − 1 = 0.5304n−δ
as desired.


8

In light of Corollary 3.3, it is often convenient to write
pc = n−2−δ

Z̄ = n−2−δ+β

Here, δ, β should be thought of as “parameters” of the graph; δ measures the probability that the smallest
cut of G fails, while β ∈ [0, 2] counts the number of small cuts. The case β ≈ 0 means there is only a
single small cut and the other cuts are very large; the case β ≈ 2 corresponds to the cycle graph. This
parametrization will appear many times throughout this paper. We will always assume that δ > δ0 > 0,
where δ0 is a constant which may be made arbitrarily small. All of the hidden asymptotic terms may depend
on δ0 . We will not state this explicitly for the remainder of the paper.
We next show that the expected number of failed cuts remains small, even after conditioning on rare
events:
Proposition 3.4. Let E be an event with probability P(E). Then
2

E[Z | E] ≤ O(P(E)− δ log2 n )
−

2

Proof. Let q = P(E). If n < O(1), then Z ≤ 2n ≤ O(1) while q δ log2 n ≥ 1, and so the result holds. So we
may assume that n is larger than any necessary constant throughout this proof.
Then:
∞
∞
X
X
P(R ≥ r)
E[Z | E] = E[2R−1 − 1 | E] ≤
2r−1 P(R ≥ r | E) ≤
2r−1 min(1,
)
q
r=1
r=1
≤
≤

∞
X

2r−1 min(1,

r=1

⌈x⌉−1

X

2r−1 +

r=1

≤ 2⌈x⌉ +
≤ 2x+1 +
≤ 2x+1 +
≤ O(2

1.01
)
nrδ/2 q

by Proposition 3.2

∞
X
1.01 × 2r−1
qnrδ/2

where x =

r=⌈x⌉

1.01 × 2⌈x⌉−1 n(δ/2)(1−⌈x⌉)
q(nδ/2 − 2)

2 log(1/q)
δ log n

as 2n−δ/2 < 1

2x+1 n(δ/2)(1−x)
q(nδ/2 − 2)

2x+1 n(δ/2)(1−x)
q(nδ/2 /2)

2 log(1/q)
δ log n

) = O(q

2
− δ log

for n > 24/δ
2n

)


As an application of Proposition 3.4, we show that Z̄ is nearly equivalent asymptotically to U (p), although
the former is much more tractable.
Proposition 3.5. For δ ≥ δ0 > 0, we have U (p) = Θ(Z̄) .
Proof. By the union bound, U (p) ≤ Z̄.
Now note that E[Z] = E[Z | Z ≥ 1]P(Z ≥ 1). So U (p) = P(Z ≥ 1) =
that E[Z | Z ≥ 1] = O(1). For this we have:
2

E[Z | Z ≥ 1] ≤ O(U (p)− δ log2 n )

2
− δ log
2n

≤ O((n−2−δ )

E[Z]
E[Z|Z≥1] .

So it suffices to show

by Proposition 3.4
)

as U (p) ≥ pc = n−2−δ

= O(22+4/δ ) ≤ O(22+4/δ0 ) = O(1)


As in Karger, our strategy will be to use Monte Carlo estimation for U (p) when U (p) is large. The
cut-enumeration will be only be performed when U (p) is small. For this, we have the following useful
bounds:
9

Proposition 3.6. Let K > 2 be an arbitrary constant. Then for U (p) < n−K and n sufficiently large, we
have the following:
(1) δ ≥ K − 2 > 0.
(2) δ ≥ β + Ω(1).
(3) β ∈ [0, 2].
Proof. First, observe that if a min-cut fails, then G fails, so U (p) ≥ pc = n−2−δ . This implies that δ ≥ K − 2.
So we may set δ0 = K − 2 > 0, which satisfies (1).
Also, by Proposition 3.5, we have U (p) = Θ(Z̄) = Θ(n−2−δ+β ). Hence β ≤ 2 + δ − K + O(1/ log n) ≤
−Ω(1) + δ + O(1/ log n). This implies that for n sufficiently large β ≤ δ − Ω(1).
The bound β ∈ [0, 2] is simply a restatement of Proposition 3.3.

For the majority of this paper, we will assume that U (p) < n−K for some fixed K > 2, and
that n is sufficiently large. Thus, all of the conclusions of Proposition 3.6 hold. We will note
this at the beginning of each relevant section; all the results in that section may depend on
this assumption and all the resulting asymptotic notations may depend upon K.
4. Estimating the failure probability for a collection of cuts
In this section, we address the following statistical problem. Suppose we are given some collection A
consisting of N cuts, which includes at least one min-cut. We define the failure probability of A as
UA (p) = P(at least one cut from A fails)

In this section, we will assume U (p) < n−K for some constant K > 2; thus the conclusions of
Proposition 3.6 hold.
Our goal here is to estimate UA (p) to within relative error ǫ. This is a key subroutine for Karger’s
algorithm, and it will also be used for ours. For this, Karger uses an elegant algorithm developed by Karp,
Luby, Madras [14]; in this context, that algorithm has a running time of roughly n2 N ǫ−2 . We will give a
new algorithm running in time O(N polylog(N n) + n2 ǫ−2 ).
We make some elementary observations first. Let us define the random variable
X
ZA =
[C fails],
C∈A

where we use the Iverson notation so that [C fails] is 1 if C fails, and 0 otherwise.
Then UA (p) = P(ZA ≥ 1). Clearly UA (p) ≤ U (p) and ZA ≤ Z. Also, UA (p) ≥ pc as A contains at least
one min-cut.

4.1. Data structures for A. Each cut in A might require Ω(n) space to store explicitly and thus even
reading A might require Ω(N n) time. We will give a running time which may be smaller than this, and thus
we must store and generate A in a compressed form.
Instead of storing the full information about each cut C ∈ A, we will store three smaller pieces of
information, each taking just O(log(N n)) words of storage, instead:
(1) A unique identifier for C
(2) The weight of C
(3) A pointer which allows us to fully reconstruct C in time O(n2 )
In order to assign every cut of A a unique identifier, we may use a simple random hashing scheme. We
choose a random function H : V → [2b ], where b = φ log N and φ > 0 is some constant.
We then define the
P
identifier for a cut C which has shores A, V − A with vertex 1 in A, by H(C) = v∈A b(v) where the sum
is taken modulo 2b . It is not hard to see that for φ a sufficiently large that with high probability all cuts of
A receive distinct identifiers.
Because the cuts of C are assigned distinct identifiers, we may sort A and remove any duplicates in time
O(N log2 (N n)). Thus, we may assume that after an additional pre-processing step, we have that N ≤ 2n .
This is a crude bound, but it will be sufficient for many purposes of analyzing our algorithm.
Proposition 4.1. Suppose that A has been sorted. Then given any cut C of G, there is an algorithm running
in time O(n2 ) to determine if C ∈ A.
10

Proof. We compute H(C) in time O(n). As all the cuts of A receive distinct identifiers, there is at most one
C ′ ∈ A with H(C ′ ) = H(C). An index to the cut C ′ can be found via binary search in time O(b log N ) ≤
O(log2 N ). Using our crude bound N ≤ 2n , this is at most O(n2 ).
Now, if there is no such C ′ ∈ A, then we know that C ∈
/ A and we are done. Otherwise, C ∈ A if and only
if C = C ′ . To check this, we use the pointer to fully reconstruct C ′ from its index; this step takes O(n2 ).
At this stage, both C and C ′ are represented explicitly so they can be compared in time O(n).

4.2. The statistical estimation algorithm. We take as our starting point a simpler algorithm, which
was presented as a toy or warm-up exercise in Karp, Luby, Madras [14]. We will see how to implement it
faster than their alternative, more sophisticated algorithms.
1. Select a cut Q from A with probability ∝ p|Q| .
2. Let L be a random subset of the edges in G − Q, in which each such edge is chosen
independently with probability p. Let H = G − Q − L.
3. Count how many P
cuts in A have failed in H; let J denote the number of such cuts.
4. Estimate ÛA =

C∈A

p|C|

J

.

P
We can perform step (1) by choosing a random real number in the range [0, p|C| ] and then performing
a binary search; as A explicitly stores the weight of all the cuts, this step can be implemented (with some
pre-processing) in time O(log(N n)).
The main cost of this algorithm is step (3). If A is an arbitrary collection of edge sets, then seemingly
the only way to do this would be to check each member of A to see whether it failed in H. This would
require roughly O(mN ) time per execution. This high running time is the main motivation for the more
sophisticated algorithm of [14].
However, A is a collection of cuts, and we can significantly accelerate step (3) by taking advantage of this
fact. We implement step (3) by enumerating all the failed cuts of H, and checking for each if it is present in
A. We will show that H typically has a small number of cuts, and so this step is relatively inexpensive.
We first show that ÛA is a good estimator for UA (p), which in turn is a good estimator for U (p).
Proposition 4.2. For any cut C ∈ A, the distribution of H in step (2) of this estimation procedure,
conditional on Q = C, is the same as the distribution of the graph G′ resulting from edge failures, conditional
on the event that C fails.
For any cut C ∈ A, the distribution of J conditional on Q = C is the same as the distribution of ZA
conditional on the event that C fails.
Proof. Because the edge failures are independent, then conditioning on the event that C fails is equivalent
to removing the edges of C and letting the remaining edges fail independently. This is exactly the random
distribution of graphs selected in step (2) of our estimation algorithm.

Proposition 4.3 ([14]). The statistic ÛA is an unbiased estimator, viz.
E[ÛA ] = UA (p)
Proof. The proof is shown originally in [14]; we present a modified proof here for completeness.
Consider the following random process: we randomly allow edges to fail with probability p. If ZA ≥ 1,
then we choose one failed cut of A uniformly at random, and mark it.
Note that some cut of A fails if and only if exactly cut in A is marked. So
X
UA (p) =
P (C marked)
C∈A

=

X

C∈A

=

X

C∈A

=

X

P (C fails)E[1/ZA | C fails]
p|C| E[1/J | Q = C]
P (Q = C)

C∈A

=

X

C∈A

X

C∈A

p

|C|


p|C| E[1/J | Q = C]


E[1/J] = E[ÛA ]
11

by Proposition 4.2


Proposition 4.4. Suppose that C ∈ A. Let H be the graph resulting from removing C and allowing other
edges to fail independently. Let Z denote the total number of failed cuts of H. Then
E[Z | Q = C] ≤ eO(|C|/c)
Proof. We have that
E[Z | Q = C] = E[Z | C fails]
≤ O((p
= O(2
=2

by Proposition 4.2

2
|C| − δ log
2n

)

2(|C|/c)(2+δ)
δ

)

by Proposition 3.4

)

O(|C|/c)


Proposition 4.5. Suppose that A contains a min-cut. Then

2
E[ÛA
] ≤ O(E[ÛA ]2 )

That is, the statistic ÛA has relative variance O(1).
2
Proof. We have E[UA
]/E[UA ]2 = E[1/J 2 ]/E[1/J]2 ≤ 1/E[1/J]2. Thus, it will suffices to show E[1/J] ≥
Ω(1).
First, we claim that there is some constant x > 1 such that P(|Q| ≤ xc) ≥ 1/2. For,
P
c
C∈A,|C|≥xc p
P
P(|Q| ≥ xc) =
c
C∈A p
P
|C|
|C|≥xc p
≤
as A contains a min-cut
n−2−δ
≤ O(n2+δ n−(2+δ)x n2x )
by Corollary 2.3

< 1/2,

for x sufficiently large constant

Now, conditional on the event that |Q| ≤ xc, by Proposition 4.4 we have that E[Z] ≤ eO(x) .
As J ≤ Z, this implies that E[1/J] ≥ E[1/J | Q ≤ xc]P(Q ≤ xc) ≥ 1/(xc)P (Q ≤ xc) ≥ e−O(x) × 1/2 ≥
Ω(1).

Finally, we prove that we can execute this estimation procedure relatively quickly — much more quickly
than by reading in the entire collection A:
Proposition 4.6. Suppose that A contains a min-cut. Then, after preprocessing steps, the expected running
time of the estimation algorithm is O(n2 ).
Proof. We can enumerate the connected component structure of H in time O(n2 ). By Proposition 4.1, it
requires O(n2 ) to check whether any cut of H is present in A. Thus, we may compute J in overall running
time is O(Zn2 ). Thus, the expected time for this step is ≤ O(n2 )E[Z]. We estimate E[Z] by breaking up
the sum in contributions from small cuts (weight is ≤ xc) and big cuts (weight > xc); here x is a parameter
we will discuss later.
X
E[Z] = E[Z | |Q| ≤ xc]P(|Q| ≤ xc) +
E[Z | Q = C]P(Q = C)
C∈A
|C|>xc

= 2O(x) +

X

E[Z | Q = C]P(Q = C)

X

E[Z | Q = C] P

C∈A,|C|>xc

≤ 2O(x) +

C∈A,|C|>xc

p|C|
|C ′ |
C ′ ∈A p

12

Proposition 4.4

≤ 2O(x) + n2+δ
≤ 2O(x) + n2+δ
≤2

O(x)

+n

2+δ

X

C∈A,|C|>xc

X

C∈A,|C|>xc

X

E[Z | Q = C]p|C|
E[Z | C failed]p|C|

eO(|C|/c) p|C|

as A contains a min-cut
Proposition 4.2

Proposition 4.4

|C|>xc

≤ 2O(x) + n2+δ O(n−δx )

Corollary 2.3

Now setting x = 1 + 2/δ = O(1), we see that this overall expression is O(1).

We summarize our estimation procedure:
Proposition 4.7. Let A be a collection of cuts which includes at least one min-cut. Then there is an
algorithm for estimating UA (p) to within relative error ǫ with probability > 0.99, and running in time
O(N polylog(N n) + n2 ǫ−2 ).
P
Proof. We have pre-preprocessing steps including sorting A and computing C∈A p|C| which can be executed
in time O(N polylog(N n)).
After this, a single iteration has relative error O(1) and costs O(n2 ) expected time. We repeat λǫ−2
independent trials of this algorithm. This reduces the relative variance of the resulting unbiased statistic
to O(λ−1 ǫ−1 ). By Chebyshev’s inequality, for λ sufficiently large, the resulting statistic estimates UA (p) to
relative error ǫ with probability > 0.99.

5. The Contraction Algorithm
We now turn our attention to how to find a representative set of cuts to use to estimate U (p). Key to this
is an algorithm of [12] for finding cuts in a graph. This algorithm is called the Contraction Algorithm, and is
based on a graph transformation called contraction which will appear throughout this paper. Given a graph
G and an edge e = hx, yi of G, then we define the contraction G/e by identifying x and y. More formally,
we create a new vertex labeled xy, we delete the vertices x, y and for each edge hx, vi ∈ G we create a new
edge hxy, vi; similarly, for each each hy, vi ∈ G we create a new edge hxy, vi. If there are any loops created
by this process, we delete them.
Suppose that a graph H is derived from G by performing a series of contractions. Then we say that
H is a contraction-subgraph of G. Every vertex of H corresponds to a set of vertices in G, any edge of H
corresponds to an edge of G, and any cut of H corresponds to a cut of G. Given a cut C of G, we say that
C survives in H if C corresponds to some cut of H; equivalently, this holds if every edge of C corresponds
to some edge of H. We often abuse notation, so that for any edge e ∈ H we also write e to refer to the
corresponding edge of G.
For any set of edges L = {e1 , . . . , el }, we may also define G/L as follows. We initially set H1 = G and
proceed through the edges e ∈ L one by one; if edge ei is present in Hi then Hi+1 = Hi /ei ; otherwise,
Hi+1 = Hi . We then define G/L = Hl+1 . Although this definition depended on the ordering of the edges in
L, it is a simple exercise to see that changing this ordering does not change G/L.
The Contraction Algorithm takes as input a parameter α, which is roughly speaking the size of the cuts
that it is designed to find. We define the Contraction Algorithm with parameter α as follows:
1. Initialize Gn = G.
2. Repeat for i = n, n − 1, . . . , ⌈2α⌉ + 1:
3. Select an edge Fi of Gi uniformly at random.
4. Set Gi−1 ← Gi /Fi
5. Output a cut C sampled uniformly from G⌈2α⌉ . (We say the Contraction Algorithm
selects C)
At each stage i of the Contraction Algorithm, the graph Gi has exactly i vertices. We let Mi denote
the number of edges in Gi . We refer to the sequence of edges hFn , Fn−1 , . . . , F⌈2α⌉ i as the history of the
Contraction Algorithm; note that the full sequence of graphs Gi is completely determined by Fn , . . . , F⌈2α⌉+1 .
13

We may also refer to the history of the Contraction Algorithm up to stage i, which we denote by F>i ; by
this we mean the sequence of edges F>i = hFn , . . . , Fi+1 i; these determine Gn , . . . , Gi uniquely.
We are only partially interested in the Contraction Algorithm as an algorithm per se. We will often
instead view it as a stochastic process which allows us to analyze the number of cuts that are present in
the graph. We refer to this stochastic process as CA(G). Thus we may write, for instance ECA(G) [Mi ]; this
means that we are taking the expected value of the number of edges present in the graph Gi , when we run
the Contraction Algorithm starting with graph G.
We will show that, for an arbitrary cut C, the Contraction Algorithm selects C with at least a certain
probability. In this type of analysis, we regard C as fixed. We refer to C as the target cut. In order
for the Contraction Algorithm to find the target cut C, a necessary condition is that C must remain in
the final G⌈2α⌉ . (This is not a sufficient condition, as we still must randomly select C among the cuts of
G⌈2α⌉ .) If C remains in G⌈2α⌉ , then we say that CA(G) succeeded and we say that C survived. We also say
that C survived the Contraction Algorithm. We emphasize that this only for the purposes of analysis; the
Contraction Algorithm itself is run without any target in mind.
When we run the Contraction Algorithm with parameter α, we say that a cut C survived to stage i if C
remains in Gi . Sometimes we may say that C survives to stage i without specifying the parameter α; here
we assume that α is any arbitrary real number which is at most i/2. This is acceptable because Gi does not
depend on α itself, only whether i ≥ 2α.
The contraction process for C. When we fix a target cut C, we may imagine a related stochastic process
which we refer to as the Contraction Process. This process may be defined more broadly in terms of any
edge-set L, and we denote it by CP(G, L):
1. Initialize Gn = G.
2. Repeat for i = n, n − 1, . . . , 1:
3. If all the edges of Gi are in L, then terminate the loop.
4. Otherwise, select an edge Fi of Gi − L uniformly at random.
5. Set Gi−1 ← Gi /Fi

If this process terminates at stage i (that is, all the edges of Gi are in L), then we say that Gj = ⊥ for
j < i. Note that it is possible for some edge of L to become contracted, even though they are not themselves
selected, if another edge with the same end-points is selected. This never happens if L is a cut; in the
Contraction Process for C, all the edges of C remain present in the resulting contraction-subgraphs.
Finally, observe that one may view the Contraction Algorithm as a special case, namely CA = CP(G, ∅).
For i = 1, . . . , n let Mi denote the number of edges in the graph Gi . We begin with some useful elementary
bounds on M . Every vertex of v of the graph Gr defines a cut, namely, v is on one shore and all the other
vertices are on the other shore. As the minimum cut size is c, this implies that every vertex must have degree
≥ c, so Mr ≥ rc/2. Thus during the process CP(G, L), as long as |L| ≤ rc/2 then Gr 6= ⊥. In fact, this
bound will always hold in our analysis, so that we will never need to deal with the case of Gr = ⊥.
The following proposition shows the connection between the Contraction Algorithm and the Contraction
Process for a cut C:
Proposition 5.1. Suppose that en , . . . , ei+1 are edges of G but not edges of the cut C and let Mi+1 , . . . , Mn
denote their edge counts.
Then
n
 Y
|C| 
(1 −
PCA(G) (F>i = hen , . . . , ei+1 i) =
) PCP(G,C) (F>i = hen , . . . , ei+1 i)
Mr
r=i+1
when the Contraction Algorithm is applied with parameter ⌈2α⌉ ≤ i.
Proof. We prove this by induction on G. The base case is when G has i vertices; in this case both the LHS
and RHS are easily seen to be one.
So we now consider the induction step. In the first stage of the Contraction Algorithm, we select some
edge Fn uniformly from G. The probability that Fn = en is M1n . Conditional on this event, the remaining
stages of the Contraction Algorithm are equivalent to the Contraction Algorithm applied to the graph G/
Fn = G/en . The edge en is not present in C, and so cut C remains a cut of G/en . So we can apply the
14

induction hypothesis to it.
1
PCA(G/en ) (F>i = hen−1 , . . . , ei+1 i)
Mn
n−1
|C| 
1  Y
(1 −
) PCP(G/en ,C) (F>i = hen−1 , . . . , ei+1 i)
=
Mn r=i+1
Mr

PCA(G) (F>i = hen , . . . , ei+1 i) =

=

n
 Y

(1 −

|C| 
1
)
PCP(G/en ,C) (F>i = hen−1 , . . . , ei+1 i)
Mr Mn − |C|

(1 −

|C| 
) PCP (G,C) (F>i = hen , en−1 , . . . , ei+1 i)
Mr

r=i+1

=

n
 Y

r=i+1

and the induction is proved.

ind. hypothesis



Corollary 5.2. Let C be any cut. The probability that cut C survives to the ith stage of the Contraction
Algorithm (i.e. the probability that cut C is present in the graph Gi ), is exactly equal to
n
h Y
|C| i
)
(1 −
P(C survives to Gi ) = ECP (G,C)
Mr
r=i+1
Proof. We sum over all partial histories up to stage i:
X
PCA(G) (F>i = hen , . . . , ei+1 i)
P(C survives to Gi ) =
en ,...,ei+1
all disjoint to C

X

=

n
 Y

(1 −

en ,...,ei+1
r=i+1
all disjoint to C
n
h Y

= ECP(G,C)

(1 −

r=i+1

|C| 
) PCP (G,C) (F>i = hen , . . . , ei+1 i)
Mr

|C| i
)
Mr

Qn

One difficulty with using Proposition 5.1 and Corollary 5.2 is the fact that the expression r=i+1 (1 −
|C|/Mr ) is a non-linear function of |C| and Mi+1 , . . . , Mn . We often prefer to use a “linearized” potential
function Si that approximates it. For any integer i ≥ 0 we define
c
c
c
Si =
+
+ ··· +
Mi+1
Mi+2
Mn
Heuristically, one may think of Si as counting the expected number of times a min-cut is selected during the
Contraction Algorithm. We have the following simple bound on Si :
Proposition 5.3. For any integer i ∈ [1, n] we have:
Si ≤ 2 log(n/i)
Proof. We have that:
Si =

n
X

Z n
n
X
c
c
2dr
≤
≤
= 2 log(n/i).
M
rc/2
r
r=i c
r=i+1
r=i+1

The next Lemma shows how the potential function Si gives a good approximation to Proposition 5.2.
Lemma 5.4. Let C be a cut of weight αc. For any real number α ≥ 1 and integer i ≥ 2α we have that:
16−α e−αSi ≤

n
Y

(1 −

r=i+1
15

|C|
) ≤ e−αSi
Mr



Proof. The upper bound is easy:
n
n
Pn
Y
Y
αc
αc
αc
)] ≤
e− Mr = e− r=i+1 Mr = e−αSi
(1 −
Mr
r=i+1
r=i+1
To show the lower bound:
n
n
Y
Y
αc
αc 2 
αc
(1 −
e− Mr × 1 −
)≥
Mr
Mr
r=i+1
r=i+1
= e−αSi ×
≥ e−αSi ×
= e−αSi ×

n
Y

r=i+1
n
Y

r=i+1
n
Y

r=i+1

1−
1−
1−

as 1 − x ≥ e−x (1 − x2 ) for x ∈ [0, 1]

αc 2 
Mr

α2 c2 
r2 c2 /4

as Mr ≥ rc/2

4α2 
r2

Q
2
Thus, we need to estimate the expression nr=i+1 (1 − 4α
r 2 ). This is an exercise in calculus:
n
n
 X
Y
4α2 
4α2
log(1 − 2 )
(1 − 2 ) = exp
r
r
r=i+1
r=i+1
Z ∞

4α2
≥ exp
as i ≥ 2α
log(1 − 2 )dr
r
r=2α

4α2
r x
= x→∞
lim exp r log(1 − 2 ) + 4α tanh−1 ( )
r
2α y
+
y→2α

= exp(−2α log 4) = 16−α

which gives us the desired lower bound.



This can be applied to obtain a simple bound for the probability of selecting a given cut C:
Lemma 5.5. Let C be any cut of weight αc. For α′ ≥ α, the probability that the Contraction Algorithm
with parameter α′ selects cut C is at least
′

P(Contraction Algorithm selects cut C) ≥ e−O(α ) ECP (G,C) [e−αS⌈2α⌉ ]

Proof. First, suppose that α′ ≥ n/2. In this case, the Contraction Algorithm simply selects a cut uniformly
′
from G, so that C is selected with probability 2−n−1 = e−O(α ) . Also, observe that S⌈2α⌉ ≤ 0 so that
ECP(G,C) [e−αS⌈2α⌉ ] ≤ 1. So the result holds easily in this case.
Next, suppose that α′ ≤ n/2. By Lemma 5.5, the probability that the cut C survives to the graph G⌈2α′ ⌉
αc
′
is at least 16−α ECP (G,C) [e− c S⌈2α′ ⌉ ].
Next, note that if C survives to G⌈2α′ ⌉ , then as the Contraction Algorithm selects a cut from this graph
′
′
uniformly at random, C is selected with probability 21−⌈2α ⌉ ≥ 2−O(α ) .
′
Overall, the probability that C is selected is at least e−O(α ) ECP (G,C) [e−αS⌈2α⌉ ] as desired.

Note that by Jensen’s inequality,
ECP (G,C) [e−αS⌈2α⌉ ] ≥ exp(−αECP (G,C) [S⌈2α⌉ ]);

thus, to apply Lemma 5.5, it will suffice to compute E[S⌈2α⌉ ]. Also observe that by combining Proposition 5.3
with Lemma 5.4, we get a simple and well-known lower bound on the probability of retaining C that does
not depend on any other properties of G:
Corollary 5.6. The probability that the Contraction Algorithm with parameter α selects a given α-cut C is
at least
−2α
.
P(select C) ≥ e−O(α) n/α
16

Proof. This holds easily when α ≥ n/2. Otherwise,

n

P(select C) ≥ e−O(α) ECP (G,C) [e−αS⌈2α⌉ ] ≥ e−O(α) ECP (G,C) [e−α log( ⌈2α⌉ ) ]
−2α
n
.
≥ e−O(α) ECP (G,C) [e−α log( 2α ) ] = e−O(α) n/α



The cut C affects the dynamics of the Contraction Process, making it more difficult to analyze than the
Contraction Algorithm. The following series of lemmas show how we can “factor out C”. We show that the
Contraction Process for C can be approximated by the Contraction Algorithm on G/L, where L ⊆ C is a
subset of edges from the cut C.
Lemma 5.7. Let C be a cut of a connected graph G and let L a subset of the edges of G. Let Mi be the
edge counts corresponding to the random process CP(G, C) and let Mi′ be the edge counts corresponding to
the random process CP(G/L, C).
Then for r > |L| the random variable Mr stochastically dominates the random variable |L| + Mr−|L|.
Note that C is not necessarily a cut of G/L; we interpret C here only as a set of edges in G/L.
Proof. As described in [8], there is an alternative description of the contraction process for G, C: we select
a random permutation of the edges in G − C. We then process these edges in order, either contracting the
edge or ignoring it if it was already contracted.
With this in mind, consider the following coupling process: given a permutation ρ of the edges e ∈ G − C,
we run respectively the processes CP (G, C) and CP (G/L, C), using the common permutation ρ to order the
relevant edges in both cases. Letting Mi , Mi′ denote the edge counts obtained in the respective processes,
we claim that for a fixed ρ,
′
Mr ≥ Mr−|L|
+ |L|

and this will show our claim.
For a fixed ρ, list the edges of G − C in order of ρ as e1 , e2 , . . . , em−|C|. Observe that both Contraction
Processes successively select these edges in this order, and contract them if they are still present in the graph
(either G or G/L respectively). We say that the process is at stage k if it has processed edges e1 , . . . , ek in
order.
Suppose that when this process is at stage k, then the graph G has reduced to r vertices and contains
s edges of L. Then G/L at this stage must have r′ ≥ r − s vertices, as it has at most s additional edges
contracted away. Also note that every edge in G/L at stage k also remains in graph G, and in addition G
has s edges which are not present for G/L. Hence
′
+s
Mr ≥ Mr′ + s ≥ Mr−s

Next, note that every time the number of vertices is decreased by one in the process, so too must the
number of edges be reduced by at least one. Hence
′
′
′
+ |L|.
Mr−s
+ s ≥ Mr−s−1
+ s + 1 ≥ · · · ≥ Mr−|L|

and our claim is proved.



Corollary 5.8. Let C be any cut of G, and L ⊆ C a subset of the edges of C. Then for any integers
j ≥ i ≥ 1 we have
|L| + j
)
ECP(G,C) [Si ] ≤ ECP(G/L,C)[Sj ] + 2 log(
i
Proof. As Mr ≥ rc/2 for all r, we have
j+|L|

ECP(G,C) [Si ] ≤ ECP(G,C) [Sj+|L| ] +
≤

n
X

r=j+|L|+1

c
rc/2
r=i+1

ECP(G,C) [
17

X

|L| + j
c
] + 2 log(
)
Mr
i

′
For each r, the random variable Mr stochastically dominates the random variable |L| + Mr−|L|
, where Mi′
c
denote the edge counts under CP(G/L, C). This implies that ECP(G,C) [ Mr ] ≤ ECP(G/L,C)[ |L|+Mc r−|L| ] ≤
c
ECP(G/L,C)[ Mr−|L|
] and so:

ECP(G,C) [Si ] ≤

n
X

r=j+|L|+1

ECP(G/L,C)[

n−|L|

=

X

r=j+1

ECP(G/L,C)[

c
Mr−|L|

] + 2 log(

|L| + j
)
i

|L| + j
c
] + 2 log(
)
Mr
i

≤ ECP(G/L,C) [Sj ] + 2 log(

|L| + j
)
i


To illustrate how we can use these results, suppose we are interested in the contraction process for C,
where C contains very few edges. In this case, if we apply Corollary 5.8 with L = C and i = j = ⌈2α⌉, then
we would have
|C|
)
ECP(G,C) [S⌈2α⌉ ] ≤ ECP(G/C,C) [S⌈2α⌉ ] + 2 log(1 +
⌈2α⌉
However, note that CP(G/C, C) is equivalent to CA(G/C). Also, observe that as |C| is small then
2 log(1 + |C|
2α ) ≈ 0. Thus,
ECP(G,C) [S⌈2α⌉ ] . ECA(G/C) [S⌈2α⌉ ]
We have thus completely factored out C — we have reduced the analysis of the Contraction Process for
C to the behavior of the Contraction Algorithm on a (slightly smaller) graph.
We note that the choice of parameters L = C, i = j = ⌈2α⌉ for Corollary 5.8 was only for illustrative
purposes, and is not optimal. When we apply this Corollary later, we will choose other parameters which
lead to stronger, but more complicated, estimates.
6. Bounds for small, odd c
Our ultimate goal for this algorithm is show that the reliability of a graph influences the number of cuts
it can have. As a warm-up exercise, we will show that graphs with connectivity c, where c is a small odd
number, have noticeably fewer α-cuts than the worst case (where c is even and the graph is a cycle with
each edge having multiplicity c/2). This section is not needed for our main algorithm, and can be
skipped if desired.
We use the following fact about the minimum cuts of G, when c is odd. This is shown in [2], [3]:
Proposition 6.1. Suppose G has minimum cut c, for c odd. Then G has at most 2n min-cuts, which are
represented by the edges of a spanning tree of G.
This is actually the only place we use the fact that c is odd; in fact, our result is true for any graph G
which has ≤ 2n min-cuts (or a similar result could be shown for a graph with O(n) min-cuts).
Although our goal is to analyze the Contraction Process for a target cut C, it will suffice to analyze the
unconditioned Contraction Algorithm. The basic strategy of this proof is use induction on the number of
vertices to show a bound on ECA(G) [Si ]. We will need to track the behavior of Si not only for the original
graph G, but for subgraphs Gr which arise during the evolution of the Contraction Algorithm. The formal
induction proof by itself is not very intuitive, because it requires guessing a bound on E[Si ] and then proving
that this bound is correct. So we will give an intuitive and non-rigorous derivation of the proof.
Consider
Qnany min-cut C (not the target cut). By Corollary 5.2, it survives to Gi with probability
ECP(G,C) [ r=i+1 (1 − c/Mr )] ≤ ECP(G,C) [e−Si ]. Now, suppose that we ignore the distinction between
CP(G, C) and CA(G) (the two processes should be almost the same, because C affects only a small part of
the graph); in this case, we can approximate that C survives to Gi with probability roughly ECA(G) e−Si .
As this is true for any min-cut, the expected number of min-cuts Ki remaining in Gi should be about
E[Ki ] ≈ k exp(−E[Si ])

where we are being deliberately vague about the scope of the expectation.
18

Now the neighborhood of each vertex of Gi defines a cut. As Gi has Ki min-cuts, this implies that at
most Ki vertices may have the minimum degree c, while the others must have degree at least c + 1, so that
Mi ≥ Ki c/2 + (i − Ki )(c + 1)/2
We have a bound on the expected value of the random variable Ki . It will turn out that, given this fixed
value of E[Ki ], the worst case distribution on Ki is that either Ki = 0 or Ki = i (the latter occurring with
probability E[Ki ]/i). In this case,
E[c/Mi ] ≤

E[Ki ] c
E[Ki ]
c
2(ic + E[Ki ])
+ (1 −
)
=
i ic/2
i
i(c + 1)/2
(c + 1)i2

This gives us a recurrence relation in Si :
X
c
c
E[Si−1 ] =
E[
] = E[Si ] + E[
]
Mj
Mi
j≥i

≈ E[Si ] +

2(ic + ke−E[Si ] )
2(ic + E[Ki ])
≈
E[S
]
+
i
(c + 1)i2
(c + 1)i2

We relax this recurrence relation to a differential equation
dE[Si ]
2(ke−E[Si ] + ci)
=−
di
(c + 1)i2
E[Sn ] = 0
which can be solved in closed form to obtain
2
−1
h (i/n) c+1
(2k + (c − 1)n) − 2k i
E[Si ] = log
(c − 1)i

This derivation makes a number of unwarranted independence and monotonicity assumptions on the
behavior of the random variables, which do not hold in general. However, as we will see, this argument does
accurately capture the worst-case behavior for all the random variables. That is, even though the random
variables are not independent, any dependency would only give us better bounds.
In the following theorem, we carry out the high-level approach discussed in Section 1.2 and prove that
our heuristic formula is in fact a correct bound:
Theorem 6.2. Let c > 1. Define the function
2
−1
h (i/n) c+1
(2k + (c − 1)n) − 2k i
f (i, n, k) = log
(c − 1)i

Suppose G is a graph with n vertices and a minimum cut weight of c. Suppose that G has at most k mincuts, where k is an integer in the range 0 ≤ k ≤ 2n. Then for 3 ≤ i ≤ n we have that ECA(G) [Si ] ≤ f (i, n, k).
Proof. For simplicity, we will defer some technical analysis of the function f to Appendix A.
First, note that by Proposition A.1, the function f is well-defined.
We induct on n. When n = i, we have Si = 0 = f (i, n, k).
Now suppose n ≥ i + 1, and G has m edges and k ≤ 2n cuts of weight c. In the first step of the
Contraction Algorithm, we select an edge of G to contract, arriving at a new graph G′ . So ECA(G) [Si ] =
c/m + EG′ ECA(G′ ) [Si ]. We have broken the expectation into two components. First, we randomly select the
next subgraph G′ ; then, we continue the Contraction Algorithm on that subgraph.
The graph G′ has n − 1 vertices and has K ′ ≤ 2(n − 1) min-cuts, where K ′ is a random variable. Each
min-cut survives to H with probability (1 − c/m), and so E[K ′ ] ≤ k(1 − c/m) ≤ ke−c/m .
By the inductive hypothesis,
ECA(G′ ) [Si ] ≤ f (i, n − 1, K ′ )
By Proposition A.2, this is a concave-down increasing function of K ′ , hence by Jensen’s inequality
ECA(G′ ) [Si ] ≤ f (i, n − 1, ke−c/m)
and hence
ECA(G) [Si ] ≤ c/m + f (i, n − 1, ke−c/m )
19

The neighborhood of each vertex of G defines a cut, and for n ≥ 3 these are all distinct. Hence at most
k vertices may have the minimum degree c, while the others must have degree at least c + 1.
First suppose k ≤ n. That implies that
m ≥ nc/2 + (n − k)/2
By Proposition A.3, the expression c/m + f (i, n − 1, ke−c/m) is decreasing in m. Then we have the bound
c
c
ECA(G) [Si ] ≤
+ f (i, n − 1, ke− nc/2+(n−k)/2 )
nc/2 + (n − k)/2
≤ f (i, n, k)
by Proposition A.4.
Suppose k ≥ n. Then m ≥ nc/2, so we have the bound
c
c
ECA(G) [Si ] ≤
+ f (i, n − 1, ke− nc/2 )
nc/2
≤ f (i, n, k)
by Proposition A.5.
This completes the induction.



The function
 f is technically not defined at c = 1. However, it approaches the limit f (i, n, k) = log (n/i)+
(k/i) log(n/i) , and this function has similar properties to the case when c > 1. We omit the full analysis of
the case when c = 1, as it is essentially identical to Theorem 6.2. For that case, we obtain the result:
Proposition 6.3. Suppose G is a graph with n vertices and c = 1, and with k ≤ n weight-one cuts (aka
bridges). Then for n ≥ i ≥ 1 we have
h
i
ECA(G) [Si ] ≤ log (n/i) + (k/i) log(n/i)
Lemma 6.4. Suppose G has minimum cut c, for c odd. Then for any integers 1 ≤ i ≤ n we have
E[Si ] ≤

2c
log(n/i) + O(1)
c+1

Proof. Observe that S1 ≤ S3 + O(1), so it suffices to show this for 3 ≤ i ≤ n. Suppose that the graph G has
n vertices and k ≤ 2n cuts of weight c. If c ≥ 3, then by Theorem 6.2 we have
ECA(G) [Si ] ≤ f (i, n, 2n)
= log

2

(c + 3)(n/i)2− c+1 − 4(n/i)
(c − 1)

2
= (2 −
) log(n/i) + log
c+1
2c
log(n/i) + O(1)
c+1
A similar proof, using Proposition 6.3, applies when c = 1.

!
2

(c + 3) − 4(i/n)1− c+1
(c − 1)

!

=



We can now estimate the probability of selecting the α-cut C:
Theorem 6.5. Suppose c is odd and C is an α-cut. Then the Contraction Algorithm with parameter α
c
selects C with probability Ω(n−2α c+1 ).
Proof. First, suppose n ≥ αc2 (which is the most interesting and difficult case). We then apply Corollary 5.8
with L = C, j = ⌈αc2 ⌉:

αc + ⌈αc2 ⌉
)
2α
c(c + 1)
≤ ECA(G/C) [S⌈αc2 ⌉ ] + 2 log(
)+1
2
where here we note that CP(G/C, C) = CA(G/C).
ECP(G,C) [S⌈2α⌉ ] ≤ ECP(G/C,C) [S⌈αc2 ⌉ ] + 2 log(

20

Let r be the number of vertices in G/C. Applying Lemma 6.4:
2c
r
2c
n
ECA(G/C) [S⌈αc2 ⌉ ] ≤ max(0,
log(
)) + O(1) ≤
log( 2 ) + O(1)
c+1
⌈αc2 ⌉
c+1
αc
So
c(c + 1)
n
2c
log( 2 ) + 2 log(
) + O(1)
ECP(G,C) [S⌈2α⌉ ] ≤
c+1
αc
2

2c
4c
=
log n − Ω(log α) −
log c + 2 log c(c + 1) + O(1)
c+1
c+1
2c
≤
log n − Ω(log α) + O(1)
c+1
By Lemma 5.5, the probability of selecting C is bounded by:
P(Contraction Algorithm selects C) ≥ exp(−O(α) − αECP(G,C) [S⌈2α⌉ ])
2c
≥ exp(−O(α) −
α log n + Ω(α log α))
c+1
2c

≥ Ω(n− c+1 α )

To finish the proof, we need to deal with the cases in which n is small. When n ≤ 2α, then observe that
c
cut C is selected with probability exactly 21−n ≥ Ω(n−2α c+1 ). Next suppose that 2α < n < αc2 . Then we
apply Corollary 5.6, which does not take account of the fact that c is odd:
2α
2c
2α
2c
n −2α
≥ n−α c+1 e−O(α) n− c+1 α2α ≥ n−α c+1 e−O(α) (αc2 )− c+1 α2α
P(Select C) ≥ e−O(α) (
α
2c
as c ≥ 1
≥ n−α c+1 e−O(α) (c1/(c+1) )−4α αα
2c

≥ n−α c+1 e−O(α) αα
2c

≥ Ω(n−α c+1 )

as x−1/(x+1) ≥ Ω(1) for x ≥ 1



The following example shows that we cannot achieve any probability of the form n
2c
constant with x < c+1
:

−αx

where x is a

Observation 6.6. Let c be odd, and let α =k c+1
2c with k an integer and α ≤ 2n. Then there is a graph G
2c
n c+1
whose min-cut has weight c and which has Ω ( 2α ) α distinct α-cuts.

Proof. Consider a cycle graph consisting of bundles of (c + 1)/2 edges between each adjacent pair of vertices,
except for one edge bundle of (c − 1)/2 edges. This graph has minimum cut c. Suppose we select any k
edge-bundles which use the (c + 1)/2 edges to fail. This gives a cut of weight k(c + 1)/2, which is k c+1
2c times

the minimum cut as indicated. There are n−1
such
choices,
so
the
total
number
of
such
α-cuts
is
at least
k

 

 n 2c 
n−1
n−1
=
= Ω ( ) c+1 α
2αc
2α
k
c+1


7. The effects of graph reliability on the Contraction Algorithm
We now show how the graph reliability affects the behavior of the Contraction Algorithm. Our goal in
this section is to obtain a quantitative form of the following simple relationship: a graph which has high
reliability will have fewer α-cuts than the cycle graph, for any value of α ≥ 1. The key to this is to draw a
connection between Z̄ (the expected number of failed cuts) and the behavior of the Contraction Algorithm.
If Z̄ is large (say as large as n2 pc ), then the graph G could be essentially like the cycle graph, in which
case Karger’s analysis of the Contraction Algorithm would be tight. However, when Z̄ is small, then the
graphs encountered during the Contraction Algorithm have more edges which implies that any target cut C
is retained with higher probability.
In this section, we will assume U (p) < n−K for some constant K; thus the conclusions of
Proposition 3.6 hold.
21

Throughout this section, we recall that
pc = n−2−δ

Z̄ = n−2−δ+β

and that δ ≥ δ0 > 0, where δ0 is an arbitrarily small constant.
We begin with a warm-up exercise, which will illustrate some of the ideas in the proof. We then discuss
how this simple proof falls short and how to improve it, at the cost of greater complexity.
Proposition 7.1. Define


2(2 + δ)(log(3 − β + δ) − log(2 − β + δ + x))
h(x) = 2(2 + δ)(log(3 − β + δ) − log(2 + δ)) + 2(β − x)


2(1 − x)
Then for any integer i ∈ [2, n] we have

if x ≥ β
if x < β ≤ 1
if β ≥ 1

log i 
log n
log n
Here, x should be thought of as a parameter which measures how far along we are in the contraction
process: x = 1 is the beginning of the process, while x = o(1) is the end.
Si ≤ h

Before we give the proof, we give a more intuitive description of the somewhat mysterious function h(x).
Suppose that we run the Contraction Algorithm starting at the original graph, but terminate it after reaching
a subgraph with nx vertices (instead of running it all the way to a graph with 2α vertices). The probability
that the cut C survives to Gnx is roughly n−αh(x) . So when x = 1, then h(x) = 0 and this makes sense
because the cut C survives with probability one. If we assume that α is a small constant, then we terminate
the algorithm at x ≈ 0 and so the cut C survives with probability n−αh(0) ; this is essentially the probability
that the cut C is actually selected by the Contraction Algorithm.
log i
Proof. Let x = log
n . For β ≥ 1, this is simply Proposition 5.3.
Let us next consider the case β ≤ x ≤ 1. Consider the subgraph Gr during during the Contraction
Algorithm for r > i. As r ≥ 3, the neighborhood of each vertex v determines a distinct cut of Gr with
weight dv , where dv is the degree of v. As all the cuts of Gr are cuts of G as well, we must have
X
X
pd v ≤
p|C| = Z̄
v

Now note that rp

P

v dv
r

≤

P

v

C a cut of G

pdv , hence rp2Mr /r ≤ Z̄, which in turn implies that
Mr ≥

r log(Z̄/r)
2 log p

Hence
Si ≤

n
X

2c log p
≤
r log(Z̄/r)
r=i+1

Z

n
r=i

2c log p
dr = −2c log p(log log(r/Z̄))
r log(Z̄/r)

n
r=nx

= 2(2 + δ) log n(log(3 − β + δ) − log(2 − β + δ + x))
= h(x) log n

A similar calculation applies in the case x ≤ β.



This simple proof demonstrates the effect of the graph reliability on the behavior of the Contraction
Algorithm. In fact, this Proposition 7.1 is already sufficient to obtain a substantially improved run-time
compared to Karger’s algorithm. We will also need this Proposition 7.1 for technical reasons later in this
paper.
However, Proposition 7.1 is not tight, because it assumes that the value of Z̄ does not change during the
execution of the Contraction Algorithm. But in fact, most of the cuts in the graph are being contracted
away, so Z̄ should be decreasing rapidly.
We will track this behavior in terms of a parameter which is slightly more general than Z̄. Suppose we
are given a target α-cut C. For any contraction subgraph H, we define the associated graph parameter
X
′
e−γ(|C −C|)/c
(1)
AH
γ =
cuts C ′ of H
22

This is the expected number of failed cuts of H, if all the edges in C fail and all the edges outside C fail
independently with probability e−γ/c. Be aware that C may not be a cut of the graph H (if some edges of
C were contracted); in (1), one should interpret C as a collection of edges which survive in H.
Proposition 7.2 shows how the parameter A changes over the course of a Contraction Process.
Proposition 7.2. Suppose that C is a cut of G, and L is a subset of the edges of C. Suppose that H is
a contraction-subgraph of G with m edges. Let H ′ denote the graph obtained from H by one step of the
Contraction Process for L (that is, selecting an edge of H − L uniformly at random and contracting it.)
Then
′

H
E[AH
γ−c/m ] ≤ Aγ

Proof. Consider some cut C ′ . In a single iteration of the contraction process, we select an edge of G − L
uniformly at random. There are |E(H) − L| such edges, hence we select an edge of C ′ − L with probability
|C ′ −L|
′
|E(H)−L| . So the probability of retaining C is
P(retain C ′ ) ≤ 1 −

|C ′ − L|
|C ′ − C|
|C ′ − C|
≤1−
≤ exp(−
)
|E(H) − L|
m
m
′

′

|C −C|
The contribution of C ′ to AH
) if C ′ is retained, and is zero otherwise. Summing
γ−c/m is exp(−(γ −c/m)
c
over all such C ′ :
X
′
|C ′ − C|
|C ′ − C|
) exp(−
)
E[AH
exp(−(γ − c/m)
γ−c/m ] ≤
c
m
C′
X
|C ′ − C|
) = AH
=
exp(−γ
γ
c
′
C


Our strategy here is to guess a formula for E[Si ] in terms of various parameters, and then prove it true
by an induction. The induction proof is not informative on its own, so we give a heuristic derivation of our
formula. This amounts to estimating Mr for the various stages of the Contraction Process for C. In this
discussion, we ignore any considerations of the fact that Si is a random variable, and we treat it as essentially
deterministic.
Suppose that
cuts of P
G, other than the target cut C, have negligible overlap with C. In this case,
P the
C′
|C ′ −C|
= Z̄. Also, applying Proposition 7.2 multiple times, and ignoring all
p
≈
AG
=
′
c
C′ p
C
− log(p )
distinctions between expected value and actual values for the variables and all variable dependencies, we
have that for the graph Gi :
Gi
G
i
AG
− log(pc )−Si = A−(log pc )−c/Mi+1 −c/Mi+2 +···−c/Mn ≤ A−(log pc ) = Z̄

Now suppose that in Gi , each vertex has degree d. Since the neighborhood of each vertex of Gi defines a
distinct cut, and these cuts are all assumed to be nearly disjoint from C,
X

i
exp (c log p + Si )d/c ≤ AG
− log(pc )+Si = Z̄
v

Which implies

d≥

c log(Z̄/i)
Si + c log p

and hence
Mi = id/2 ≥

ic/2 log(Z̄/i)
Si + c log p

Thus we have a recurrence relation in Si :
Si−1 = Si + c/Mi ≤ Si +
23

2(c log p + Si )
i log(Z̄/i)

We relax this to a differential equation
dSi
2(Si + c log p)
=−
di
i log(Z/ī)
Sn = 0
which can be solved in closed form to obtain

log2 (Z̄/i) 
Si = (− log(pc )) 1 −
log2 (Z̄/n)
This derivation is completely non-rigorous, as it makes a number of unwarranted independence and monotonicity assumptions. However, as we will see, all of these assumptions turn out to be the worst-case behavior.
Hence the above bound is essentially correct.
As in Section 6, we will use this bound as the basis of an induction argument. However, the situation is
more complicated because of the way we must transform the contraction process for C into an unconditioned
contraction algorithm. In Section 6, we handled this by applying Lemma 5.7 with L = C. This worked
because C was small compared to n. We cannot assume this here; instead, we will define L to be a small
random subset of the edges of C. This will remove the influence of C from cuts C ′ which heavily overlap
C. We will show that in fact the worst-case behavior of the contraction process comes about when all other
cuts of G have negligible overlap with C; in that case, we can essentially ignore C.
Lemma 7.3. There is a subset of the edges L ⊆ C with the following properties:
(1) |L| ≤ ⌈α(2 + δ) log n⌉
G/L
(2) A− log(pc ) ≤ Z̄
G/L

(We can interpret this as follows. The parameter A− log(pc ) counts the expected number of failed cuts,
given that all edges in L are retained and all edges in C − L are removed and all other edges fail randomly
with probability p)
Proof. Choose L to be a random subset of C of size exactly x = ⌈α(2 + δ) log n⌉. (If this number is larger
than the number of edges in C, we simply set L = C, in which case the lemma is trivially true.) Now consider
G/L
the contribution of some cut C ′ to A− log(pc ) . If L contains some edge in C ∩ C ′ , then C ′ contributes zero;
′

else it contributes p|C −C| .
So, supposing that |C ∩ C ′ | = sc, we have:
G/L

E[Contribution of cut C ′ to A− log(pc ) ] = p|C

′

|−sc

P(C ′ ∩ L = ∅)

αc−sc
|C ′ | −sc
x
≤p p
αc
x

(αc − sc)(αc − sc − 1) . . . (αc − sc − (x − 1))
= p|C | p−sc
(αc)(αc − 1) . . . (αc − (x − 1))
′
s
|C ′ | −sc αc − sc x
≤p p (
) = p|C | n(2+δ)s (1 − )x
αc
α
′
′
s
≤ p|C | ns(2+δ) e− α α(2+δ) log n = p|C |
P
′
G/L
Thus, summing over all C ′ , we have E[A− log(pc ) ] ≤ C ′ p|C | = Z̄. In particular, there exists some subset
′

G/L

L with A− log(pc ) ≤ Z̄.



We are now ready to introduce the main induction argument:
Theorem 7.4. Define the function
f (i, r, a, γ) =

( 
γ 1−

log2 (a/i)
log2 (a/r)

2 log(r/i)



if a ∈ (0, 1]

if a > 1

Fix a graph G and a target cut C of G, and let H be a contraction-subgraph of G with r vertices. Let γ
be a real number in the range [2 log r, ∞) and let i, r be integers with 100 ≤ i ≤ r ≤ n. Then
ECP(H,C) [Si ] ≤ f (i, r, AH
γ , γ)
24

We emphasize here that C is not necessarily a cut of H; in the expression CP(H, C) and AH , we view C
simply as a subset of the edges of H.
Proof. We defer the proof of some technical properties of f to Appendix B, for sake of clarity.
We induct on r. When r = i, we have Si = f (i, r, a, γ) = 0.
Now suppose r ≥ i + 1, and H has m edges with AH
γ = a. We may assume that a ≤ 1, as otherwise this
follows immediately from Proposition 5.3.
So ECP(H,C) [Si ] = c/m + EH ′ ECP(H ′ ,C) [Si ]. We have broken the expectation into two components: first,
we select an edge e of H − C to contract, leading to the graph H ′ = H/e; second, we continue the contraction
process on the subgraph H ′ , which has r − 1 vertices.
Note that m ≥ rc/2, so γ − c/m ≥ 2 log r − 2/r ≥ 2 log(r − 1). So the induction hypothesis applies to the
graph H ′ with γ ′ = γ − c/m giving


′
ECP(H,C) ≤ c/m + EH ′ f (i, r − 1, AH
γ−c/m , γ − c/m) .
′

By Proposition 7.2, we have EH ′ [AH
γ−c/m ] ≤ a. So by Proposition B.1,

ECP(H,C) ≤ c/m + f (i, r − 1, a, γ − c/m).
We will now bound the number of edges m of the graph H. For each vertex v ∈ H, let dv be the number
of incident edges not including the edges of C. Each vertex then corresponds to a cut which has dv edges
outside C, and as r ≥ 3 these cuts are all distinct. So
X
exp(−γdj /c) ≤ AH
γ = a.
v∈H

By the arithmetic mean-geometric mean (AM-GM) inequality,
P
Y
1/r
X
−γ v dj
)
exp(−γdj /c) ≥ r
(exp(−γdj /c))
= r exp(
rc
v
v∈H

≥ r exp(

−γ(m/2)
)
rc

as m ≥

This implies that
m≥

X

dv /2 and γ > 0

v

rc log(a/r)
−2γ

By Proposition B.2, the quantity c/m + f (i, r − 1, a, γ − c/m) is decreasing in m. Hence
2γ
−2γ
+ f (i, r − 1, a, γ +
)
r log(a/r)
r log(a/r)
≤ f (i, r, a, γ)
by Proposition B.3

ECP(H,C) [Si ] ≤


We use this to estimate the probability ECP(G,C) [Si ] for a target cut C.
Theorem 7.5. Define the function h̄ : [0, 1] → R+ by
h̄(x) =

(δ + 2)(1 − x)(5 − 2β + 2δ + x)
(3 − β + δ)2

Let C be an α-cut of G, and let i be an integer in the range i = ⌈2α⌉, . . . , n. Then
ECP(G,C) [Si ] ≤ h̄

log i 
log n + O(log log n)
log n

(The function h̄ has the same interpretation as h, however h̄(x) is (typically) smaller than h(x) and
so it provides a tighter bound on the probability of the cut C surviving (partially) through the Contraction
Algorithm.)
25

log i
Proof. Let x = log
n , so x ∈ [0, 1].
If δ ≥ log n, the Proposition 5.3 gives Si ≤ 2 log(n/i) = (2 − 2x) log n. One may verify that (2 − 2x) ≤
h̄(x) + 3/δ. This implies that Si ≤ (h̄(x) + log3 n ) log n ≤ h̄(x) log n + O(1) and we are done.1
So we may assume that δ < log n for the remainder.
G/L
Let L ⊆ C be as given by Lemma 7.3, so that A− log(pc ) ≤ Z̄ and L ≤ ⌈α(2 + δ) log n⌉ ≤ O(α log2 n). Let
H = G/L, and suppose that H has r ≤ n vertices. There are now two cases depending on the size of r, i.
In the first (and most important) case, suppose that r ≥ i + 100. Then we apply Corollary 5.8 with
j = i + 100:

|L| + i + 100
)
i
|L| + i + 100
c
≤ f (j, r, AH
)
by Theorem 7.4, as r ≥ j ≥ 100
− log(pc ) , − log(p )) + 2 log(
i
c
≤ f (j, r, AH
as i ≥ 2α, |L| ≤ ⌈α(2 + δ) log n⌉ ≤ O(α log2 n)
− log(pc ) , − log(p )) + O(log log n)

ECP(G,C) [Si ] ≤ ECP(H,C) [Sj ] + 2 log(

Simple inspection shows that f (k, ℓ, a, γ) is a decreasing function of k and an increasing function of ℓ.
c
H
c
Thus f (j, r, AH
− log(pc ) , − log(p )) ≤ f (i, n, A− log(pc ) , − log(p )). Furthermore, using Proposition B.1 and the
H
H
fact that A− log(pc ) ≤ Z̄ ≤ 1, we have that f (i, n, A− log(pc ) , − log(pc )) ≤ f (i, n, Z̄, − log(pc )). So
ECP(G,C) [Si ] ≤ f (i, n, Z̄, − log(pc )) + O(log log n)
Now substitute i = nx , Z̄ = n−2−δ+β , pc = n−2−δ , and observe that f (i, n, Z̄, − log(pc )) = h̄(x) log n.
The next case is when r < i + 100. We apply Corollary 5.8 with j = i:
ECP(G,C) [Si ] ≤ ECP(H,C) [Si ] + 2 log(

|L| + i
) ≤ 2 log(r/i) + 2 log(1 + |L|/i)
i

i + 100
) + O(log log n)
as i ≥ 2α, |L| ≤ ⌈α(2 + δ) log n⌉ ≤ O(α log2 n)
i
≤ O(log log n) ≤ h̄(x) log n + O(log log n)
≤ 2 log(


Our next result introduces an important parameter h̄(0). Essentially, h̄(0) measures the rate of decay of
the number of α-cuts. If we make no assumptions about the graph reliability, then the number of α-cuts
may be as large as n2α . When we take the reliability of G into account, we show that instead the number
of α-cuts is like nh̄(0)α . Crucially, barring some exceptional cases, we have h̄(0) < 2.
Corollary 7.6. For α ∈ [1, n/2] we have
ECP(G,C) [S⌈2α⌉ ] ≤ h̄(0) log n + O(log log n) − Ω(log α)
Proof. We have
log⌈2α⌉
) log n + O(log log n)
by Theorem 7.5
log n
Z log⌈2α⌉
log n
= h̄(0) log n + log n
h̄′ (x)dx + O(log log n)

E[S⌈2α⌉ ] ≤ h̄(

x=0

log⌈2α⌉
× Ω(1) + O(log log n)
log n
= h̄(0) log n − Ω(log α) + O(log log n)

≤ h̄(0) log n − log n ×

by Proposition D.3


1Observe that h̄(x) is a rational function of the parameters β, δ, x, the coefficients of which are rational numbers. Thus, the

statement that (2 − 2x) ≤ h̄(x) + 3/δ for β, δ, x in the appropriate range is equivalent to a first-order sentence in the theory of
real-closed fields. A classical result of Tarski is that the theory of real-closed fields is decidable; many symbolic algebra packages
have implemented practical algorithms for this. We used the Mathematica function Reduce which implements these algorithms
to check that this inequality holds. For the remainder of the paper, whenever we refer to mechanically checking an inequality,
we mean that employ the Mathematica software package which proves that it is a validity.
26

Corollary 7.7. The Contraction Algorithm with parameter α outputs any given α-cut with probability at
least n−αh̄(0) log−O(α) n. In particular, the number of such cuts is at most nαh̄(0) logO(α) n.
Proof. If n ≤ 2α, then C is selected with probability exactly 21−n ≥ Ω(n−α ); by Proposition D.1, h̄(0) ≥ 10/9
so this is ≥ n−αh̄(0) .
Otherwise, by Lemma 5.5, the probability of selecting any given α-cut C is at least
P(select C) ≥ exp(−O(α) − αECP(G,C) [S⌈2α⌉ ]).

By Corollary 7.6 this is at least exp(−O(α)) exp(Ω(α log α))n−αh̄(0) log−O(α) n ≥ n−αh̄(0) log−O(α) n.



8. Bounds on α∗
In this section, we will assume U (p) < n−K for some constant K; thus the conclusions of
Proposition 3.6 hold.
Recall that the approach of [8] is to show that most unreliability is due to the failure of a small cut. We
can use our bound on the number of cuts to estimate this more precisely than Theorem 2.5.
Proposition 8.1. Define Uα (p) to be the probability that some cut of weight ≤ αc fails. Then for all α ≥ 1
we have the bounds
U (p) − Uα (p) ≤ nα(h̄(0)−2−δ) logO(α) n

U (p) − Uα (p) ≤ O(n−αδ )
Proof. We have

U (p) − Uα (p) = P(Some cut of weight > αc fails and no cut of weight ≤ αc fails)
≤ P(Some cut of weight > αc fails)

By Corollary 2.4, this is at most O(n−αδ ), thus proving the second bound. If h̄(0) ≥ 2, then n−αδ ≤
n
and we automatically prove the first bound as well.
So we may suppose that h̄(0) ≥ 2. Then we estimate this by the union bound
X
p|C|
P(Some cut of weight > αc fails) ≤
α(h̄(0)−2−δ)

|C|>αc

Proposition 7.7 states that the number of cuts of weight xc is at most F (x) = nh̄(0)x logO(x) n. Hence we
may apply Proposition 2.2: this sum is bounded by
Z ∞
X
|C|
αc
pxc F ′ (x)dx
p ≤ F (α)p +
x=α

C:|C|>αc

=n

h(0)α α(−2−δ)

n

log

O(α)

n+

Z

∞

nx(−2−δ) nh̄(0)x (logO(x) n)(h̄(0) log n + O(log log n))dx

x=α

≤ nα(h̄(0)−2−δ) logO(α) n

for h̄(0) ≤ 2 and δ ≥ δ0 > 0


As in Karger [8], we estimate U (p) by examining only the smallest cuts. We define α∗ to be the minimal
value of α such that
U (p)(1 − ǫ) ≤ Uα∗ (p) ≤ U (p)
The parameter α∗ plays a crucial role in the analysis. We can estimate U (p) to the desired relative error
by estimating Uα∗ (p), which we can do by enumerating all the α∗ -cuts. This is a relatively small collection,
which we can explicitly collect and list.
For the rest of the paper, we define
(2)

ρ = log(1/ǫ)/ log n.

Although in general we allow ρ to increase arbitrarily, we find that these bounds can become confusing
because of the interplay between the asymptotic growth of n and ǫ. One can get most of the intuition behind
these results by restricting attention to the case ρ = O(1).
27

Using our improved bounds on the Contraction Algorithm, we tighten Theorem 2.5.
Lemma 8.2. We have
α∗ ≤
If β ≤ 3/2, then we have
α∗ ≤

2−β+δ+ρ
1
+ O(
)
δ
log n

(1 + ρ) log log n
(3 − β + δ)2 (2 − β + δ + ρ)
+ O(
)
(2 − β + δ)2 (2 + δ)
log n

Proof. The first bound is easier. As shown in Proposition 8.1, the absolute error introduced by ignoring cuts
of weight ≥ αc is U (p) − Uα (p) = O(n−αδ ). So the relative error is at most
Rel Err = O
=O

n−αδ) 
U (p)
n−αδ 

by Proposition 3.5

Z̄

≤ Cn−αδ n2+δ−β

for some constant C

log n
= 2−β+δ+ρ
+ O( log1 n ).
Elementary algebra shows that this is ≤ ǫ for α ≥ log C−log ǫ+(2−β+δ)
δ log n
δ
Next let us consider the case when β ≤ 3/2. By Proposition D.1 this implies h̄(0) ≤ 2. As shown
in Proposition 8.1, the absolute error introduced by ignoring cuts of weight ≥ αc is U (p) − Uα (p) =
nα(h̄(0)−2−δ) logO(α) n. So the relative error is at most

Rel Err = O
=O

nα(h̄(0)−2−δ) logO(α) n 
U (p)
α(h̄(0)−2−δ)
n
logO(α) n 

Z̄
α(h̄(0)−2−δ) 2+δ−β
=n
n
logO(α) n

Set α =

ρ+2−β+δ
2+δ−h̄(0)

+

φ(1+ρ) log log n
,
log n

δ > δ0 > 0 and h̄(0) ≤ 2.

where φ is some constant be specified. Note that α ≤ O(1 + ρ), as

Rel Err ≤ n−(ρ+2−β+δ) n
≤ n−ρ−Ω(

φ(1+ρ) log log n(h̄(0)−2−δ)
log n

φ(1+ρ) log log n
)
log n

−Ω(φ(1+ρ))

= ǫ(log n)
≤ǫ

by Proposition 3.5

(log n)O(1+ρ)
O(1+ρ)

(log n)O(α)
as δ ≥ β and α ≤ O(1 + ρ)

(log n)

for φ a sufficiently large constant

So
α∗ ≤
in this case.

(1 + ρ) log log n
(3 − β + δ)2 (2 − β + δ + ρ)
(1 + ρ) log log n
ρ+2−β+δ
+ O(
)=
+ O(
)
log n
(2 − β + δ)2 (2 + δ)
log n
2 + δ − h̄(0)


If we only want a very crude estimate for α∗ we can use the following, which holds irrespective of the
precise value of K, β, δ:
Corollary 8.3. We have α∗ ≤ O(1 + ρ)
Proof. By Proposition 3.6, δ ≥ K − 2 > 0 and δ ≥ β for n sufficiently large.
By Lemma 8.2,
α∗ ≤

1
2−β+δ+ρ
+ O(
)
δ
log n

The restrictions δ ≥ δ0 > 0 and δ ≥ β ensures that this is O(1 + ρ).
28



Remark: In light of Corollary 8.3, it will be convenient to define a term α∗max , which is a computable
upper bound of α∗ and which satisfies α∗max ≤ O(1 + ρ). The precise value of the constant term here will
not be relevant.
It is tempting to simply modify Karger’s original algorithm, using this improved estimate for α∗ in place
of Karger’s estimate. We cannot do this directly, as this estimate depends on the parameter β which we
cannot simply compute.
One approach would be to estimate α∗ using a worst-case estimate for β. This would give usable and tighter
bound than Karger’s. For example, suppose that we use Monte Carlo estimation when U (p) ≥ n−2.73 and cutenumeration when U (p) < n−2.73 . Some simple analysis (which we omit here) shows that α∗ ≤ 1.87 + O(ρ)
whenever U (p) < n−2.73 . using Karger’s algorithm for the remainder, this would give us a total runtime of
n3.73 ǫ−O(1) .
This is good, but we will take another approach which will allow us to do better. To explain our approach
∗
intuitively, consider the following process: We run nα h̄(0) (n/ǫ)o(1) independent executions of the Contraction
Algorithm with parameter α∗max . This generates a large collection A of cuts, of various sizes. As we show in
Proposition 8.4, with high probability A contains all the α∗ -cuts. As described in Section 4, we may then
use the collection A to estimate U (p).
Proposition 8.4. The Contraction Algorithm with parameter α∗max finds any α∗ -cut C with probability at
∗
least n−α h̄(0) (ǫ/n)o(1) .
Proof. By Corollary 8.3, we have α∗ ≤ α∗max .
∗
If α∗ ≥ n/2, then the cut C is found with probability 21−n . By Proposition D.1, n−α h̄(0) ≤ n−Θ(n) ,
which is smaller than 21−n for n sufficiently large. So we may assume that α∗ ≤ n/2.
By Lemma 5.5, this cut C is produced by the Contraction Algorithm with probability ≥
∗
∗
e−O(αmax ) e−α E[S⌈2α∗ ⌉ ] .
∗
∗
Note that e−O(αmax ) ≥ e−O(1+ρ) . Also observe that eρ = e− log(1/ǫ)/ log n ≥ ǫo(1) . So e−O(αmax ) ≥ ǫo(1) .
∗
Also by Corollary 7.6, we have E[S⌈2α∗ ⌉ ] ≤ h̄(0) log n + O(log log n). We have that e−α E[S⌈2α∗ ⌉ ] ≥
∗
′
∗
∗
∗
e−α (h̄(0) log n+O(log log n)−Ω(log α )) ≥ e−α h̄(0) log n × (log n)−O(α ) ≥ e−α h̄(0) (ǫ/n)o(1) .

If we use this algorithm directly, then we must run completely separate instances of the Contraction
Algorithm for each sample. Each execution of the Contraction Algorithm takes time O(n2 ) (to process the
∗
graph), and so the total work would be roughly nα h̄(0)+2 . Our goal now will be to reduce the work closer
∗
to nα h̄(0) .
In [12], an efficient algorithm called the Recursive Contraction Algorithm (RCA) was introduced for
running multiple samples of the Contraction Algorithm simultaneously. This amortizes the work of processing
the graph across the multiple iterations, effectively reducing the time for a single execution of the Contraction
Algorithm from O(n2 ) to O(1).
In the next section, we will discuss how to combine the Recursive Contraction Algorithm with our improved
analysis of the Contraction Algorithm. Unlike in [12], we will not be able to show that a single application
of the RCA is as powerful as n2 independent applications of the Contraction Algorithm. We will still show
it is powerful enough to substantially reduce the cost of multiple applications of the Contraction Algorithm.
The next section will examine the Recursive Contraction Algorithm in detail.
We note that we do not need to bound either α∗ or h̄(0) individually, which would depend on knowing β.
It suffices to give an upper bound on the product α∗ h̄(0) irrespective of β.
9. The Recursive Contraction Algorithm
The basic method of finding the α∗ -cuts is to run the Contraction Algorithm for many iterations and collect
all the resulting cuts. Each iteration requires O(n2 ) work (to process the entire graph). As described in [12],
this data-processing can be amortized across the multiple iterations. The resulting Recursive Contraction
Algorithm, can enumerate all the α-cuts in time O(n2α log2 n).
We will run the RCA for a large, fixed number of iterations. This will produce a large collection of cuts
A, of various sizes. We will then show that the resulting collection will contain all the α∗ -cuts with high
probability. Note that we do not know the precise value of α∗ (it may depend on β), so we cannot simply
discard cuts of weight > α∗ c at this stage.
29

In this section (with the exception of Section 9.6), we will assume U (p) < n−K for some
constant K > 2; thus the conclusions of Proposition 3.6 hold.
We define the RCA with parameter α as follows:2
1. Randomly contract edges of G until the resulting graph G′ has at most
min(n/2, ⌈2α⌉) vertices. Run the RCA with parameter α on the subgraph G′ .
2. If G′ has ⌈2α⌉ vertices, output a random cut of G.
3. Otherwise, perform 4 independent executions of the RCA on the graph G′ .
The RCA was introduced in [12], which showed the following bounds on its performance:
Theorem 9.1 ([12]). For any graph G, the RCA with parameter α′ executes in time O(n2 log n). For
′
α > 1 + Ω(1), it finds a target α-cut C with probability at least Ω(2−α n2−2α ).
The analysis in [12] does not take into account the graph reliability. We will show a better success
probability than n2−2α taking account of this information. Our goal is to show that we can enumerate all
the α∗ cuts with high probability using n1+o(1) ǫ−1.99 independent applications of the RCA. As the running
time of RCA is n2+o(1) , the overall run time will be ≤ n3+o(1) ǫ−1.99 .
∗
We observe first that the number of α∗ -cuts is at most n2α . Thus, suppose we are able to show that any
α∗ -cut C is found with probability at least n−1−o(1) ǫ1.98 in a single execution of the RCA; then by a standard
∗
analysis of the Coupon Collector Problem, this implies that after O(log n2α × n1+o(1) ǫ−1.98 ) iterations of
∗
the RCA that all such α∗ -cuts are found, with high probability. Observing that log(n2α ) = (n/ǫ)o(1) , the
1+o(1) −1.98−o(1)
1+o(1) −1.99
total number of iterations is then bounded by n
ǫ
≤n
ǫ
, as desired.
This observation means that it suffices to consider a fixed target cut C of weight αc, for α ≤ α∗ , and to
show that C is found with probability at least n−1−o(1) ǫ1.98 . This will be our goal for the remainder of this
section. For the remainder of this section, we let C be a fixed target cut and αc its weight.
(Note: significantly better exponents than 3, 1.99 can be shown for n, ǫ respectively; but this requires
more careful calculations. Improvements in these exponents would not improve the overall run time of our
algorithm, so these are omitted.)
9.1. Storing the cuts produced by the RCA. As we have already discussed in Section 4.1, we do not
wish to explicitly store all the cuts that will be output by the RCA. Rather, we wish to store them in a
compressed format. We briefly discuss how the RCA is to able to output each cut in terms of this compressed
representation.
First, we must store a unique index for each cut C, which we define by
X
H(C) =
H(v)
modulo 2b
v∈A

where A is the first shore of C.
To compute this, we note that during the intermediate steps of the RCA, every node in the resulting
subgraphs Gi corresponds to a set P
of vertices of G. For each such vertex v ∈ Gi , which corresponds to some
subset Xv ⊆ V , we define H(v) = x∈Xv H(x) mod 2b . This can be updated at each contraction step. At
′
the end of the RCA, we must
P select a cut of the graph G⌈2α⌉ . The cut C of the graph G⌈2α⌉ corresponds to
a cut C of G and H(C) = v∈C ′ H(v). A similar process can be used to count the weight of C.
Finally, we must keep track of a pointer which allows us to fully reconstruct any cut in its uncompressed
form. To do so, we first store the complete random tape used by applications of the RCA. Then any cut
output by the RCA can be reconstructed in terms of its tree-path through the recursive calls to the RCA.
These details are discussed more in [8].
9.2. Handling the easy cases. Our analysis of the RCA will be technically challenging. As a preliminary,
we can deal with some of the easy cases first.
Proposition 9.2. The RCA enumerates C with probability ≥ n−1−o(1) ǫ1.98 , assuming that one of the following conditions is satisfied:
(1) α ≤ 3/2

2This version is slightly different from that of [12]; the algorithm in that paper uses 2 independent executions to reduce
√
the graph to n/ 2 vertices. The only effect of this change is to remove some quantization effects, which would complicate our
proof.
30

(2) ρ ≥ 2.1
(3) β ≥ 1
Proof. By Proposition 3.6, we have δ ≥ β + Ω(1) and δ ≥ K − 2 > 0 and β ∈ [0, 2].
We break this proof into a number of cases.
∗
Case I: α ≤ 3/2. By Theorem 9.1 the cut C is found with probability at least n2−2α+o(1) 2−αmax ≥
−1−o(1) −O(1+ρ)
−1−o(1) −o(1)
n
2
≥n
ǫ
as desired. Hence for the remainder of this proof we assume α ≥ 3/2.
∗
Case II: β ≥ 3/2. By Theorem 9.1, C is found with probability at least Ω(2−αmax n2−2α ) ≥
∗
2−O(1+ρ) n2−2α∗ ≥ (ǫ/n)o(1) n2−2α .
By Lemma 8.2, we have α∗ ≤ 2−β+δ+ρ
+ O(1/ log n). For β ≥ 3/2 we have α∗ ≤ 4/3 + 2/3ρ. So C is
δ
o(1) 2−4/3−2/3ρ
found with probability at least (ǫ/n) n
= n−2/3−o(1) ǫ2/3+o(1) as desired.
Thus, for the remainder of the proof, we assume β ≤ 3/2.
Case III: ρ > 2.1. In this case, we make the simple observation that a single application of the RCA
is at least as powerful as a single application of the Contraction Algorithm (if we simply ignore all but one
∗
branch of the RCA). By Proposition 8.4, then C is enumerated with probability at least n−α h̄(0) (n/ǫ)−o(1) .
Assuming that β ≤ 3/2 (otherwise case II holds), then by Lemma 8.2:
α∗ h̄(0) ≤

 (3 − β + δ)2 (2 − β + δ + ρ)
δ)2 (2

+ O(

(1 + ρ) log log n 
)) h̄(0)
log n

(2 − β +
+ δ)
(5 − 2β + 2δ)(2 − β + δ + ρ)
+ o(1 + ρ)
=
(2 − β + δ)2
 5 − 2β + 2δ


 5 − 2β + 2δ
=
−
o(1)
− o(1) + ρ
2−β+δ
(2 − β + δ)2

It can be verified mechanically that
5 − 2β + 2δ
≤ 5/2 − Ω(1)
2−β+δ

5 − 2β + 2δ
≤ 5/4 − Ω(1)
(2 − β + δ)2

Hence α∗ h̄(0) ≤ 5/2 + 5/4ρ. When ρ > 2.1, this quantity is less than 1 + 1.97ρ. Recalling that ρ =
∗
log(1/ǫ)/ log n, this means that n−α h̄(0) ≥ n−1−o(1) ǫ1.98 as desired.
Case IV: 1 ≤ β ≤ 3/2. By Lemma 8.2
α∗ ≤

(3 − β + δ)2 (2 − β + δ + ρ)
+ o(1 + ρ)
(2 − β + δ)2 (2 + δ)

It can be verified mechanically that this is at most 3/2 + (3/4)ρ for all β ∈ [1, 3/2] and δ ≥ β. So again by
Theorem 9.1, then C is found with probability at least n2−2α−o(1) ≥ n−1−o(1)−3/2ρ−o(1)ρ ≥ n−1−o(1) ǫ1.51 
Simplifying assumptions. Hence we can make the simplifying assumptions that α ≥ 3/2, ρ ≤ 2.1, β ∈
[0, 1]. As α∗ ≤ α∗max = O(1 + ρ) by Proposition 8.3, this implies that α ≤ O(1) as well. We summarize the
following assumptions which we adopt in Sections 9.3, 9.4, 9.5, and which which will not be stated explicitly
there:
(1)
(2)
(3)
(4)
(5)

ρ ≤ 2.1
3/2 ≤ α ≤ α∗ ≤ α∗max ≤ O(1)
δ > δ0 > 0
δ≥β
β ∈ [0, 1]

In light of these simplifying assumptions, we can simplify Theorem 9.1.
Proposition 9.3. Let H be a contraction-subgraph of G with r ≤ n vertices. Then the RCA with parameter
α∗max selects cut C with probability Ω(r2−2α )
∗

Proof. We have 2−αmax ≥ 2−O(1) = Ω(1) and α ≥ 3/2 > 1 + Ω(1)
31



9.3. The RCA as a branching process. It is useful to view the sequence of graphs produced by the RCA
in terms of a branching tree, in which there is a node in this branching process for each recursive call to the
RCA. Every node in this process corresponds to an partial execution of the Contraction Algorithm. We view
the root node (depth 0) as corresponding to the original graph G. The leaf nodes correspond to subgraphs
which have ≤ ⌈2α⌉ vertices. If our target cut C appears in any of the subgraphs corresponding to a leaf
node, it will be output at least once by the RCA. For any node v of this branching process, we let Gv be
the corresponding subgraph. For the root node v we have Gv = G. We say that node v succeeds if the cut
C remains in Gv .
To avoid quantization issues, it will be convenient to assume that n is a power of two. We can always
modify our original input graph to achieve this, by adding extra dummy vertices; each dummy vertex
is connected to every other vertex (including the other dummy vertices) by infinitely many edges. This
modification does not change U (p), and it only changes n by a constant factor. As we aim to give running
times which are polynomial in n and do not depend on m, this will not affect our runtime analysis by more
than a constant factor.
Once we make this assumption, then we can see that, aside from the leaf nodes, the nodes at depth i of
the RCA branching process correspond to running the Contraction Algorithm from the original graph G to
a graph with exactly n2−i nodes. The overall depth of this tree is H = ⌊log2 ( ⌈2αn∗ ⌉ )⌋. As α∗max = O(1),
max
we have that log2 n − O(1) ≤ H ≤ log2 n.
Our goal is to calculate the probability that some leaf node succeeds. In the ideal case (if the leaves
corresponded to independent executions of the Contraction Algorithm), then the probability of a successful
leaf node is nearly equal to the expected number of leaf nodes.
The analysis of [12] viewed the RCA as a type of percolation process, in which the survival of a target cut
C percolated from the root node to the leaf nodes. Starting at any given node at depth i, there is a certain
probability that a cut C is retained throughout all the contractions from that node to its children. All the
survival events are independent.
Our analysis, however, must also keep track of the stochastic evolution of the subgraphs Gi during the
Contraction Process. Our improvements have been based on bounding the expected number of edges in these
graphs. Thus, we cannot assume that starting at a node v at depth i, the probability that cut C survives
in two nodes is the square of the probability that it survives in one; the reason is that these events are both
dependent on the random variable Gv .
As a result of this, there is a significant correlation between the successes at nearby nodes of the RCA
tree. This in turn lowers the overall probability that there is at least one successful leaf node. Dealing with
this correlation among nearby nodes will be the major technical challenge for the analysis of the RCA. This
correlation becomes more severe at greater depths of the RCA tree.
9.4. Marking nodes. We wish to show that there is a good probability of having at least one successful
node. We will do so by using Inclusion-Exclusion (IE):
P(At least one successful node) ≥ E[# successful nodes] − E[# pairs of successful nodes]
One somewhat paradoxical feature of Inclusion-Exclusion is that sometimes it can give worse estimates
when the expected number of successes goes up. For
Pexample, suppose wehave n independent Bernoulli-q
random variables X1 , . . . , Xn . By IE, we have P( Xi ≥ 1) ≥ nq − n2 q 2 . When q → 0, then this is
essentially an accurate estimate, but when q → 1 then the RHS becomes negative — yielding a completely
useless estimate.
We will avoid this problem for our analysis as follows. Every node v at depth k of the RCA corresponds
to a partial execution of the Contraction Algorithm, up to a subgraph with n2−k vertices. We can define
the random variables Si , Mi , Gi , Fi for i = n2−k , . . . , n for this node; we denote them by Siv , Miv , Gvi , Fiv .
Observe that Gvn2−k = Gv .
v
Now, if the cut C survives to Gv , then mark the node v with probability min(1, eα(Sn2−k −B) ), where B
is a threshold value which we will specify. All such markings are done independently. If the cut C does not
survive in Gv , then we do not mark v.
Clearly, the probability that some node survives to depth k is at least equal to the probability that there
is a marked node at depth k. It is the latter that we will estimate via IE.
32

For any execution of the Contraction Algorithm and any integer k ≥ 0, we define
Tk = max(Sn2−k , B)

We will show a lower bound on the probability that a depth-k node is marked, and an upper bound on
the probability that two depth-k nodes are both simultaneously marked.
Proposition 9.4. Let v be a node at depth k of the RCA tree. The probability that node v is marked is at
least
P(v is marked) ≥ Ω(ECP(G,C) [e−αTk ])
v
Proof. Let i = n2−k . The partial history F>i
for the node v has a distribution which is simply the Contraction
Algorithm up to stage i. In order for the node v to be marked, the edges of that history must all be disjoint
to C. So, integrating over such edges,
X
PCA(G) (F>i = hen , . . . , ei+1 i) × min(1, eα(Si −B) )
P(v marked) =
ei+1 ,...,en
disjoint to C

=

X

ei+1 ,...,en
disjoint to C

PCP(G,C) (F>i = hen , . . . , ei+1 i) min(1, eα(Si −B) )

n
Y

(1 −

r=i+1

|C|
)
Mr

by Proposition 5.1
X
PCP(G,C) (F>i = hen , . . . , ei+1 i) min(1, eα(Si −B) )e−αSi
≥ 16−α

by Lemma 5.4

ei+1 ,...,en
disjoint to C

≥ 16−α
= 16−α

X

PCP(G,C) (F>i = hen , . . . , ei+1 i) min(e−αSi , e−αB )

X

PCP(G,C) (F>i = hen , . . . , ei+1 i)e−αTk

ei+1 ,...,en
disjoint to C

ei+1 ,...,en
disjoint to C

= 16−α ECP(G,C) [e−αTk ]
Now as α ≤ α∗max ≤ O(1) we have the claimed result.



Proposition 9.5. Let v, v ′ be two nodes at depth k of the RCA tree, whose nearest common ancestor w is
at depth j ≤ k. The probability that v, v ′ are both marked satisfies the bounds
P(v and v ′ marked) ≤ ECP(G,C) [e−αTk ]
P(v and v ′ marked) ≤ n

αh(1− logj

)
2n

ECP(G,C) [e−2αTk ]

Proof. To show the first bound, we simply ignore node v ′ completely. In this case, the proof is nearly identical
to Proposition 9.4, except we use an upper bound instead of a lower bound.
Let us turn our attention to the second bound. Let i = n2−k and t = n2−j . The graph Gw is derived
by running the Contraction Algorithm up to j nodes. Conditional on Gw , the nodes v, v ′ are independent,
and they are derived by running the Contraction Algorithm starting at Gw down to i nodes. We can thus
view the joint distribution on the histories at v, v ′ in terms of a “double Contraction Algorithm” denoted
DCA(G). One can similarly define a “double Contraction Process” denoted DCP(G, C), where at every
stage we select an edge uniformly from the edges outside C.
′
For this process, let Fi+1 , . . . , Fn be the resulting set of edges for the first leg, and let Fi+1
, . . . , Fn′ be
′
the resulting set of edges for the second leg. Both F>i and F>i are distributed according to the Contraction
Process, but are not independent. Also, we must have Fℓ = Fℓ′ for ℓ = t + 1, . . . , n.
Now suppose we are given a sequence of edges fi , . . . , fn , fi′ , . . . , fn′ , with fℓ = fℓ′ for ℓ = t + 1, . . . , n;
we wish to analyze whether they could be produced by double Contraction Algorithm. In the usual way
for analyzing the Contraction Algorithm, let the resulting subgraphs by defined by Gn = G′n = G, and
Gℓ−1 = Gℓ /fℓ etc. We similarly define Mℓ , Mℓ′ , Sℓ , Sℓ′ . Finally, we define Tk = max(Si , B) and similarly for
33

Tk′ = max(Si′ , B). Finally we define H = Gt ; this is the graph at which the two legs of the double Contraction
Process first diverge.
PDCA(G,C) (F>i f~ ∧ F>i = f~′ )

′
= PCA(G) (F>t = hfn , . . . , ft+1 i)PCA(H) (F>i = hft , . . . , fi+1 i)PCA(H) (F>i = hft′ , . . . , fi+1
i)

= PCP(G,C) (F>t = f~)

n
Y

(1 −

r=t+1

t
Y
|C|
|C|
(1 −
)PCA(H) (F>i = hft , . . . , fi+1 i)
)
Mr
Mr
r=i+1

′
× PCA(H) (F>i = hft′ , . . . , fi+1
i)
′
= PDCP(G,C) (F>i = f~ ∧ F>i
= f~′ )

≤ PDCP(G,C) (F>i
= PDCP(G,C) (F>i
log t

t
Y

r=i+1
n
Y

(1 −

(1 −

r=t+1

|C|
)
Mr′

by Proposition 5.1

t
t
|C| Y
|C| Y
|C|
(1 −
(1 − ′ )
)
)
Mr r=i+1
Mr r=i+1
Mr

′
′
= f~ ∧ F>i
= f~′ )e−αSt e−α(Si −St ) e−α(Si −St )

by Lemma 5.4

′
′
= f~ ∧ F>i
= f~′ )eαSt e−αSi e−αSi

′
′
= f~′ )e−αSi e−αSi
≤ nαh( log n ) PDCP(G,C) (F>i = f~ ∧ F>i

by Proposition 7.1

If we include the probability that both nodes are also marked, we have:
v
v′
P(F>i
= f~ ∧ F>i
= f~′ ∧ v, v ′ marked) = PDCA(G,C) (F>i = f~ ∧ F>i = f~′ ) ∧ P(v, v ′ marked)
log t

′
′
≤ nαh( log n ) PDCP(G,C) (F>i = f~ ∧ F>i
= f~′ )e−αSi e−αSi
′

× min(1, eα(Si −B) ) min(1, eα(Si −B) )
log t

′
′
= f~′ )e−αTk e−αTk
≤ nαh( log n ) PDCP(G,C) (F>i = f~ ∧ F>i

Now, integrating over f~, f~′ ,
′

v
v
P(F>i
= f~ ∧ F>i
= f~′ ∧ v, v ′ marked) ≤

X
f~,f~′

log t

′

′
nαh( log n ) PDCP(G,C) (F>i = f~ ∧ F>i
= f~′ )e−αTk e−αTk
log t

′

= nαh( log n ) ETk ,Tk′ ∼DCP(G,C) [e−αTk e−αTk ]
q
log t
′
≤ nαh( log n ) ETk ,Tk′ ∼DCP(G,C) [e−2αTk ]ETk ,Tk′ ∼DCP(G,C) [e−2αTk ]

by Cauchy-Schwarz
q
log t
′
= nαh( log n ) ETk ∼CP(G,C) [e−2αTk ]ETk′ ∼CP(G,C) [e−2αTk ]
log t

= nαh( log n ) ETk ∼CP(G,C) [e−2αTk ]
Finally, observe that t = n2−j , giving the final result.



9.5. Inclusion-Exclusion analysis. We now move on to use Inclusion-Exclusion. We will not directly
apply it to show that there is a leaf node where C survives — the correlation among the nodes is too severe
for nodes deep in the RCA tree. We will count smaller-depth nodes instead.
Proposition 9.6. For any integers j, k with 0 ≤ j ≤ k ≤ H, we have
i

h
αh(1− logj n ) −2αTk
2
e
E[ # pairs of marked nodes at depth k] ≤ O ETk ∼CP(G,C) 42k−j e−αTk + n

Proof. For each i ≤ k, we count the number of level-k nodes which are marked and have a nearest common
ancestor at level i. As every node has four children, the total number of such nodes pairs is 4k × 3 × 4k−i−1 .
For each such pair, we use Proposition 9.5 to estimate the probability that both nodes are marked; we use
log j
the cruder estimate ECP(G,C) [e−αTk ] for i ≥ j and the more refined estimate nαh( log n ) ECP(G,C) [e−2αTk ] for
i < j.
34

Thus, summing over all i = 0, . . . , k, we have
E[ # pairs of marked nodes at depth k] ≤

k
X

i=j+1

+

4k × 3 × 4k−i−1 ECP(G,C) [e−αTk ]

j
X
i=0

i

4k × 3 × 4k−i−1 nαh(1− log2 n ) ECP(G,C) [e−2αTk ]

≤ 42k−j ECP(G,C) [e−αTk ] + 42k ECP(G,C) [e−2αTk ]

j
X
i=0

By Proposition D.2 we have that h′ (x) ≤ −4/3 − Ω(1) for all x ∈ [0, 1]. Thus, for all x ≥ 1 −

have h(x) ≤ h(1 −

j
log2 n )

− (4/3 − Ω(1))(x − (1 −
j

i

4−i nαh(1− log2 n ) ≤ 4−i nαh(1− log2 n )−

j
log2 n )).

α(4/3−Ω(1))
log2 n

j

= 4−j n
So

Pj

i=0

4−i n

αh(1− logi

)
2n

j
log2 n ,

we

So we estimate

j

≤ 4−i nαh(1− log2 n ) 2−α(j−i)(4/3−Ω(1))

≤ 4−i nαh(1− log2 n ) 2−3/2(j−i)(4/3−Ω(1))
αh(1− logj n )
2

i

4−i nαh(1− log2 n )

as α > 3/2

(1 − Ω(1))j−i



αh(1− logj n )
2
. This gives us our final estimate
≤ O 4−j n
αh(1−

j

)

log2 n
ECP(G,C) e−2αTk )
E[ # pairs of marked nodes at depth k] ≤ 42k−j ECP(G,C) [e−αTk ]) + O(42k−j n


j
= O ECP(G,C) [42k−j e−αTk + nαh(1− log2 n ) e−2αTk ]



Lemma 9.7. Suppose that j, k are integers in the range 0 ≤ j ≤ k ≤ H. Let ψ > 0 be any sufficiently small
constant. Then the RCA with parameter α∗max finds the target cut C with probability at least

h
j
i
P(RCA tree includes C) ≥ Ω ECP(C,G) 4αk n2−2α e−αTk − ψ42αk−j n4−4α e−αTk + nαh(1− log2 n ) e−2αTk

Proof. Each marked node at depth k of the RCA tree corresponds to a subgraph with n2−k vertices which
contains cut C. Hence, if we execute the remaining stages of the RCA, by Proposition 9.3 it will generate some
leaf node containing C with probability Ω((n2−k )2−2α ). So each such marked node v has some independent
probability qv ≥ φ′ (n2−k )2−2α that a leaf node below it contains cut C; here φ′ is some constant.
Let φ be any constant such that φ ∈ (0, φ′ ] and let q = φ(n2−k )2−2α . Now we apply an additional
randomization step: we discard v and all its subtree below v with probability qv − q. This is a valid
probability as qv ≥ q. Also, it is easy to see now that for any marked node, the probability that there is a
non-discarded leaf node containing C is exactly equal to q.
Note that we have applied two “attenuation” steps which can only reduce the probability of finding C
among the nodes of the RCA-tree. First, some unmarked nodes may have a leaf node containing C, and
some marked nodes will contain C but be discarded. If a marked node v at depth k contains some leaf
node containing C, and v is not discarded, we say that v is a winner. Each marked node is a winner with
probability exactly equal to q.
By Proposition 9.4, the expected number of marked leaf nodes is Ω(4k ECP(G,C) [e−αTk ]) and so the expected number of winners is Ω(q4k ECP(G,C) [e−αTk ]).

h

By Proposition 9.6, the expected number of pairs of marked leaf nodes is O ECP(G,C) 42k−j e−αTk +
i

h
j
and so the expected number of pairs of winners is O q 2 42k−j ECP(G,C) e−αTk +
nαh(1− log2 n ) e−2αTk
i
j
nαh(1− log2 n ) e−2αTk .
35

By Inclusion-Exclusion, the probability that there is at least one winner can be lower bounded by:
P(RCA tree includes C) ≥ P(There is a winner at depth k)
i


h
j
≥ Ω q4k ECP(G,C) [e−αTk ]) − O q 2 42k−j ECP(G,C) e−αTk + nαh(1− log2 n ) e−2αTk
h
j
i
= ECP(G,C) c1 φ4αk n2−2α e−αTk − c2 φ2 42αk−j n4−4α e−αTk + nαh(1− log2 n ) e−2αTk
where c1 , c2 are constants

1
Set φ = min(φ′ , ψc
c2 ) and we lower-bound this expression as

h
j
i
Ω ECP(C,G) 4αk n2−2α e−αTk − ψ42αk−j n4−4α e−αTk + nαh(1− log2 n ) e−2αTk



Lemma 9.8. Let y ∈ [0, 1], and define t = max(h(y), h̄(y/α)). Then the RCA with parameter α∗max finds
the target cut C with probability at least
P(RCA succeeds) ≥ n2−αt−2y−o(1)
Proof. Let x = y/α, so that t = max(h(y), h̄(x)). We set
j = min H, ⌊(1 − y) log2 n⌋



k = min H, ⌊(1 − x) log2 n⌋



Clearly j, k are integers and 0 ≤ j ≤ k ≤ H. Also, as H ≥ log2 n − O(1), we have that |j − (1 − y) log2 n| ≤
O(1) and |k − (1 − x) log2 n| ≤ O(1).
We now observe that h(1 − logj n ) = h(y ± O(1/ log n)); as the derivative of h is bounded by constants
2
(Proposition D.2), this is at most t + O(1/ log n). Similarly, the derivative of h̄ is bounded by constants, so
h̄(1 − logk n ) ≤ t + O(1/ log n).
2
We now apply Lemma 9.7 to obtain:

h
j

P(RCA tree includes C) ≥ Ω ECP(G,C) 4αk n2−2α e−αTk − ψ42αk−j n4−4α e−αTk + nαh(1− log2 n ) e−2αTk
where ψ is a constant parameter to be determined. Using the fact that α = O(1) and |k − (1 − x) log2 n| ≤
O(1), we see that the terms can be bounded as
4αk n2−2α ≥ Ω(n2−2y )

42αk−j n4−4α ≤ O(n2−2y )
j

So

nh(1− log2 n ) ≤ O(nt )


h
i
P(RCA tree includes C) ≥ n2−2y Ω ECP(G,C) Ω(e−αTk ) − ψO e−αTk + nαt e−2αTk

By choosing ψ to be a sufficiently small constant, we obtain:


h
i
P(RCA tree includes C) ≥ n2−2y Ω ECP(G,C) e−αTk − 13 e−αTk + nαt e−2αTk
i

h
= n2−2y Ω ECP(G,C) e−αTk (1 − 21 nαt e−αTk )

At this point, we are ready to specify the threshold value B = t log n; recall that Tk = max(Sn2−k , B).
By definition of Tk we have that nαt e−αTk ≤ nαt e−αB = 1 and so


P(RCA tree includes C) ≥ n2−2y Ω ECP(G,C) [e−αTk (1 − 12 )
= n2−2y Ω(ECP(G,C) [e−αTk ])

We now claim that
(3)
which will give us our claimed result.

ECP(G,C) [e−αTk ] ≥ n−αt−o(1)
36

Let us write S = Sn2−k , and so Tk = max(S, B). Let r = P(S > B). We show (3) by considering separate
cases for the size of r.
log n
. In this case,
Case I: r ≤ 1+αt
2+αt log n
ECP(G,C) [e−αTk ] ≥ P(S ≤ B) × ECP(G,C) [e−αTk | S ≤ B]
= (1 − r)e−αB

≥ (1 −

1 + αt log n −αB
)e
2 + αt log n

n−αt
2 + αt log n

=

≥ n−αt−o(1)
Case II: r >
B) = s/r. So

1+αt log n
.
2+αt log n

as α, t ≤ O(1)

Let s = ECP(G,C) [S]. Observe that ECP(G,C) [S | S ≥ B] ≤ ECP(G,C) [S]/P (S ≥

ECP(G,C) [e−αTk ] ≥ E[e−αTk | S > B]P(S > B)
= E[e−αS | S > B]P(S > B)

≥e

−αE[S|S>B]

P(S > B)

≥ re−αs/r ≥ 21 e

S = Tk for S > B

by Jensen’s inequality

log n
−αs× 2+αt
1+αt log n

We now estimate s using Theorem 7.5 as:

log(n2−k )
) log n + O(log log n)
log n
k
) log n + O(log log n)
≤ h̄(1 −
log2 n
≤ h̄(x) log n + O(1) + O(log log n)

s = ECP(G,C) [S] ≤ h̄(

≤ t log n + O(log log n)

So

 2 + αt log n
)
exp(−α t log n + O(log log n) ×
1 + αt log n
2 + αt log n
≥ n−o(1) exp(−αt log n ×
)
as α = O(1)
1 + αt log n

ECP(G,C) [e−αTk ] ≥

1
2

2

= n−o(1) e1−αt log n− 2+αt log n ≥ n−o(1) n−αt
In either case, we have shown (3).



Theorem 9.9. The RCA with parameter α∗max finds any target α∗ -cut C with probability at least
n−1−o(1) ǫ1.98 .
Proof. If the simplifying assumptions do not hold, then this is already covered by Proposition 9.2.
By Lemma 9.8, C is found with probability at least n2−α max(h(y),h̄(y/α))−2y−o(1) in each iteration of the
RCA, for any y ∈ [0, 1]. By Proposition C.3, there is y ∈ [0, 1] so that this at least n2−3−1.5ρ−o(1) =
n−1−1.5ρ−o(1) .

We defer the proof of Proposition C.3 to Appendix C. It is simple conceptually but it is an extremely
tedious exercise, based on computer checking of a very large number of cases.
9.6. Further applications of the Recursive Contraction Algorithm. In this Section 9.6, we do not
make any assumption on the size of U (p).
The Recursive Contraction Algorithm provides a powerful approach to enumerate all the approximatelyminimum cuts in a given graph G. Our reliability-estimation algorithm uses it in a very specific way based
on bounds for the number of cuts of G. However, we can slightly improve the analysis of the Recursive
Contraction Algorithm in other situations. Given a particular value of α and a given graph G (with no
37

information about the cut structure or reliability of G), how to enumerate the α-cuts of G. The Recursive
Contraction Algorithm was first introduced in [12] to solve this problem. However, the original description
of the RCA was not parametrized in the best way, leading to slightly sub-optimal running time. We improve
this here.
Theorem 9.10. There is an algorithm to enumerate, with high probability, all α-cuts of G in time
O(n2α log n).
Proof. First, suppose α < 3/2. Then [10] describes a data structure to represent all the α-cuts in time O(n2 )
2
and to enumerate all the α-cuts
√ in time O(n log n).
Finally, suppose 3/2 ≤ α ≤ n. We execute the following variant of the Recursive Contraction Algorithm,
which we denote RCA2
1. Randomly contract edges of G until the resulting graph G′ has at most
min(n−2/5 , ⌈2α⌉) vertices.
2. If G′ has ⌈2α⌉ vertices, output a random cut of G.
3. Otherwise, perform 2 independent executions of RCA2 on the graph G′ .
A simple application of the Master Theorem for recurrences along with arguments from [12] shows that
this algorithm executes in time O(n5/2 ). Also using arguments from [12], we can show that for any α-cut C,
and any execution of this algorithm, the cut is selected with probability n5/2−2α exp(Ω(α log α)).
Thus we can view the process of finding all α-cuts as a Coupon Collector Problem. As there are at most
n2α cuts, if we run (2α log n) × n2α−5/2 exp(−α log α) = n2α−5/2 log n independent executions of RCA2, then
we find all cuts with high probability. This gives a total run time of O(n2α log n).

10. Putting it all together
We may now put all the pieces of the algorithm together. Our basic plan is to use the cut-enumeration if
U (p) < n−K , and use Monte-Carlo sampling when U (p) ≥ n−K , where K is some chosen parameter close to
2.
How do we determine which of these two methods to apply? At first, it would appear that this decision
requires knowing U (p), which is what we are trying to determine in the first place. A simple way to make this
decision is to run a preliminary Monte-Carlo sampling for φnK trials, where φ > 1 is constant. If during any
of these samples we observe the graph become disconnected, we will use Monte-Carlo sampling to estimate
U (p); otherwise we use cut-enumeration.
This achieves at least a gross discrimination between the two regimes:
Proposition 10.1. Suppose U (p) ≥ n−K . Then the probability of observing the graph become disconnected,
is bounded from below by a constant which approaches 1 for φ sufficiently large.
Suppose U (p) ≤ φ′ n−K , for φ′ a constant. Then the probability of observing the graph become disconnected,
is bounded from above by a constant which approaches 0 for φ′ sufficiently small.
Proof. In the first case, the number of times the graph becomes disconnected is a binomial random variable,
with φnK trials and expected number of successes ≥ φ. By Chernoff’s bound, the probability that there are
zero successes is ≤ e−φ ; this approaches zero for φ sufficiently large.
In the second case, the expected number of successes is ≤ φ′ . By Markov’s inequality, the probability
that that there is at least one success is ≤ φ′ ; this approaches zero for φ′ sufficiently small.


Now, when U (p) ≥ n−K , we will choose Monte-Carlo sampling with probability at least 0.99. This is good
because the cut-enumeration algorithm may not be well-behaved when U (p) ≥ n−K ; most of our theorems
completely break down in the regime U (p) ≥ n−2 .
When U (p) ≤ φ′ n−K , we will use cut-enumeration with probability at least 0.99.
When φ′ n−K < U (p) < n−K , we may use either Monte Carlo sampling or cut-enumeration. In this
regime, either of these two algorithms gives good performance. The Monte-Carlo sampling will have relative
variance O(n−K ). We have already shown that when U (p) < n−K that cut-enumeration behaves correctly.
We now obtain our main result:

Proposition 10.2. Let γ > 0 be any constant. Then we can estimate U (p) in time O(n3+γ ǫ−2 ) with
probability ≥ 3/4.
38

Proof. Let K = 2 + γ/2.
Suppose that U (p) < n−K and we elect to use the cut-enumeration procedure. We run the RCA for
3+o(1) −1.99
n
ǫ
iterations, and let A denote the resulting set of cuts. By Theorem 9.9, A contains all the
α∗ -cuts with high probability. In particular,
(1 − ǫ)U (p) ≤ Uα∗ (p) ≤ UA (p) ≤ U (p)
So UA (p) indeed estimates U (p) to within relative error ǫ. We next use the estimation algorithm of
Section 4 with this collection. By Proposition 4.7, this estimates UA (p), and hence U (p), to within relative
error O(ǫ). The total time for this is O(|A|polylog|A|+n2 /ǫ2 ). As |A| ≤ n3+o(1) ǫ−1.99 , the term |A|polylog|A|
is at most n3+o(1) ǫ−2 . So the overall running time is indeed n3+o(1) ǫ−2 as desired.
Suppose instead that U (p) ≥ φ′ n−K , where φ′ is a constant chosen in Proposition 10.1, and we elect to use
Monte-Carlo sampling. The straightforward strategy for Monte Carlo sampling would require O(m) time per
sample. However, a sparsification method of [8] reduces this is n1+o(1) time per sample. (This sparsification
is somewhat involved and we will not modify it; see [8] for a more thorough description). Overall, the time
for Monte Carlo sampling O(nK+1 ǫ−2 logO(1) n).
The total work is O(n3+γ ǫ−2 ) either way.
By Proposition 10.1, with arbitrarily high constant probability, one of these two cases holds. This implies
that we find a good estimate with probability > 3/4, which is the goal of our FPRAS.

Note that our estimates have been developed under the assumption that δ is uniformly bounded away
from 0. This means that for any constant γ > 0, there exists an algorithm with running time O(n3+γ ǫ−2 ).
All of the asymptotic terms may depend arbitrarily on γ. As γ → 0, then δ → 0 as well.
In fact one can produce these algorithms in a uniform way. That is, there is a Turing machine M which
on input t produces a Turing machine Mt ; in turn, Mt produces an estimate for U (p) in time n3+1/t ǫ−2 .
This follows from the fact that all the hidden constants in our proofs can be upper-bounded by computable
1
⌉. (This is easy to show, but we have avoided doing so because explicitly tracking all these
functions of ⌈ K−2
constant terms would make our analysis more difficult than it already is. This is a very weak property, as
computable functions may grow very quickly.)
We first show a general condition for uniformization of FPRAS algorithm; we then conclude by applying
it to estimating U (p).
Lemma 10.3. Suppose that M is a Turing machine with the following behavior: on input t > 0, it produces
a Turing machine Mt . Furthermore, Mt has the property that it estimates some statistic X with relative
error ǫ with probability > 3/4, and Mt runs in time ≤ ct na+1/t ǫ−b .
Then there is an FPRAS for X running in time na+o(1) ǫ−b .
Proof. First, by repeating any FPRAS for Ω(log n) samples and taking the median, one can increase the
success probability from 3/4 to 1 − 1/n2 . Let Mt′ be the FPRAS derived by this amplification; clearly they
are also computable and they have running times O(ct na+1/t ǫ−b log n).
Now, consider the following algorithm: given some input vector ~x of bit-length n, we wish to estimate
X(~x). To do so, we dovetail the following computations: we run M (1), . . . , M (log n); as soon as M (i)
terminates, we immediately run the resulting Mi′ (~x). If any computation Mi′ terminates, we output its
answer and terminate.
We first claim that with probability ≥ 3/4 this gives a correct answer. For, a necessary condition for this
′
to fail is that one of Mi′ , . . . , Mlog
x; the total probability of this is at most log n× 1/n2 ≤ 1/4.
n fails on input ~
Next, we claim that for any fixed integer s > 0 that this algorithm runs in time ≤ na+1/s ǫ−b for n
sufficiently large. Let t = 2s. Suppose that M (t) takes time k to compute Mt . Then, for log n ≥ t, our
algorithm runs Mt′ (among other algorithms). It would take time k + ct na+1/t ǫ−b log n for algorithm Mt′ to
succeed.
We are dovetailing log n separate computations. If the total run-time exceeds (k + ct na+1/t ǫ−b log n) log n,
then algorithm Mt will receive at least a share of k + ct na+1/t ǫ−b log n runtime, and it will terminate with
the answer (unless another process has terminated earlier). Thus, the overall run-time of this algorithm is
at most (k + ct na+1/t ǫ−b log n) log n. This is ≤ na+1/s ǫ−b for n sufficiently large as t > s.
39

So, in all, our algorithm runs in time ≤ na+1/t ǫ−b for any t > 0 and n sufficiently large. This implies it
runs in time na+o(1) ǫ−b . It returns a correct answer with probability ≥ 3/4, as required.

Theorem 10.4. There is an algorithm to estimate U (p) in time n3+o(1) ǫ−2 .
Proof. This follows from Lemma 10.3 and Proposition 10.2.



11. Concluding Remarks
Two natural open questions are to see if a run-time bound such as O(n2 /ǫ2 ) is possible, and to identify
other possible applications of differential-equation approximations such as ours.
It remains an outstanding open question to make progress on the approximability of R(G, p) = R(p), the
probability of G remaining connected : as pointed out by Leslie Goldberg to us, even very weak approximations here can be turned into PTAS-type approximations, and a proof of this from [5] is as follows. For
example, suppose for some ǫ > 0 that there is a polynomial-time algorithm that given as input any connected
graph H with nH vertices, produces a value R̂(H, p) satisfying
√
nH

(1 − ǫ)

(4)

√

R(H, p) ≤ R̂(H, p) ≤ (1 + ǫ)

nH

R(H, p);

note that this is a very weak approximation algorithm. However, it can be turned into essentially an (1 ± ǫ)–
approximation algorithm as follows. Take the connected input graph G for which we want to well-approximate
R(G, p). Choose an arbitrary vertex v of G, and construct a graph H by taking nG copies of G, but by also
graph-theoretically “identifying” (i.e., fusing together) the copies of vertex v. Then R(H, p) = R(G, p)nG
√
and nH = n2G − nG + 1 ∼ n2G ; in particular, nH = nG − 1/2 + o(1). Thus, by (4),
√

(1 − ǫ)

nH

R(G, p)nG

≤ R̂(H, p) ≤

(1 − ǫ)1−o(1) R(G, p) ≤ (R̂(H, p))1/nG ≤

√
nH

(1 + ǫ)

R(G, p)nG , i.e.,

(1 + ǫ)1−o(1) R(G, p);

thus, (R̂(H, p))1/nG is an excellent approximation to R(G, p). Thus, the approximability of R(G, p) is either
excellent, or very poor; determining the truth here is a very intriguing open question.
12. Acknowledgments
We thank the SODA 2014 referees for their helpful comments, and Leslie Goldberg for a valuable discussion
on R(p). The discussion with Leslie Goldberg that is included in Section 11, as well as part of Aravind
Srinivasan’s writing, transpired while Srinivasan attended the ICERM Workshop on Stochastic Graph Models
in March 2014. We thank the workshop organizers for their kind invitation.
Thanks to Thomas Lange and to the anonymous journal reviewers for their many helpful comments and
thorough reading of this paper.
References
[1] Benczúr, A., Karger, D.: Approximate s − t min-cuts in Õ(n2 ) time. SIAM Journal on Computing 44-2, pp. 290-319 (2015)
[2] Bixby, R.: The minimum number of edges and vertices in a graph with edge connectivity n and m n-bonds. Bulletin of the
American Mathematical Society 80, 700-704 (1974).
[3] Chandran, L., Shankar, L.: On the number of minimum cuts in a graph. SIAM Journal of Discrete Mathematics 18, 177-194
(2004).
[4] Gdalyahu, G., Weinshall, D., Weman, M.: Self-organization in vision: stochastic clustering for image segmentation, perceptual grouping, and image database organization. Pattern Analysis and Machine Intelligence, IEEE Transactions on 23.10,
pp. 1053-1074 (2001).
[5] Goldberg, L. A., Jerrum, M.: Approximating the Partition Function of the Ferromagnetic Potts Model. Journal of the ACM
59, 25:1–25:31 (2012).
[6] Karger, D.: Random Sampling in Graph Optimization Problems. Ph.D. Thesis, Department of Computer Science, Stanford
University, 1994.
[7] Karger, D.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. Proceedings of the ACM-SIAM
Symposium on Discrete Algorithms, 21-30 (1993).
[8] Karger, D.: A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem.
SIAM Journal on Computing 29-2, 492-514 (1999)
[9] Karger, D.: A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem.
SIAM Review 43-3, 499-522 (2001)
[10] Karger, D.: Minimum Cuts in Near-Linear Time. Journal of the ACM 47 1, 46-76 (2000)
[11] Karger, D.: A fast and simpler unbiased estimator for network (un)reliability. Proceedings of the 48th annual Symposium
on the Foundations of Computer Science, pp. 635 - 644 (2016)
40

[12] Karger, D., Stein, C.: A new approach to the minimum cut problem. Journal of the ACM 43, 601-640 (1995).
[13] Karger, D., Tai, P.: Implementing a Fully Polynomial Time Approximation Scheme for All Terminal Network Reliability.
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 334-343 (1997).
[14] Karp, R. M., Luby, M., Madras, N. Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms
10, 429-448 (1989).
[15] Lomonosov, M.: Bernoulli scheme with closure. Problems of Information Transmission 10, 73-81. (1974)
[16] Lomonosov, M., Polesskii, V. P.: Lower bound of network reliability. Problems of Information Transmission 7, 118-123.
(1971)
[17] Sharafat, A., Ma’rouzi, O.: All-Terminal network reliability using recursive truncation algorithm. IEEE Transactions on
Reliability 58, 338 - 347. (2009)
[18] Wormald, N.: The differential equation method for random graph processes and greedy algorithm. Annals of Applied
Probability 5-4, pp. 875 - 1240 (1995).

Appendix A. Numerical analysis for Section 6
To complete the proof of Theorem 6.2, we must verify certain concavity and monotonicity properties of
the function f defined by
2
h (i/n) c+1
−1
(2k + (c − 1)n) − 2k i
f (i, n, k) = log
(c − 1)i
Proposition A.1. For 1 ≤ i ≤ n, the function f is well-defined.

Proof. We need to show that the argument of the logarithm is strictly greater than 0. By Proposition A.2,
the argument is strictly increasing in k, so it suffices to show that it is positive at k = 0. When k = 0, it is
equal to
2
(i/n) c+1 −1 ((c − 1)n)
(c − 1)i
which is clearly positive.

Proposition A.2. For 1 ≤ i ≤ n and c ≥ 1 the function f (i, n, k) is an increasing, concave-down function
of k.
Proof. The function f applies the logarithm function to an argument which is a linear function of k. The
slope of that linear function is
2
2n((i/n) c+1 − (i/n))
>0
(c − 1)i2
for c > 1 and 1 ≤ i ≤ n.

Proposition A.3. Suppose c ≥ 3 and i, k, n ≥ 0. Then the expression
c/m + f (i, n, ke−c/m)

is a decreasing function of m.
Proof. Let t = c/m. We wish to show that t + f (i, r, ke−t ) is increasing in t.
Differentiating with respect to t, it suffices to show that
2

2

2k((i/n) − (i/n) c+1 )

(i/n) c+1 ((c − 1)net + 2k) − 2(i/n)k

+1≥0

By differentiating with respect to i (viewing i as a continuous parameter), we see that the left-hand side
of the above expression is increasing in i. Hence it suffices to show that this holds when i → 0. In this case,
as i → 0, the terms (i/n)2/(c+1) are negligible compared to the linear terms in (i/n), so the above approaches
a limit as i → 0 of
(c − 1)net
(c − 1)net + 2k
which is obviously positive.

Proposition A.4. For c ≥ 3, n ≥ i + 1 and k ≤ n we have
c
c
+ f (i, n − 1, ke− nc/2+(n−k)/2 ) ≤ f (i, n, k)
nc/2 + (n − k)/2
41

Proof. It suffices to show that


c
c
exp
+ f (i, n − 1, ke− nc/2+(n−k)/2 ) − exp(f (i, n, k)) ≤ 0
nc/2 + (n − k)/2
This expression can be rewritten as
 c−1

 2c

c−1
2c
2c
−2k n c+1 − (n − 1) c+1 − (c − 1) n c+1 − e cn+n (n − 1) c+1
(5)
≤0
2c
(c − 1)i c+1
2

2

denominator is positive,
and the term n1− c+1 − (n − 1)1− c+1 is positive. Finally, the coefficient

 The
2c
2c
2c
n c+1 − e cn+n (n − 1) c+1 can be bounded as:




2c
2c
2c
2c
2c
2c
2c
2c
2c
n c+1 − e cn+n (n − 1) c+1 = n c+1 1 − e n(c+1) 1 − 1/n) c+1 ≥ n c+1 1 − e n(c+1) (e−1/n ) c+1 = 0
Thus, we verify that (5) holds.



Proposition A.5. For c ≥ 3, k ≥ n ≥ i + 1 we have
2
2
+ f (i, n − 1, ke− n ) ≤ f (i, n, k)
n
Proof. It suffices to show that
2

2
exp
+ f (i, n − 1, ke− n ) − exp(f (i, n, k)) ≤ 0
n
This simplifies to showing that
 c−1

 2c

c−1
2c
−2k n c+1 − (n − 1) c+1 − (c − 1) n c+1 − e2/n (n − 1) c+1
≤0
(6)
2c
(c − 1)i c+1

The denominator of (6) is positive, and the numerator is a decreasing function of k. Hence, as k ≥ n, it
suffices to show that this holds at k = n. There, the numerator of (6) is equal to:

(7)

2c

c−1

2c

− (c + 1)n c+1 + 2n(n − 1) c+1 + (c − 1)e2/n (n − 1) c+1

So, we need to show (7) is negative. Here we have:


c−1
2c
(7) = n c+1 −(c + 1) + (1 − 1/n) c+1 (2 + (c − 1)e2/n (1 − 1/n))


c−1
2c
≤ n c+1 −(c + 1) + (1 − 1/n) c+1 (2 + (c − 1)(1 + 1/n)
as e2x (1 − x) ≤ 1 + x for x ∈ [0, 1]
c−1

The derivative of the quantity −(c + 1) + (1 − 1/n) c+1 (2 + (c − 1)(1 + 1/n)) with respect to n is
− 2
c+1
2(c−1)c( n−1
n )
, which is clearly positive. Also clearly this quantity is negative at n = 1 (it approaches
(c+1)n3
−(c + 1)) and approaches 0 as n → ∞. This implies that it is always negative, which in turn implies that
(7) is negative as desired.

Appendix B. Numerical analysis for Section 7
In this section, we will assume U (p) < n−K for some constant K > 2; thus the conclusions of
Proposition 3.6 hold.
To complete the proof of Theorem 7.4, we must verify certain concavity and monotonicity properties of
the function f defined by

( 
log2 (a/i)
if a ∈ (0, 1]
γ 1 − log
2 (a/r)
f (i, r, a, γ) =
2 log(r/i)
if a > 1
Proposition B.1. Let r, i be integers with r ≥ i ≥ 100 and let γ, a be real numbers with γ ≥ 2 log r, a ∈ (0, 1).
Let A be any random variable with domain (0, ∞) satisfying E[A] ≤ a. Then
E[f (i, r, A, γ)] ≤ f (i, r, a, γ)
42

Proof. Let us fix i, r, γ and define the function g : [0, 1] → R by
g(x) = f (i, r, x, γ)

We claim first that g ′ (x) ≥ 0 and g ′′ (x) ≤ 0; so g is increasing and concave-down. For, we have that:
g ′ (x) =

−2γ log(i/r) log(i/x)
x log3 (r/x)

As r ≥ i ≥ 1 and x ∈ [0, 1], the term log(i/r) is negative, the terms log(i/x), log(r/x) are positive, and γ is
positive. So overall g ′ (x) ≥ 0.
The second derivative is given by

−2γ log(r/i) log(r/x) + (log(r/x) − 3) log(i/x)
′′
g (x) =
x2 log4 (r/x)
For r ≥ 21, we have log(r/x) − 3 ≥ 0. The other terms here log(r/i), log(r/x), log(i/x), γ are all clearly
positive. So overall g ′′ (x) ≤ 0.
We next claim that g(1) ≥ 2 log(r/i), that is,
γ(1 −
As γ ≥ 2 log r, it suffices to show that
2 log r(1 −

log2 i
) ≥ 2 log(r/i)
log2 r

log2 i
) − 2 log(r/i) ≥ 0
log2 r

log i
The simplifies to showing 2 × log i × (1 − log
r ) ≥ 0, which is clear.
Thus, as g(x) is increasing on x ∈ (0, 1] and g(1) ≥ 2 log(r/i), it follows that g(x) ≤ g(1) for all x ∈ (0, ∞).
Having shown these concavity properties of the function g(x), we continue to prove the claimed result.
Consider the random variable A′ = min(A, 1). Observe that g(A) ≤ g(A′ ). Also, clearly E[A′ ] ≤ E[A] ≤ a.
By Jensen’s inequality E[g(A′ )] ≤ g(E[A′ ]). As g(x) is increasing on x ∈ (0, 1], we have that g(E[A′ ]) ≤ g(a).
This shows that E[g(A)] ≤ g(a) as desired.


Proposition B.2. For a ≤ 1 and r ≥ i + 1, the expression
is non-increasing in m.

c/m + f (i, r − 1, a, γ − c/m)

Proof. For a ≤ 1, the derivative of this quantity with respect to m is given by

−c log2 ai


a
m2 log2 r−1

which is clearly ≤ 0.



Proposition B.3. For a ∈ [0, 1], γ ≥ 0, and r ≥ 100, we have
2γ
−2γ
+ f (i, r − 1, a, γ +
) ≤ f (i, r, a, γ)
r log(a/r)
r log(a/r)
Proof. We compute the RHS minus the LHS. After collecting terms this is given by:


γ log2 ai r(2 log a)(1 + r log(1 − 1/r)) − 2r log r + r2 (log2 (r) − log2 (r − 1))
a
) log2 ( ar )
r2 log2 ( r−1

and we want to show this is positive.
Removing terms with obvious signs, it suffices to show that
(8)

r(2 log a)(1 + r log(1 − 1/r)) − 2r log r + r2 (log2 (r) − log2 (r − 1)) ≥ 0

Simple calculus shows that 1 + x log(1 − 1/x) ≤ 0 for all x ≥ 0; as a ≤ 0 this implies that r(2 log a)(1 +
r log(1 − 1/r)) ≥ 0. Thus, in order to show (8) it suffices to show that
43

(9)

r2 (log2 r − log2 (r − 1)) − 2r log r ≥ 0

To show this, we take a second-order Taylor expansion of log x around x = r; this gives us that
1
1
log(r − 1) ≤ log r − − 2
r
2r
Hence
r2 (log2 r − log2 (r − 1)) − 2r log r ≥ r2 (log2 r − (log r − 1/r − 1/(2r2 ))2 ) − 2r log r = log r − (1 +
Simple calculus shows that this is positive for r ≥ 4.

1 2
) .
2r


Appendix C. Selecting y ∈ [0, 1] for Lemma 9.8

In this section, we will assume U (p) < n−K for some constant K > 2; thus the conclusions of
Proposition 3.6 hold. We also suppose throughout that 3/2 ≤ α ≤ α∗ ≤ O(1), ρ ≤ 2.1, β ≤
1, δ ≥ β. (Other cases are covered already in Proposition 9.2.)
For any y ∈ [0, 1], let us define
T (y, α) = α max(h(y), h̄(y/α))
For any y ∈ [0, 1], Lemma 9.8 shows that the success probability of the RCA will be at least
n2−2y−T (y,α)−o(1) . We claim that it is always possible to select y so that this quantity is at least
n−1−o(1) ǫ−1.5−o(1) . Thus, it suffices to show that
2y + T (y, α) ≤ 3 + 1.5ρ

(10)
Let us define

(3 − β + δ)2 (2 − β + δ + ρ)
(2 − β + δ)2 (2 + δ)
We prove (10) in two parts. First, we show that it suffices to bound 2y + T (y, a) — that is, when we
replace α by a quantity which is (approximately) an appropriate upper bound on α∗ . Next, we show that
2y + T (y, a) can be regarded as a scalar function depending on only a few real parameters, which can be
tested exhaustively.
a=

Proposition C.1. For any y ∈ [0, 1] we have
∗

T (y, α) ≤ T (y, a) + o(1)

Proof. By Lemma 8.2, we have α ≤ α ≤ a + o(1 + ρ). As ρ = O(1), this implies that α ≤ a + o(1).
First, suppose that α = a + t, where 0 ≤ t ≤ o(1). By Proposition D.2, the derivatives of h, h̄ are bounded
by constants, and so αh(y) ≤ ah(y)+o(1) and similarly αh̄(y/α) ≤ ah̄(y/a)+o(1). So T (y, α) ≤ T (y, a)+o(1)
as desired.
Next, suppose that α ≤ a. Then αh(y) ≤ ah(y). Also, it can be mechanically verified that xh̄(y/x) is an
increasing function of x; thus αh̄(y/α) ≤ ah̄(y/a). This implies that T (y, α) ≤ T (y, a)

Next, we bound 2y + T (y, a) by using the crude but effective method of using a ǫ-net and essentially trying
every value of β, δ exhaustively.
Proposition C.2. There is y ∈ [0, 1] with 2y + T (y, a) ≤ 1 + 1.5ρ + o(1).
Proof. First, suppose that δ ≥ 3/2. Then we set y = 1 and obtain that

2y + T (y, a) ≤ 2 + a max(h(1), h̄(1/a))

As h(1) = 0, this implies that 2y + T (y, a) ≤ 2 + ah̄(1/a). This can be written as a rational function of
β, δ, ρ, and it can be verified mechanically that 2 + ah̄(1/a) ≤ 3 + 1.5ρ.
We next assume that β ∈ [0, 1], δ ∈ [β, 3/2]. We will show that in this range we can choose y such that
2y + T (y, a) ≤ 2.95 + 1.2ρ

We loop over choices of b = 0, s, 2s, . . . , 1−s and d = b−s, b, b+s, b+2d, . . ., 3/2−s and r = 0, s, 2s, . . . , 2.1
where s = 0.001. For each such choice b, d, r we choose some y ∈ [0, 1] and compute an upper bound on
2y + T (y, a) for β, δ, ρ in the range β ∈ [b, b + s], δ ∈ [d, d + s], ρ ∈ [r, r + s]. We denote this interval by Ib,d,r .
(Note that the inequality d ≥ b − s comes from the fact that we must have δ ≥ β.)
44

Now, suppose we have fixed some choice of b, d, y and we want to show that in this region
2y + a max(h(y), h̄(y/a)) ≤ 2.95 + 1.5ρ

(11)

It can be mechanically verified that in the interval Ib,d,r we have
a ≤ amax =

(3 − b + d)2
(r + s)(3 − b + d − s)2
+
(2 + d)(2 − b + d) (2 + d)(2 − b + d − s)2

As h̄ is an increasing function, a sufficient condition to show (11) is that

2y + amax max(h(y), h̄(y/amax )) ≤ 2.95 + 1.5r

(12)

It is easy to compute using standard numerical techniques an upper bound on the quantity
max(h(y), h̄(y/amax )) over the interval Ib,d,r . (This upper bound is not affected by the value of ρ) For
example, h̄(z) is an increasing function of β, δ.
Thus, we can compute an upper bound on 2y + amax max(h(y), h̄(y/amax )) in the interval Ib,d,r ; if this
upper bound is at most 2.95 + 1.5r, then this shows that (12) and hence (11) holds.
We wrote C code (omitted here) to loop over all b, d, r and perform the above calculation. This procedure
works for any choice of y. The method we used was to approximately satisfy the constraint h(y) = h̄(y/amax )
at β = b, δ = d. With this choice of y, we satisfy (12) for all intervals.3

Putting these cases together, we have our desired result:
Proposition C.3. Suppose 3/2 ≤ α ≤ α∗ and ρ ≤ 2.1 and β ∈ [0, 1]. Then there is y ∈ [0, 1] such that
2y + T (y, α) ≤ 2.95 + 1.5ρ + o(1)

Appendix D. Properties of the functions h, h̄
We discuss here some properties of the functions h(x), h̄(x). We repeat the functions h, h̄ for convenience.
In this section, we will assume U (p) < n−K for some constant K > 2; thus the conclusions of
Proposition 3.6 hold.


2(2 + δ)(log(3 − β + δ) − log(2 − β + δ + x))
h(x) = 2(2 + δ)(log(3 − β + δ) − log(2 + δ)) + 2(β − x)


2(1 − x)
h̄(x) =

(δ + 2)(1 − x)(5 − 2β + 2δ + x)
(3 − β + δ)2

if x ≥ β
if x ≤ β ≤ 1
if β ≥ 1

Proposition D.1. We have 10/9 ≤ h̄(0) ≤ 20/9. Furthermore, if β ≤ 3/2 then h̄(0) ≤ 2.
Proof. h̄(0) is a rational function of β, δ so this fact can be verified mechanically for δ ≥ β, β ∈ [0, 2].



Proposition D.2. We have −2 ≤ h′ (x) ≤ −4/3 − Ω(1)

Proof. When β ≥ 1 or x ≤ β then h′ (x) = −2 and so this is clear. When β ≤ x ≤ 1 we have
h′ (x) =

−2(2 + δ)
2−β+δ+x

As β ≤ 2 + o(1) and δ ≥ δ0 , for n sufficiently large this is negative. Hence the maximum value occurs at
β = 0, x = 1 yielding
2
2
h′ (x) ≤ −2 +
≤ −4/3 − Ω(1)
≤ −2 +
3+δ
3 + δ0
The minimum value of h′ (x) occurs at β = x yielding h′ (x) ≥ 2.

3Note that the relevant calculations were performed using double-precision floating point (with the default rounding mode),
instead of rigorous interval arithmetic. This was done for the sake of easy implementation using standard numerical libraries. However, in fact, we observed that these constraints were both satisfied with significant slack — we saw that
2y + amax max(h(y), h̄(y/amax )) − 2.95 − 1.5r ≤ −0.01. Thus we do not expect that this slight numerical error will affect
the validity of the results.
45

Proposition D.3. We have −4 + Ω(1) ≤ h̄′ (x) ≤ −Ω(1).
Proof. We compute the derivative of h̄ as:
2(δ + 2)(−β + δ + x + 2)
(−β + δ + 3)2
This is clearly a decreasing function of x, so it achieves its minimum value at x = 1. There it is equal to
−2(2 + δ)
−2(2 + δ0 )
−2(2 + δ)
≥ −4 + Ω(1)
≥
≥
h̄′ (1) =
3−β+δ
3−2+δ
1 + δ0
h̄′ (x) = −

Similarly, h̄′ (x) achieves its maximum value at x = 0 where we have

2(δ + 2)(β − δ − 2)
(−β + δ + 3)2
One can see that this is U-shaped as a function of β. So its maximum value occurs at either β = 0 or
β = 2. At those points respectively we have
h̄′ (0) =

h̄′ (0) =

−2(2 + δ)2
≤ −8/9
(3 + δ)2

and
h̄′ (0) = −2 +

2
2
≤ −2 +
≤ −Ω(1)
(1 + δ)2
(1 + δ0 )2


Proposition D.4. For β ∈ [0, 1] and x ∈ [0, 1] we have h̄(x) ≤ h(x).

Proof. Observe that h(1) = h̄(1) = 0. So it suffices to show that h̄′ (x) ≥ h′ (x) for x ∈ [0, 1]. We have
that h̄′ (x) = −2(δ+2)(−β+δ+x+2)
. This is a rational function, and so it can be mechanically verified that
(−β+δ+3)2
′
h̄ (x) ≥ −2 for x ∈ [0, 1] and β, δ ∈ [0, 1]. As h′ (x) = −2 when x ≤ β, this automatically implies that
h̄′ (x) ≥ h′ (x) for x ≤ β.
−2(2+δ)
When x ≥ β, we have that h′ (x) = 2−β+δ+x
. So to show that h̄′ (x) ≥ h′ (x), we must show that
−2(δ + 2)(−β + δ + x + 2)
−2(2 + δ)
≥
≥0
2
(−β + δ + 3)
2−β+δ+x
Again, this is a rational function, so it can be mechanically verified that this holds in the indicated
range.


46

