Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs

Abstract

We consider multiobjective and parametric versions of the global minimum cut problem in undirected graphs and bounded-rank hypergraphs with multiple edge cost functions. For a fixed number of edge cost functions, we show that the total number of supported non-dominated (SND) cuts is bounded by a polynomial in the numbers of nodes and edges, i.e., is strongly polynomial. This bound also applies to the combinatorial facet complexity of the problem, i.e., the maximum number of facets (linear pieces) of the parametric curve for the parametrized (linear combination) objective, over the set of all parameter vectors such that the parametrized edge costs are nonnegative and the parametrized cut costs are positive. We sharpen this bound in the case of two objectives (the bicriteria problem), for which we also derive a strongly polynomial upper bound on the total number of non-dominated (Pareto optimal) cuts. In particular, the bicriteria global minimum cut problem in an n-node graph admits $O(n^3 \log n)$ SND cuts and $O(n^5 \log n)$ Pareto optimal cuts. These results significantly improve on earlier graph cut results by Mulmuley (SIAM J Comput 28(4):1460–1509, 1999) and Armon and Zwick (Algorithmica 46(1):15–26, 2006). They also imply that the parametric curve and all SND cuts, and, for the bicriteria problems, all Pareto optimal cuts, can be computed in strongly polynomial time when the number of objectives is fixed.

1 Introduction

We consider the multicriteria version of the global minimum cut problem in undirected graphs. Global minimum cut is extensively studied in combinatorial optimization since many practical problems in, e.g., routing (subtour elimination), communications and electrical networks, contain it as a subproblem [2]. Let $G = (V, E)$ be an undirected graph, and $c^1, \ldots , c^k : E \rightarrow \mathbb {R}$ be k cost functions, or criteria, defined on its edges. A cut X in G is a subset of nodes $X\subseteq V$ such that $\emptyset \ne X \ne V$, and it determines the set $\delta (X)$ of edges with exactly one end in X. The cost of cut X w.r.t. criterion j is $c^j(X) := c^j(\delta (X))$.

Many concepts and algorithms for global minimum cut generalize to hypergraphs.¹ We recall that a hypergraph is a finite set of vertices V, together with a family E of subsets of V. Thus each $e\in E$ is a vertex subset $e\subseteq V$, and is called a hyperedge, or simply, an edge. We say that hypergraph $G = (V,E)$ is rank-$\rho$ if $|e|\leqslant \rho$ for all $e\in E$. Thus an undirected graph is a rank-2 hypergraph, and is rank-$\rho$ for all $\rho \geqslant 2$. A cut X in hypergraph G is a non-trivial node subset, i.e., $\emptyset \ne X\subset V$. It cuts the set of edges $\delta (X) := \{e\in E : e \cap X\ne \emptyset \ne e{\setminus } X\}$. Notice that this matches the definition of a cut for a graph. A hypergraph is connected if all cuts X are non-empty, i.e., $\delta (X) \ne \emptyset$ for every cut X. Given edge costs $c^j(e) (e\in E, j = 1, \dots , k$), the cost of a cut X w.r.t. $c^j$ is the total cost $c^j(X) := c^j(\delta (X)) = \sum _{e\in \delta (X)} c^j(e)$ of all the edges crossed by cut X.

Ideally we would like a cut that simultaneously minimizes all criteria, but such a solution usually does not exist. Therefore, we focus on Pareto optimal solutions, i.e., solutions that cannot be improved upon in any criterion without degrading another criterion. Each cut X is associated with its criteria vector (or point) $c(X) := (c^1(X),\ldots ,c^k(X))$ in the criteria space $\mathbb {R}^k$. Let $\mathcal {C}$ denote the set of all cuts, and $Y := \{ c(X) : X\in \mathcal {C}\}$ denote the image in the criterion space of all the cuts (note that different cuts may give rise to the same criteria point). A point $c(X')$ dominates c(X), and by extension, cut $X'$ dominates X, if $c^j(X') \leqslant c^j(X)$ for all $j=1,\ldots ,k$, and $c^j(X') < c^j(X)$ for at least one j. If there is no $c(X') \in Y$ that dominates c(X), then the point c(X), and by extension, the cut X itself, is non-dominated, or Pareto optimal. In order to derive strongly polynomial bounds and algorithms, when we study the multicriteria minimum cut problem we assume that all edge costs are nonnegative, as negative edge costs may give rise to NP-hard minimization problems; and that all cuts have strictly positive costs, i.e., that $c^j(X) > 0$ for every objective j and cut X, for otherwise the hypergraph $(V,E^{>0,j})$ induced by the positive-cost edges (i.e., with edge set $E^{>0,j}=\{e\in E : c^j(e) > 0\}$) is not connected and may have an exponential number of minimum (zero-cost) cuts.

The computation of Pareto optimal points (i.e. non-dominated points) is related to the field of parametric optimization. For $j = 1, \dots , k-1$ we put a non-negative parameter $\mu _j$ on criterion j, and we consider the parametric optimization problem

$$\begin{aligned} c^*(\mu ) := \min _{X\in \mathcal {C}} c_\mu (X) \quad \text {where}\quad c_\mu (X) := \sum _{j=1}^{k-1} \mu _j c^j(X) + c^k(X). \end{aligned}$$

(1)

Notice that a multicriteria problem with k objectives corresponds to a parametric problem with a single objective and $k-1$ parameters. We call $c_\mu$ the parametrized objective. If there is some positive parameter vector $\mu \in \mathbb {R}^{k-1}_{>0}$ (i.e., with all components $\mu _j > 0$) such that cut X minimizes $c_{\mu }$ then c(X) is Pareto optimal, we call it a supported non-dominated (SND) point, and the cut X an SND cut. The Pareto optimal points that are not SND points are called unsupported non-dominated (UND) points, see Fig. 1.

A natural object to define is the dominant $\mathcal {D}$ of the convex hull of Y, i.e., the set of all points $x\in \mathbb {R}^k$ that satisfy $x\geqslant y$ for some y in the convex hull of Y. The boundary of $\mathcal {D}$ (its lower convex hull) is the set of all points in $\mathcal {D}$ “accessible” as optimal solutions for parametrized objectives $c_{\mu }$ with $\mu \geqslant 0$. Thus all SND points must lie on the boundary of $\mathcal {D}$, and every vertex of $\mathcal {D}$ is actually an SND point (when the costs are in “general position”, the converse will also be true, namely, that every SND point is a vertex of $\mathcal {D}$. Otherwise, non-vertex SND points may arise as alternate optima for certain parameter vectors $\mu$). The optimum cost function $c^* : \mathbb {R}^{k-1}_+ \mapsto \mathbb {R}$ is piecewise linear and concave, and its graph is in a sense the convex dual of the boundary of $\mathcal {D}$ (which is piecewise linear and convex, e.g., [8, 10]). This duality interchanges vertices and facets, and so the fact that the vertices of $\mathcal {D}$ are SND points means that the facets of the graph of $c^*$ also correspond to SND points. See Fig. 1 for an example of this for $k = 2$.

Fig. 1

a Is an example of SND points, UND points, and $\mathcal {D}$. Each point corresponds to a cut X with values $(c^1(X), c^2(X))$. SND points are black and are labeled $C_1$, $C_2$, ..., UND points are gray, and dominated points are white. b Plots $c^*(\mu )$ for the same data. The extreme points and line segments of both graphs are labeled such that extreme point $C_1$ of a corresponds to line segment $C_1$ of the b, extreme point $b_2$ of the chart a is an example o corresponds to line segment $b_2$ of a, etc.

In fact, our results apply to a slightly more general parametric minimum cut problem than arises from the multicriteria version, wherein we do not require either the objectives or the parameters to be nonnegative. However, in order to derive strongly polynomial bounds and algorithms, when we study the parametric minimum cut problem we make two assumptions on the parametric cost values that are similar to the assumption on the cost function values for the multicriteria version: we assume that all parametrized edge costs $c_{\mu }(e) := \sum _{j=1}^{k-1} \mu _j c^j(e) + c^k(e)$ are nonnegative (though a single-criterion cost function $c^j(e)$ may be negative), and that all cuts have positive parametrized costs, i.e., that $c^*(\mu ) > 0$. Thus we restrict attention to the following relevant region in the parameter space:

$$\begin{aligned} M = \left\{ \mu \in \mathbb {R}^{k-1} : c_{\mu }(e) \geqslant 0~\forall e\in E, ~\text { and } c_{\mu }(X) > 0~\forall X\subset V,~ X\not =\emptyset \right\} . \end{aligned}$$

Note that M is a convex polyhedral set, defined by a finite system of strict and non-strict linear inequalities. Readers who find this slight generalization confusing can imagine, as in the multicriteria version, that every objective $c^j$ is nonnegative and its minimum is positive (i.e., its support graph is connected), in which case M is just the nonnegative orthant $\mathbb {R}^{k-1}_+$.

Define $\mathcal {S}$ as the set of cuts $X\in \mathcal {C}$ which minimize $c_\mu (X)$ for some $\mu \in M$; i.e., $\mathcal {S}$ is the set of all SND cuts.

We define the combinatorial facet complexity ² of the parametric minimum cut problem to be the maximum number of facets of the graph of $c^*$, which is equivalent to the maximum number of vertices of $\mathcal {D}$, and to the maximum number of SND points. Our main interest here is to study the combinatorial facet complexity of global minimum cut for hypergraphs, and thus also for graphs. We also derive sharper bounds on combinatorial facet complexity for the bicriterion case $k = 2$.

A natural subproblem of parametric minimum cut is solving single-criterion (ordinary) minimum cut, e.g., for some fixed value of $\mu$. For graphs, the fastest deterministic algorithms for this problem run in $O(|E|\cdot |V| + |V|^2 \log |V|)$ time (Nagamochi and Ibaraki [30], and Stoer and Wagner [42]). The fastest randomized algorithm runs in $O(|E| \log ^3 |V|)$ time (Karger [17]). These algorithms are faster than minimum s–t-cut algorithms that are based on network flows. See [31] for a detailed treatment of graph connectivity problems. For hypergraphs there exist polynomial time algorithms for finding a minimum cost cut in a hypergraph with nonnegative edge costs, see [20, 25, 37].

The multicriteria versions of several combinatorial optimization problems have been extensively studied, see Ehrgott [8] for a comprehensive survey. These problems are often intractable in the sense that the size of the set of (supported) Pareto optimal points grows exponentially in the input size. Furthermore, it is often hard even to verify if a given point is Pareto optimal. For example, Carstensen [3] shows that the combinatorial facet complexity of the minimum s–t-cut problem in a graph (namely, to find a minimum cost cut X that separates two given vertices s and t, in the sense that $\left| X\cap \{s,t\}\right| =1$) is exponential, even for a single parameter (two cost functions). Mulmuley [28] gives a simpler proof of this result. In addition, it follows from Papadimitriou and Yannakakis [34, Theorem 6] that the decision version of the bicriteria minimum s–t-cut problem in a graph is strongly NP-hard.

Multicriteria global minimum cut in graphs are an exception to such intractability results. Mulmuley [28, Theorem 3.10] considers the combinatorial facet complexity of the parametric minimum cut problem with two objectives that may be negative, but where all parametric edge costs are positive (a slight restriction, for the bicriteria case, of our more general parametric framework above). His Theorem 3.10 implies that the combinatorial facet complexity is $O(|V|^{19}\log |V| \log c_{\mathrm {max}})$, where $c_{\mathrm {max}} := \max _e \max \{c^1(e),c^2(e)\}$ is the maximum edge cost. This is a weakly polynomial bound, but Mulmuley also claims (without detailed proof) that the bit sizes of the costs can be assumed to have polynomial size without affecting the combinatorial facet complexity, and this yields a strongly polynomial bound. In addition, Armon and Zwick [2] show that, when the number k of criteria is fixed, the decision version of the multicriteria minimum cut problem in graphs can be solved in strongly polynomial time. They also point out the existence, when k is fixed, of a pseudo-polynomial time algorithm to find all the Pareto optimal points, and of a fully-polynomial time approximation scheme (FPTAS) for finding an approximate Pareto set, a notion defined by Papadimitriou and Yannakakis  [34]. All these results may be surprising since the single-objective global minimum cut problem may be solved by solving $|V|-1$ minimum s–t-cut problems (e.g., by fixing s and letting t vary over the other nodes). Thus, for example, the parametric function $c^*$ is the pointwise minimum of $|V|-1$ parametric minimum s–t cut functions, each of which possibly has an exponential number of breakpoints.

All these positive results rely on the deep and far-reaching fact that the single-criterion global minimum cut problem on graphs has at most a strongly polynomial number of near-optimal solutions. Indeed, given $\alpha \geqslant 1$, call a cut $\alpha$-$approximate$ if its cost is less than $\alpha$ times the minimum. For global minimum cut in graphs, Dinitz et al. [6] showed that there are at most $\left( {\begin{array}{c}|V|\\ 2\end{array}}\right) = \theta (|V|^2)$ minimum (i.e., 1-approximate) cuts, and that this bound is tight. Nagamochi et al. [33] and Henzinger and Williamson [14] show that this bound also applies to the number of $\alpha$-approximate cuts for all $\alpha < 4/3$ and all $\alpha < 3/2$, respectively; the latter authors also show that 3 / 2 is the largest approximation factor for which this result holds. More generally, Karger [16] states (see [19] for a detailed proof) that for every $\alpha > 1$ the number of $\alpha$-approximate cuts is $O(|V|^{2\alpha })$. All these results are subsumed by Karger’s result [17] that for every $\alpha \geqslant 1$ the number of $\alpha$-approximate cuts in a graph is $O(|V|^{\left\lfloor 2\alpha \right\rfloor })$.

In this paper, we give a strongly polynomial upper bound on the combinatorial facet complexity of global minimum cut on rank-$\rho$ hypergraphs. Our bound hides a constant that depends at least exponentially on $\rho$. For the case of two nonnegative objectives (with positive minimum cut values), we also derive sharper bounds that are much smaller, and follow from a simpler proof, than in [28].

As pointed out above, our bounds of the combinatorial facet complexity of global minimum cut depend on a strongly polynomial upper bound on the number of approximate optimal solutions to global minimum cut. Hence our first step, in Sect. 2, is to generalize the results on approximate global minimum cut from graphs to hypergraphs. In particular, we extend a recent result of Kogan and Krauthgamer [21]; a proof of our extended result is found in the Appendix. Given this, we derive in Sect. 3 a strongly polynomial bound on the combinatorial facet complexity of global minimum cut on hypergraphs. Then Sect. 4 studies in detail the bicriteria case, i.e., when $k=2$. Finally, Sect. 5 shows how to adapt existing parametric algorithms for computing the graph of the parametric function $c^*$, the boundary of $\mathcal {D}$ (SND points and cuts), and for $k=2$, the set of all Pareto optimal cuts.

2 Approximate minimum cuts for a single objective

In this section we consider a hypergraph $G=(V,E)$ with a single, nonnegative edge cost function c that has positive minimum cut value (without loss of generality we can discard all zero cost edges, and then G has positive minimum cut value if and only if it is connected). We assume that all edges $e\in E$ have size $2 \leqslant |e| \leqslant |V|-1$, as edges with $|e| = 1$ or |V| do not contribute to any cut. We also assume that distinct edges in E span different sets of vertices, and thus that $|E| = O(|V|^{\rho })$, since if G contains “parallel” edges that span the same set of vertices, we may replace them by a single edge with cost equal to the sum of the costs of the parallel edges.

Theorem 1

(Adapted from Kogan and Krauthgamer [21]) For every fixed scalar $\alpha \geqslant 1$ and integer $\rho \geqslant 2$, the number of $\alpha$-approximate cuts in all rank-$\rho$ hypergraphs $G = (V,E)$ with nonnegative edge costs c and positive minimum cut cost, is $O\left( |V|^{2\alpha }\right)$.

While Kogan and Krauthgamer only present this result for the case when $\alpha$ is half-integer,³ the proof in the Appendix shows that it actually holds for all $\alpha \geqslant 1$.

Karger’s $O\left( |V|^{\lfloor 2\alpha \rfloor }\right)$ bound for graphs [17] is tighter than that in Theorem 1 when $\rho = 2$. When combined with a simple approximation of hypergraph cuts as graph cuts, it also leads to tighter bounds for $\rho = 3$, and for $\rho = 4$ and a small (but important in the sequel) range of values of $\alpha$. To show this, in the next Proposition, we recall a general approximation method (see, e.g., Ihler et al. [15]) and derive consequences for bounding the number of $\alpha$-approximate cuts.

Proposition 2

For every fixed integer $\rho \geqslant 3$, fixed scalar $\alpha \geqslant 1$, and rank-$\rho$ hypergraph $G = (V,E)$ with nonnegative edge costs c and positive minimum cut cost, the number of $\alpha$-approximate cuts is $O\Big (|V|^{\left\lfloor 2 B(\rho )\alpha \right\rfloor }\Big )$ where $B(\rho ) = 1$ if $\rho = 3$, and $B(\rho ) = {\lfloor \rho ^2 /4 \rfloor }/(\rho -1) \leqslant \frac{\rho }{4} + \frac{1}{3}$ if $\rho \geqslant 4$.

Proof

We prove the result by approximating the minimum cut problem in hypergraph $G = (V,E)$ with edge costs c, by the minimum cut problem in the complete graph $K(V) = (V,E_{K(V)})$ with edge costs $\tilde{c}$, whereby each edge $e\in E$ is replaced by a clique on the nodes in e and each edge in the clique has cost $c(e)/(|e|-1)$, i.e., by letting

$$\begin{aligned} \tilde{c}(i,j) = \sum _{e\in E : \{i,j\}\subseteq e} \frac{c(e)}{|e|-1} \quad \text {for all }\{i,j\}\in E_{K(V)}. \end{aligned}$$

(2)

In particular, every cardinality-2 edge $e = \{i,j\}\in E$ contributes its full cost c(e) to $\tilde{c}(i,j)$, and thus to the cost $\tilde{c}(X)$ of every cut X in K(V) that crosses it. Note also that every cardinality-3 edge $e\in E$ that is crossed by cut X has two of its nodes on one side of the cut and the other node on the other side, and thus also contributes its exact cost $2(c(e)/2) = c(e)$ to $\tilde{c}(X)$. Therefore [as it is well known, e.g., Ihler et al. [15]), when $\rho \leqslant 3$ this transformation preserves all cut values, i.e., $\tilde{c}(X)$] ${=}c(X)$ for every cut X. The result then follows from Karger’s bound when $\rho \leqslant 3$.

Now assume that $\rho \geqslant 4$. A cut X that crosses an edge $e\in E$ with cardinality ${|e|} \geqslant 4$ crosses at least $|e|-1$ edges in the clique K(e) (when exactly one node of e is on one side of the cut), and at most $\lfloor |e|^2 /4 \rfloor$ such edges (when half the nodes of e are on either side). Thus every edge $e\in E$ crossed by X contributes at least c(e) and at most $(\lfloor |e|^2 /4\rfloor )\frac{c(e) }{|e|-1}\leqslant \frac{\lfloor \rho ^2 /4\rfloor }{\rho -1}\, c(e) = B(\rho )c(e)$ to the cost $\tilde{c}(X)$. Therefore,

$$\begin{aligned} c(X) \leqslant \tilde{c}(X) \leqslant B(\rho )\, c(X). \end{aligned}$$

Note that

$$\begin{aligned} B(\rho ) \leqslant \left( \frac{\rho }{4} + \frac{1}{4}\left( 1+\frac{1}{\rho -1}\right) \right) \leqslant \frac{\rho }{4} + \frac{1}{3}, \end{aligned}$$

where the last inequality follows from $\rho \geqslant 4$.

Let $X^*$ denote a minimum cut for $(K(V), \tilde{c})$. If X is an $\alpha$-optimal cut for (G, c), i.e., $c(X)\leqslant \alpha \, \min _{Y\in \mathcal {C}} c(Y)$, then we have

$$\begin{aligned} \tilde{c}(X) \le B(\rho )\, c(X) \leqslant B(\rho )\, \alpha \, \min _{Y\in \mathcal {C}} c(Y) \leqslant B(\rho )\, \alpha \, c(X^*) \le B(\rho )\, \alpha \, \tilde{c}(X^*), \end{aligned}$$

implying that X is a $\big (B(\rho )\, \alpha \big )$-optimal cut for $(K(V), \tilde{c})$. The result then again follows from Karger’s bound when $\rho \geqslant 4$. $\square$

Combining Theorem 1 and Proposition 2 (and noting that when $\rho = 4$ and $1 < \alpha < 9/8, \lfloor 2\,B(\rho )\,\alpha \rfloor = 2 = \lfloor 2\alpha \rfloor$), we obtain:

Corollary 3

For every fixed scalar $\alpha \geqslant 1$ and fixed integer $\rho \ge 2$, the number of $\alpha$-approximate cuts in all rank-$\rho$ hypergraphs $G = (V,E)$ with nonnegative edge costs c and positive minimum cut cost, is

$$\begin{aligned} O\left( |V|^{\lfloor 2\alpha \rfloor }\right)&\text {for }\rho \leqslant 3,\text { and}\\&\text {for }\rho = 4\text { when }1 \leqslant \alpha < 9/8; \\ O\left( |V|^{2\alpha }\right)&\text {for }\rho \geqslant 4\text { when }\alpha \geqslant 9/8,\text { and}\\&\text {for all }\rho \geqslant 5. \end{aligned}$$

These results show that the dependence of the number of $\alpha$-approximate cuts is polynomially bounded in the number |V| of vertices when $\alpha$ and $\rho$ are fixed. On the other hand, it is known (see, e.g., an example in [14] and its immediate generalization to larger half-integer values of $\alpha$), that the dependence on $\alpha$ is exponential. Similarly, Kogan and Krauthgamer present in [21] a family of instances showing that the dependence on $\rho$ (through the “hidden” multiplicative constant in the $O\left( |V|^{2\alpha }\right)$ expression) is at least exponential.

3 Minimum cuts with multiple edge costs

We are now given a hypergraph $G=(V,E)$, and k edge cost functions $c^1,\ldots , c^k : E \rightarrow \mathbb {R}$, where $k \geqslant 2$ is fixed. Before considering the multiobjective version of the problem, we start with its parametric version. Recall that for $\mu \in \mathbb {R}^{k-1}$ the parametrized cut cost is $c_{\mu }(X) = \sum _{e\in \delta (X)} c_{\mu }(e)$ for all cuts X in G.

Our strategy for proving the following theorem is to express the parameter space M first as a union of regions defined by edges, then to cut each region into subregions via a hyperplane dissection. The region for edge a is the part of M where some minimum cut has a as a maximum cost edge w.r.t. $c_\mu$. The hyperplanes belong to a family of hyperplanes constructed from $c_\mu (a)$ and at successive relative distance $\beta$ for some appropriate $\beta > 1$, and from $c_\mu (e)$ for every other edge e. The resulting subregions are small enough that we can apply Corollary 3 to get a small number of minimum cuts per region, and then we sum up across all subregions to get our bound.

In view of Corollary 3, we introduce the following notation: given a number $r\in \mathbb {R}\cup \{\pm \infty \}$, and real-valued functions $f_{\rho }$ and g, where $f_{\rho }$ (and possibly g) depends on a fixed parameter $\rho$, we say that

$$\begin{aligned} f_{\rho }(n) = O_{\rho ,r}(g(n))~\text { iff }&f_{\rho }(n) = O\left( g(n)\right) \text { when }\rho < r;\text { and}\\&f_{\rho }(n) = O\left( g(n) \, n^{\epsilon }\right) \text { for all }\epsilon > 0,\text { when }\rho \geqslant r. \end{aligned}$$

In particular, $O_{\rho ,+\infty }(g(n))$ is just O(g(n)).⁴ Corollary 3 thus implies that, when $\epsilon > 0$ approaches 0, the number of $(1+\epsilon )$-approximate cuts in all rank-$\rho$ hypergraphs $G = (V,E)$ with nonnegative edge costs c and positive minimum cut cost, approaches $O_{\rho ,5}(|V|^2)$, i.e., $O(|V|^2)$ if $\rho \le 4$ and $|V|^{2+o(1)}$ if $\rho \ge 5$.

Theorem 4

Given a fixed integer $\rho \geqslant 2$, a rank-$\rho$ hypergraph $G=(V,E)$ and k edge cost functions $c^1,\ldots , c^k$, the total number of cuts X minimizing $c_{\mu }(X)$ over all $\mu$ in M is $O_{\rho ,5}\Big (|E|^k |V|^2 \log ^{k-1}|V|\Big )$.

Proof

For every cut X in G let

$$\begin{aligned} M(X) = \left\{ \mu \in M : c_{\mu }(X) = \min _W\{ c_{\mu }(W) : \emptyset \not =W \subset V\}\right\} \end{aligned}$$

denote the subset of parameter vectors in M for which X is a minimum cut. Recall that $\mathcal {S}$ is the set of all SND cuts. For every edge $a \in E$ let

$$\begin{aligned} \mathcal {S}_{a} = \left\{ X \in \mathcal {S}: a \in \mathop {{{\mathrm{arg\,max}}}}\limits _{e \in X} c_{\mu }(e) \text{ for } \text{ some } \mu \in M(X)\right\} \end{aligned}$$

denote the set of all cuts X such that, for some $\mu$ for which X is a minimum cut, a is an edge in X with largest cost $c_{\mu }(a)$. It suffices to show that $|\mathcal {S}_{a}| = O_{\rho ,5}\Big (|E|^{k-1}|V|^2 \log ^{k-1}|V|\Big )$ and the result will follow.

Thus, in the rest of this proof, fix edge $a\in E$ such that $\mathcal {S}_{a}\not =\emptyset$. For every $X \in \mathcal {S}_{a}$ let

$$\begin{aligned} M_a(X) = \left\{ \mu \in M(X) : a \in \mathop {{{\mathrm{arg\,max}}}}\limits _{e \in X} c_\mu (e)\right\} \end{aligned}$$

so that $M_a(X)\not =\emptyset$, and let

$$\begin{aligned} M_a = \bigcup _{X\in \mathcal {S}_{a}} M_a(X) \end{aligned}$$

denote the set of parameter vectors for which edge a has maximum cost in a minimum cut. We will cover the parameter region $M_a$ with a number $L = O\left( |E|^{k-1}\log ^{k-1}|V|\right)$ of regions $R_l$ ($l=1,\dots ,L$). We will then derive, for each region $R_l$, an $O_{\rho ,5}(|V|^2)$ bound on the total number of cuts W in $\mathcal {S}_a$ that are minimum for some $\mu \in R_l\cap M_a$, i.e., such that $R_l\cap M_a(W) \not = \emptyset$. The covering condition $M_a = \bigcup _{l=1}^L R_l$ implies $\mathcal {S}_a = \bigcup _{l=1}^L\{ W\in S_a : R_l\cap M_a(W) \not = \emptyset \}$, and the result will follow.

First, note that for every $\mu \in M_a$ and cut W such that $a \in {{\mathrm{arg\,max}}}_{e \in W} c_{\mu }(e)$ we have

$$\begin{aligned} c_\mu (a) \leqslant c_{\mu }(W) \leqslant |E|c_\mu (a). \end{aligned}$$

(3)

Since $c_{\mu }(W) > 0$ for every $W\in \mathcal {S}_{a}\not =\emptyset$, this implies $c_{\mu }(a) > 0$.

Now fix a constant $\beta > 1$ whose value will be specified later, and let $\alpha = \frac{\beta -1}{ |E|} > 0$. Compute $p = 1 + \lceil \log \frac{|E|^2}{\beta -1} / \log \beta \rceil$ so that $\alpha \beta ^{p - 1} > |E|$, and observe that $p = O(\log |V|)$ (since $p = O(\log |E|)$, and $|E| = O(|V|^\rho )$ due to no parallel edges, and $\rho$ being constant).

Define the functions $g_i : \mathbb {R}^{k-1}\rightarrow \mathbb {R}$ by $g_0(\mu ) = 0$ and

$$\begin{aligned} g_{i}(\mu )=\alpha \,\beta ^{i-1}c_{\mu }(a) \quad \text {for }i=1,\dots ,p,\quad \text {and} \end{aligned}$$

$g_{p+1}(\mu ) = +\infty$.

Inequality (3) implies that, for every $\mu \in M_a$, every cut W such that $a \in {{\mathrm{arg\,max}}}_{e \in W} c_{\mu }(e)$, and every $e\in W$,

$$\begin{aligned} c_{\mu }(a) \leqslant c_{\mu }(W) \leqslant |E|c_\mu (a) < g_p(\mu ). \end{aligned}$$

(4)

Since $c_{\mu }(a) > 0$,

$$\begin{aligned} 0 = g_0(\mu ) < g_1(\mu ) < \dots < g_p(\mu ) < g_{p+1}(\mu ) = +\infty \end{aligned}$$

(5)

for all $\mu \in M_a$.

For each $e\in E$ and each $i=1,\ldots ,p$, the hyperplane $H_{i,e} = \{\mu \in \mathbb {R}^{k-1} : g_i(\mu ) = c_\mu (e)\}$ divides $\mathbb {R}^{k-1}$ into at most two regions, one where $g_i(\mu ) \leqslant c_\mu (e)$, and the other where $g_i(\mu ) \geqslant c_\mu (e)$.

Recall that, for fixed dimension d, N hyperplanes divide the d-dimensional space $\mathbb {R}^d$ into $O(N^d)$ regions ([41], see also [45] for further references). Thus the $O(|E| \log (|V|))$ hyperplanes $H_{i,e}$ define regions $R_1,\dots ,R_L$ that cover the set $M_a \subset \mathbb {R}^{k-1}$, and $L = O\left( |E|^{k-1}\log ^{k-1}|V|\right)$. By (5), for each $l\in \{1,\dots ,L\}$ and each $e\in E$ there exists an index $i(e,l)\in \{0,1,\dots ,p\}$ such that

$$\begin{aligned} R_l \cap M_a = \left\{ \mu \in M_a : g_{i(e,l)}(\mu )\leqslant c_{\mu }(e) \leqslant g_{i(e,l)+1}(\mu )~\forall e\in E\right\} . \end{aligned}$$

Consider any such region $R_l$ and any cut $W\in \mathcal {S}_a$. Note that (4) implies that $i(e,l) \leqslant p-1$ for all $e\in \delta (W)$. Let

$$\begin{aligned} R_l(W) = \left\{ \mu \in R_l : a \in \mathop {{{\mathrm{arg\,max}}}}\limits _{e \in W} c_{\mu }(e)\right\} , \end{aligned}$$

the subset of $R_l$ such that our fixed arc a has the maximum $c_\mu (a)$ value among all edges in cut W. Then for every $\mu \in R_l(W)$, the definition of i(e, l) implies that

$$\begin{aligned} c_{\mu }(W)\geqslant & {} c_{\mu }(a) + \sum _{e\in \delta (W){\setminus }\{a\}\; : \; 1\leqslant i(e,l)\leqslant p-1}c_{\mu }(e) \\\geqslant & {} c_{\mu }(a)\left( 1 + \sum _{e\in \delta (W){\setminus }\{a\}\; :\; 1\leqslant i(e,l)\leqslant p-1} \alpha \,\beta ^{i(e,l)-1} \right) . \end{aligned}$$

If we define

$$\begin{aligned} \gamma _{l}(W) = 1 + \sum _{e\in \delta (W){\setminus }\{a\}\; :\; 1\leqslant i(e,l)\leqslant p-1} \alpha \,\beta ^{i(e,l)-1} \end{aligned}$$

then we can re-write this as

$$\begin{aligned} c_{\mu }(W) \geqslant c_{\mu }(a) + \sum _{e\in \delta (W){\setminus }\{a\}\; : \; 1\leqslant i(e,l)\leqslant p-1}c_{\mu }(e) \geqslant c_{\mu }(a)\, \gamma _{l}(W) \end{aligned}$$

(6)

for every $\mu \in R_l(W)$.

The definition of $\alpha$ also implies that, for every $\mu \in R_l(W)$,

$$\begin{aligned} c_{\mu }(W)= & {} c_{\mu }(a) + \sum _{e\in \delta (W){\setminus }\{a\}\; : \; i(e,l) = 0}c_{\mu }(e) + \sum _{e\in \delta (W){\setminus }\{a\}\; : \; 1\leqslant i(e,l)\leqslant p-1}c_{\mu }(e) \nonumber \\\leqslant & {} c_{\mu }(a) + |E|\,\alpha \, c_{\mu }(a) + c_{\mu }(a)\,\beta \,\left( \gamma _{l}(W)-1\right) \nonumber \\= & {} c_{\mu }(a)\, \beta \,\gamma _{l}(W). \end{aligned}$$

(7)

Now fix a cut $X\in \mathcal {S}_a$ such that there exist $\mu \in R_l\cap M_a(X)$. Thus X is a minimum cut for the cost $c_{\mu }$. For every cut $W\in \mathcal {S}_a$ such that there exists $\nu \in R_l\cap M_a(W)$, we have

$$\begin{aligned} c_{\mu }(W)&\leqslant c_{\mu }(a)\, \beta \,\gamma _{l}(W)&\text {[by (7)]}\\&= \frac{c_{\mu }(a)}{c_{\nu }(a)}\, \beta \, c_{\nu }(a)\, \gamma _{l}(W)&\\&\leqslant \frac{c_{\mu }(a)}{c_{\nu }(a)}\, \beta \, c_{\nu }(W)&\text {[by (6)]}\\&\leqslant \frac{c_{\mu }(a)}{c_{\nu }(a)}\, \beta \, c_{\nu }(X)&(\text {by optimality of }W \hbox { for }\nu )\\&\leqslant \frac{c_{\mu }(a)}{c_{\nu }(a)}\, \beta ^2\, c_{\nu }(a)\,\gamma _{l}(X)&\text {[by (7)]}\\&= \beta ^2\, c_{\mu }(a)\, \gamma _{l}(X)&\\&\leqslant \beta ^2\, c_{\mu }(X)&\text {[by (6)]}. \end{aligned}$$

Therefore, every cut W such that $R_l\cap M_a(W) \not = \emptyset$ is a $\beta ^2$-approximate cut for the parametrized cost $c_{\mu }$.

If $\rho \leqslant 4$ then choose any $\beta$ such that $1 < \beta < \sqrt{9/8}$, so $\beta ^2 < 9/8$ and, by Corollary 3, the total number of such cuts W is $O(|V|^2)$. Otherwise (when $\rho \geqslant 5$), for every $\epsilon > 0$ we may choose $\beta = \beta (\epsilon )$ such that $1 < \beta (\epsilon ) < \sqrt{1+\epsilon /2}$, and the total number of such cuts W is $O(|V|^{2+\epsilon })$. Therefore it is $O_{\rho ,5}(|V|^2)$, and the proof is complete. $\square$

Recall that the combinatorial facet complexity of the parametrized minimum cut problem over the relevant set M of parameters is the maximum number of facets of the graph of $c^*(\mu )$ when $\mu \in M$; equivalently, of vertices of the dominant $\mathcal {D}$, and also of SND points. Thus Theorem 4 implies:

Corollary 5

Given a fixed integer $\rho \geqslant 2$, a rank-$\rho$ hypergraph $G=(V,E)$, and a fixed number k of edge cost functions $c^1,\ldots ,c^k$, the combinatorial facet complexity of the parametrized minimum cut problem over set M is $O_{\rho ,5}\Big (|E|^k \; |V|^2$ $\log ^{k-1}|V|\Big )$.

We now briefly comment on the multicriteria minimum cut problem. As explained earlier, we now assume that all edge costs are nonnegative, i.e., all $c^j \geqslant 0$, and that every cut cost $c^j(X) > 0 (j=1,\dots ,k, \emptyset \not =X\subset V$) (and therefore that G is connected). Under these assumptions, the relevant region in the parameter space is the nonnegative orthant, $M = \mathbb {R}^{k-1}_+$ and, by Theorem 4, the number of SND points is $O_{\rho ,5}(|E|^k \, |V|^2\, \log ^{k-1}|V|)$. In Theorem 8 in the next Section, we derive a strongly polynomial bound on the total number of (supported and unsupported) Pareto optimal points when $k = 2$. However, for $k\geqslant 3$ we leave the following:

Open Problem

In a graph or a bounded-rank hypergraph, with a fixed number $k \geqslant 3$ of nonnegative edge cost functions such that each cut cost is positive, is the number of UND points polynomially bounded?

4 Tighter bounds for minimum cuts with two nonnegative edge cost functions

When the bound on the number of SND cuts from Theorem 4 is specialized to $k=2$ edge cost functions, it becomes $O_{\rho ,5}(|E|^2\, |V|^2 \log |V|)$. This section sharpens this bound to $O_{\rho ,5}(|V|^3 \log |V|)$, an improvement by a factor $|E|^2/|V|$. For graphs (and rank-3 hypergraphs), this improvement is from $O(|E|^2|V|^2 \log |V|)$ to $O\left( |V|^3 \log |V|\right)$. We also derive a strongly polynomial bound on the total number of (supported and unsupported) nondominated points. Our proof strategy will rely on partitioning the criteria space, instead of the parameter space as in Sect. 3. For this reason, we now assume that both edge cost functions $c^1$ and $c^2$ are nonnegative. Note that partitioning the criteria space fails to work in the more general case discussed in Sect. 3 as the cost functions $c^j$ there may be negative. The results below also hold in the case where the edge parametric costs are $c_\mu (e)=\mu c^1(e)+(1-\mu )c^2(e)$ for $\mu \in [0,1]$.

For general optimization problems with several objectives, Papadimitriou and Yannakakis [34] use a partitioning of the criteria space into rectangular regions of exponentially increasing sizes and obtain an approximate Pareto set of weakly polynomially bounded size. Here we partition the criteria space according to value of criterion $c^1$, and we use two properties of global minimum cuts: First (in the proofs of Lemmas 6, 7), the polynomial bound on the number of approximate cuts from Corollary 3; and second (in the proof of Theorem 8), properties of edge contractions. We derive strongly polynomial bounds on the total number of all exact SND cuts.

The main argument used in the proof of Lemma 6 below is that every SND cut in a $c^1$-cost interval of relative width $\beta > 1$ is a $\beta$-approximation for the objective $c_{\mu }$ defined by a particular facet of the dominant polyhedron $\mathcal {D}$. Then, by choosing a small enough constant $\beta$, the number of SND cuts is shown to be $O_{\rho ,5}(|V|^2)$ per interval.

Lemma 6

Given a fixed integer $\rho \geqslant 2$, a rank-$\rho$ hypergraph $G=(V,E)$, two nonnegative edge cost functions $c^1$ and $c^2$ such that all cut costs are positive, and two reals $b > a > 0$, the total number of SND cuts X with $c^1$-cost satisfying $a \leqslant c^1(X) \leqslant b$ is $O_{\rho ,5}(|V|^2\,\log (b/a))$.

Proof

First, if $\rho \leqslant 4$ then choose any $\beta$ such that $1 < \beta < 9/8$; otherwise, i.e., when $\rho \geqslant 5$, for every $\epsilon > 0$ choose any $\beta$ such that $1 < \beta < 1+\epsilon /2$, so $2\beta < 2+\epsilon$. Next, choose $n = \lfloor \log (b/a)/\log \beta \rfloor + 1 = O\left( \log (b/a)\right)$ to ensure that $\beta ^{n-1} a \leqslant b < \beta ^n a$. Thus we can cover the “target” interval [a, b] with half-open intervals $I_j = \left[ \beta ^{j-1} a,\;\beta ^{j} a\right)$ for $j = 1,\dots ,n$, such that $b\in I_n$.

Let $\mathcal{X}_j$ denote the set of SND cuts X such that $c^1(X) \in I_j$. If $\mathcal{X}_j\not =\emptyset$ then let W be a cut in $\mathcal{X}_j$ with largest $c^2$-cost. Let $\mu > 0$ be a parameter value for which W maximizes the parametrized objective $c_{\mu } = \mu c^1 + c^2$. Since we only have two criteria, for every SND cut $X\in \mathcal{X}_j$ such that $\left( c^1(X),c^2(X)\right) \not = \left( c^1(W),c^2(W)\right)$, we have $\beta ^{j-1} a \leqslant c^1(W) < c^1(X) < \beta ^j a$ and $c^2(X) < c^2(W)$. Thus

$$\begin{aligned} c_{\mu }(X)< & {} \mu \, c^1(X) + c^2(W) < \mu \beta ^{j} a + c^2(W)\nonumber \\< & {} \beta \left( \mu \beta ^{j-1}a + c^2(W)\right) \leqslant \beta \left( \mu \,c^1(W) + c^2(W)\right) \nonumber \\= & {} \beta \, c_{\mu }(W). \end{aligned}$$

(8)

Therefore, every cut in $\mathcal{X}_j$ is a $\beta$-approximate cut for the parametrized objective $c_{\mu }$. By Corollary 3 and the above choice of $\beta$, the total number $|\mathcal{X}_j|$ of such cuts is $O_{\rho ,5}(|V|^2)$, and the total number of SND cuts X with $a \leqslant c^1(X) \leqslant b$ is at most $\sum _{j=1}^n |\mathcal{X}_j| =O_{\rho ,5}(|V|^2 \log (b/a))$, as claimed. $\square$

In a given width-$\beta$ interval I, let $c^1(I)$ be the $c^1$-cost of the SND cut in I with minimum $c^1$-cost, with $c^1(I)$ equalling the left endpoint of I if it contains no SND cut. The proof of the next lemma uses the fact that there are two types of Pareto optimal cuts in I: Those with $c^1$-cost greater than $c^1(I)$, which are again $\beta$-approximations; and the others (which must be UND cuts with $c^1$-cost less than $c^1(I)$), which we show are 2-approximations for a suitable $c_{\mu }$ objective.

Lemma 7

Given a fixed integer $\rho \geqslant 2$, a rank-$\rho$ hypergraph $G=(V,E)$, two nonnegative edge cost functions $c^1$ and $c^2$ such that all cut costs are positive, and two reals $b > a > 0$, the total number of Pareto optimal cuts X with $c^1$-cost satisfying $a \leqslant c^1(X) \leqslant b$ is $O_{\rho ,5}(|V|^4\log (b/a))$.

Proof

Let $\mathcal {N}[a,b]$ denote the set of all Pareto optimal cuts W with $c^1(W)\in [a , b]$, so we need to bound $|\mathcal {N}[a,b]|$. Our proof considers a number of cases and subcases. Cases 1 to 1.1.1 comprise the bulk of the proof; the other cases and subcases yield to simpler treatment.

• Case 1. There is at least one SND cut Z with $c^1(Z)\in [a, b]$: Define $a'' = \min \{c^1(X) : X\in \mathcal {S}\}$, so $a''\leqslant c^1(Z)$ and there is no Pareto optimal cut W with $c^1(W) < a''$. Similarly, define $b'' = \max \{c^1(X) : X\in \mathcal {S}\}$, so $b''\geqslant c^1(Z)$ and there is no Pareto optimal cut W with $c^1(W) > b''$. Now we restrict our attention to the interval $[a',b']$, where $a' = \max \{a, a''\}$ and $b' = \min \{b, b''\}$. Note that $[a',b']\subseteq [a,b]$ and $\mathcal {N}[a',b'] = \mathcal {N}[a,b]$.

  • Case 1.1. $a' < b'$: Let $x_1 < x_2 < \dots < x_N$ denote the distinct values of $c^1(X)$ for all SND cuts X with $a' < c^1(X) < b'$. It follows from Lemma 6 that $N = O\big (|V|^2 \log (b'/a')\big )$. Let $X_1, \dots , X_N$ be corresponding SND cuts, i.e., with $c^1(X_i) = x_i$ (Since different cuts may give rise to the same point in the criterion space there may be several choices for $X_i$, but this does not affect our arguments). Define $x_0 = \max \{c^1(X) : X\in \mathcal {S}\text { with }c^1(X) \leqslant a'\}$ with corresponding SND cut $X_0$, and $x_{N+1} = \min \{c^1(X) : X\in \mathcal {S}\text { with }c^1(X) \geqslant b'\}$ with corresponding SND cut $X_{N+1}$. For $i=0,1,\dots ,N$ define $\nu (i)$ as the value of $\mu$ such that $c_{\mu }(X_i) = c_{\mu }(X_{i+1}) = \min \{c_{\mu }(X) :X\in \mathcal {C}\}$. Thus, $\nu (0)>\nu (1)>\dots >\nu (N)$ are the successive breakpoints of the parametric curve $c^*(\mu )$ over the interval of $\mu$ values for which SND cuts X that minimize $c_{\mu }$ have $c^1(X)\in [a',b']$.

    • • For example, suppose that in Fig. 1a we have $c^1(C_2) < a < c^1(C_3)$ and $b > c^1(C_5)$. Then $a'=a$ and $b'=c^1(C_5)$; $N=2$; $x_0 = c^1(C_2), x_1 = c^1(C_3), x_2 = c^1(C_4)$ and $x_3 = c^1(C_5)$; $\nu (0) = b_2, \nu (1) = b_3$ and $\nu (2) = b_4$.

    Every Pareto optimal cut $W\in \mathcal {N}[a',b']$ has $c^1(W)\in [x_{i},\;x_{i+1}]$ for some $i\in \{0,1,\dots ,N\}$. Since W is Pareto optimal, its $c^2$ cost satisfies $c^2(W)\in [c^2(X_{i+1}),\, c^2(X_{i})]$. Since $X_{i}$ and $X_{i+1}$ are both minimum cuts for $\mu = \nu (i)$, we have $c_{\nu (i)}(X_i) = c_{\nu (i)}(X_{i+1})$ and so

    $$\begin{aligned} c_{\nu (i)}(W)\leqslant & {} \nu (i)\; c^1(X_{i+1}) + c^2(X_{i})\nonumber \\< & {} \nu (i)\; c^1(X_{i+1}) + c^2(X_{i+1}) + \nu (i)\; c^1(X_{i}) + c^2(X_{i})\nonumber \\= & {} 2\; c_{\nu (i)}(X_{i}). \end{aligned}$$

    (9)

    That is, W is a 2-approximate cut for the parametrized objective $c_{\nu (i)}$. As in Lemma 6, we cover the interval $[a',b']$ by half open intervals $\left[ \beta ^{j-1} a',\;\beta ^{j} a'\right)$, where $\beta >1$ is an appropriately chosen constant. Now fix one of the intervals $I'_j = \left[ \beta ^{j-1} a',\;\beta ^{j} a'\right)$ and let $\mathcal {N}(I'_j) := \{ W\in \mathcal {N}[a',b'] : c^1(W)\in I'_j\}$.

    • Case 1.1.1. There is an SND cut with $c^1$ cost in $I'_j$: Let $X_i$ be the SND cut with the least $c^1$ cost among all SND cuts with $c^1$ cost in $I'_j$. Every $W\in \mathcal {N}(I'_j)$ with $c^1(W) < c^1(X_i)$ satisfies $c^1(W)\in [x_{i-1}, x_i]$ and so by (9) is a 2-approximate cut for the parametrized objective $c_{\nu (i-1)}$; there are again $O_{\rho ,5}(|V|^4)$ such Pareto optimal cuts. Every other $W\in \mathcal {N}(I'_j)$ satisfies $c^1(X_i) \leqslant c^1(W) < \beta ^{j} a'$. Since W is non-dominated, we must have $c^2(W) < c^2(X_i)$. Using a similar argument as for (8), we have

      $$\begin{aligned} c_{\mu }(W)< & {} \mu \, c^1(W) + c^2(X_i) < \mu \beta ^{j} a + c^2(X_i)\\< & {} \beta \left( \mu \beta ^{j-1}a + c^2(X_i)\right) \leqslant \beta \left( \mu \,c^1(X_i) + c^2(X_i)\right) \\= & {} \beta \, c_{\mu }(X_i). \end{aligned}$$

      This implies that W is a $\beta$-approximate cut for the parametrized objective $c_{\nu (i)}$; thus, for $\beta$ chosen as in the proof of Lemma 6, there are $O_{\rho ,5}(|V|^2)$ such cuts, and so a total of $O_{\rho ,5}(|V|^4)$ Pareto optimal cuts in $I'_j$. Since $|\mathcal {N}(I'_j)| = O_{\rho ,5}(|V|^4)$ for each of the $O(\log (b'/a')$ intervals $I'_j$, we get $|\mathcal {N}[a,b]| = |\mathcal {N}[a',b']|$ $= O_{\rho ,5}(|V|^4 \log (b'/a')) = O(|V|^4 \log (b/a))$, as claimed.

    • Case 1.1.2. $I'_j$ does not contain the $c^1$ cost of any SND cut: Then every $W\in \mathcal {N}(I'_j)$ has $c^1(W) \in [x_i,\, x_{i+1}]$ for some i such that $x_i < \beta ^{j-1} a'$ and $\beta ^{j} a' \leqslant x_{i+1}$, hence is a 2-approximate cut for the parametrized objective $c_{\nu (i)}$. By Corollary 3 there are $O_{\rho ,5}(|V|^4)$ such cuts.

  • Case 1.2 $a'=b'$: Then $\mathcal {N}[a',b']$ is just the set of all SND cuts X with $c^1(X) = a'$, and the proof of Lemma 6 shows that $|\mathcal {N}[a',a']| =$ $O_{\rho ,5}(|V|^2 ) = O(|V|^4 \log (b/a))$.

• Case 2. There is no SND cut Z with $c^1(Z)\in [a, b]$: Then either (i) there is no SND cut Z at all with $c^1(Z) < a$, and thus $\mathcal {N}[a,b] = \emptyset$; or else (ii) let as above $X_0$ be an SND cut with largest cost $c^1(X_0) < a$ and $\nu (0)$ the corresponding parameter value, then (9) implies that every $W \in \mathcal {N}[a,b]$ is a 2-approximate cut for the parametrized objective $c_{\nu (0)}$, and thus $|\mathcal {N}[a,b]| =$ $O_{\rho ,5}(|V|^4) = O_{\rho ,5}(|V|^4 \log (b/a))$, as claimed.

The proof is complete. $\square$

The proof of the next theorem uses the following observation: every cut either has its $c^1$ cost in the interval $\left[ \frac{c^1(E)}{|E|}, c^1(E)\right]$ between the average and total $c^1$ edge costs, that has relative width $|E| = O(|V|^{\rho })$ (hence $\log |E| = O(\log |V|)$) and to which we apply the two preceding lemmas; or else the cut cannot contain any edge e with cost $c^1(e) \geqslant \frac{c^1(E)}{|E|}$, in which case we can contract all such costlier-than-average edges and recurse. Since there is at least one such edge to contract, the number of vertices decreases by at least one in each iteration and we are done after fewer than |V| rounds of edge contractions.

Theorem 8

Given a fixed integer $\rho \geqslant 2$, a rank-$\rho$ hypergraph $G=(V,E)$, and two nonnegative edge cost functions such that all cut costs are positive, the total number of SND cuts is $O_{\rho ,5}(|V|^3 \log |V|)$ and the total number of Pareto optimal cuts is $O_{\rho ,5}(|V|^5 \log |V|)$.

Proof

Our strategy is to repeatedly apply Lemma 6 to a sequence of hypergraphs obtained by contracting edges. As in [20, 25], by contracting an edge e in hypergraph $G = (V,E)$ with edge costs $c^j$ to get $G' = (V',E')$ we mean replacing all nodes in e by a single “contracted node” $v_e$ (i.e., $V' = (V{\setminus } e)\cup \{v_e\}$), and every edge $f\in E$ by an edge $f'$ of same costs, $c^j(f') = c^j(f)$, wherein all nodes in $e\cap f$, if any, are replaced by the single node $v_e$ (i.e., $f' = (f{\setminus } e)\cup \{v_e\}$ if $f\cap e\not =\emptyset$, and $f' = f$ otherwise). We then remove from E all edges f with $|f| =1$ (loops, which no cut in $G'$ can cross), and all nodes that do not belong to any edge in $E'$ (isolated nodes). Conversely, every cut in the contracted hypergraph corresponds, after expanding back the contracted node $v_e$, to a cut with the same cost in the original hypergraph. Note that this generalizes edge contraction in graphs, e.g., [31].

Suppose that X is a cut in G, and we contract e to get $G'$. If e is not in $\delta (X)$ (“X does not cross e”), then $X' := X {\setminus } \{v_e\}$ is a cut in $G'$ where $f'$ is in $\delta (X')$ if and only if f is in $\delta (X)$. Thus $c^j(X) = c^j(X')$ for $j = 1, 2$. On the other hand, if X is a cut in G with $e\in \delta (X)$ (“X crosses e”), then there is no cut in $G'$ corresponding to X.

We construct a sequence of m rank-$\rho$ hypergraphs, $i=1,\dots ,m$. Hypergraph i is $G_i = (V_i, E_i)$ with edge costs $c_i =(c^1_i,c^2_i)$, such that $(G_0, c_0) = (G,(c^1,c^2))$. Hypergraph $(G_i,c_i)$ is derived from $(G_{i-1},c_{i-1})$ by contracting all edges in $e\in E_{i-1}$ with cost $c^1_{i-1}(e) \geqslant a_{i-1} := \frac{c^1_{i-1}(E_{i-1})}{|E_{i-1}|}$, so long as $|V_{i-1}| > \rho$. Since there is at least one edge $e\in E_{i-1}$ with $c^1$-cost no less than the average $a_{i-1}$, there will be at least one edge to contract. Thus $|V_i| < |V_{i-1}|$ and so $m \leqslant |V| - \rho$.

We associate with each hypergraph $G_i$ in the sequence an interval $[a_i, b_i]$ where, as defined above, $a_i := \frac{c^1_i(E_i)}{|E_i|}$ is the average edge $c^1_i$-cost in $G_i$, and $b_i = c^1_i(E_i) = |E_i| a_i$ is the total $c^1_i$-cost. Since $c^1_i \geqslant 0$, the $c^1_i$-cost of every cut X in $G_i$ satisfies $c^1_i(X)\leqslant c^1_i(E_i) = b_i$. Every cut X in $G_i$ either has cost $c^1_i(X)\geqslant a_i$, and therefore $c^1_i(X)\in [a_i, b_i]$, or else it cannot cross any edge e with cost $c^1_i(e) \geqslant a_i$. In the latter case, if $i < m$ then X does not cross any edge which is contracted when defining $G_{i+1}$. Thus there is a cut $X'$ in $G_{i+1}$ corresponding to X, and its cost $c^1_i(\delta _i(X)) = c^1_{i+1}(\delta _{i+1}(X')) \leqslant b_{i+1}$.

Let $s_i$ (resp. $n_i$) denote the number of SND (resp. nondominated) cuts in $G_i$ with cost $c^1_i(X)$ in $[a_i,b_i]$. It follows that $s_i$ (resp. $n_i$) is also the number of SND (resp. nondominated) cuts in the original hypergraph G with cost $c^1(X)\in [a_i,b_i]$. Then the total number of SND cuts in G is at most $\sum _{i=1}^m s_i$, and it suffices to prove that each $s_i = O_{\rho ,5}(|V|^2 \log |V|)$. Similarly, it suffices to prove that each $n_i = O_{\rho ,5}(|V|^4 \log |V|)$. These are certainly true for $i=m$ since $|V_m| \leqslant \rho$ and thus $s_m \leqslant n_m < 2^{\rho } = O(1)$. For $i<m, s_i = O_{\rho ,5}(|V_i|^2 \log |E_i|)$ by Lemma 6, and $n_i = O_{\rho ,5}(|V_i|^4 \log |E_i|)$ by Lemma 7. Since $|E_i| = O(|V_i|^{\rho })$ and $\rho$ is fixed, $\log |E_i| = O\left( \log |V_i|\right) = O\left( \log |V|\right)$. $\square$

Since distinct facets of the graph of $c^*$ are associated with distinct SND cuts, we have:

Corollary 9

Under the assumptions of Theorem 8, the combinatorial facet complexity of the bi-objective parametrized minimum cut problem is $O_{\rho ,5}(|V|^3~\log |V|\big )$.

Notice that in the case of graphs (where $\rho = 2$) the bounds in Theorem 8 specialize to there being $O(|V|^3 \log |V|)$ SND cuts and $O(|V|^5 \log |V|)$ UND cuts. The conference version of this paper [1] claimed a slightly better bound of $O(|V|^3)$ SND cuts, but there was an error in its analysis of its Algorithm 2 in the proof of its Claim 3. On the other hand, the present $O(|V|^5 \log |V|)$ bound on the number of UND cuts is better than the $O(|V|^7)$ bound of [1].

5 Algorithms

In this section we show how to combine the preceding results with several existing algorithms, and derive strongly polynomial time deterministic algorithms for computing the optimum cost function $c^*$; the sets of supported and, for $k=2$, unsupported Pareto optimal points; and the sets of all corresponding minimum cuts. For this we use three types of existing algorithms:

• (1) Algorithms for solving the ordinary (single-objective) minimum cut problems, i.e., to determine the value $c^*(\mu )$ and a corresponding minimum cut for any given $\mu \in M$, see the Introduction. Let $MC = MC(|V|,|E|)$ denote the running time of such an algorithm for finding a minimum cut in a hypergraph with |V| vertices and |E| edges. Recall that $MC = O(|E|\cdot |V| + |V|^2 \log |V|)$ ([30, 42] for graphs; [20, 25, 37] for hypergraphs).

• (2) Algorithms for construction of the optimum cost function $c^*$ for $\mu$ in a convex parameter region, see [11, Section 3.2] or [10, Section 30.4.2]. In particular, Theorem 30.2 in [10] implies that if the upper envelope of the piecewise linear concave function $c^*$ of d parameters has $\varPhi$ facets and $\varPsi$ vertices then, it can be obtained by evaluating $c^*(\mu )$ at $O(\varPhi + d \; \varPsi )$ points $\mu$, and then constructing the full upper convex hull derived from the resulting hyperplanes. The latter task is dual, and computationally equivalent, to the well-studied question of constructing the convex hull of a given set of points, e.g., [36, Section 3.4], [26, Section 7.3]. Chan’s algorithm [4], the fastest convex hull algorithm known today, achieves this in $O\Big (\varPhi \log \varPhi +(\varPsi \varPhi )^{1+1/(\lfloor d/2\rfloor +1)}\log ^{O(1)} \varPhi \Big )$ time. For $k = 2$ (hence $d=1$), the whole graph can be constructed in $O\left( \varPhi \;T \right)$ total time [9], where T is the time needed for an evaluation of $c^*(\mu )$ (i.e., MC for our problem).

• (3) Algorithms for producing, for a single objective, all minimum cuts and all 2-approximate cuts. We collect and summarize a number of methods and results in the next lemma and its proof:

Lemma 10

Let AMC1 and AMC2 denote the total time to produce all minimum cuts and all 2-approximate cuts, respectively, in rank-$\rho$ hypergraphs $G=(V,E)$ with nonnegative edge costs c and positive minimum cut value.

• (i) For $\rho = 2$ (i.e., for graphs), $AMC 1 = O(|E|^2 |V| + |V|^2 |E|)$, and $AMC 2 = O(|E|\;|V|^4)$.

• (ii) For $\rho = 3, AMC 1 = O(|V|^5)$ and $AMC 2 = O(|V|^6)$.

• (iii) For $\rho \geqslant 4$, $AMC 1 = \min \left\{ O(|V|^{2 B(\rho )+2}),\; \widetilde{O}(|V|^3 |E|^2)\right\}$ and $AMC 2 = \min \left\{ O(|V|^{4 B(\rho )+2}),\; \widetilde{O}(|V|^5 |E|^2)\right\}$.

Proof

(i) For the case where G is a graph, Dinitz et al. [6] present a “cactus representation” of all minimum cuts, which is a of tree of cycles on node set V such that cut X is minimum if and only if it cuts exactly two arcs in one cycle. Nagamochi et al. [32] use a cactus representation to show that $AMC 1 = O(|E|^2 |V| + |V|^2 |E|)$, while it follows from [31] that $AMC 2 = O(|E|\;|V|^4)$ (see also [18] and [35, Chapter 2] for randomized graph cut enumeration algorithms).

(ii) If G is a rank-3 hypergraph then, as shown in the proof of Proposition 2, the cost of a cut X is the same in graph G with edge cost function c as in the complete graph K(V) with edge cost function $\tilde{c}$ defined in the proof of that proposition. Therefore one may apply the method of [32] to $(K(V),\tilde{c})$ and produce in $AMC 1 = O(|E_{K(V)}|^2 |V| + |V|^2 |E_{K(V)}|) = O(|V|^5)$ time all minimum cuts for (G, c), and in $AMC 2 = O(|E_{K(V)}| |V|^4 ) = O(|V|^6)$ time all 2-approximate cuts for (G, c).

(iii) If G is a rank-$\rho$ hypergraph with $\rho \geqslant 4$, then we choose the faster of the following two methods. First, we may apply the approximation to graph cuts in K(V) from the proof of Proposition 2. By (2) with $\alpha =1$ and $\alpha =2$, it suffices to produce all $\alpha B(\rho )$-approximate cuts in $(K(V),\tilde{c})$, and then only retain the $\alpha$-approximate cuts for (G, c). Since $\rho$ is fixed, it takes $O( |E|+|V|^2 )$ time to compute the weights of all clique edges (storing them in a $|V|\times |V|$ matrix). It then follows from [31] that $AMC 1 = O( |E|+|V^2| + |E_{K(V)}|\; |V|^{2 B(\rho )}) = O(|E| + |V|^{2 B(\rho )+2})$ and $AMC 2 = O( |E|+|V^2| + |E_{K(V)}|\; |V|^{4 B(\rho )}) = O(|E| + |V|^{4 B(\rho )+2})$.

Alternately, we may apply the Lawler-Murty (LM) general approach for ranking solutions to combinatorial optimization problems (see, e.g., [12, 22] for treatments generalizing [29], and [13, 43] or [31, Section 4.1] for its application to ranking graph cuts). The LM method produces a sequence $(X^1, X^2, \dots )$ of cuts, where we require (w.l.o.g.) that node 1 be in each $X^i$, in nondecreasing cost order, i.e., $c(X^1) \leqslant c(X^2) \leqslant \dots$, and such that if $c(X) < c(X^i)$ then X must be one of $X^1,\dots ,X^{i-1}$. Thus $X^1$ is a minimum cut; $X^2$ is a “second best cut”, i.e., a least cost cut (with $1\in X^2$) distinct from $X^1$; $X^3$ is a “third best cut”; and so on. The LM method requires solving O(|V|) modified minimum cut problems per cut $X^i$ produced. It is based on the repeated application of a simple idea: $X^2$ contains at least one vertex $v\not \in X^1$ or its complement $V{\setminus } X^2$ contains at least one vertex $v\in X^1{\setminus }\{1\}$. Then $X^2$ is a best cut among $|V|-1$ candidate sets $Y^1_v$, one for each $v\in V{\setminus }\{1\}$, where $Y^1_v$ is a least cost cut with $1\in Y^1_v$ and either (a) $v\in Y^1_v$ if $v\not \in X^1$, or (b) $v\not \in Y^1_v$ if $v\in X^1$. Case (a), $1\in Y^1_v$ and $v\in Y^1_v$, is easy to enforce, for example by merging vertices 1 and v; but case (b), $1\in Y^1_v$ and $v\not \in Y^1_v$, gives rise to a hypergraph s–t-cut problem, viz, to find a minimum cost cut $Y^1_v$ that separates terminals $s=1$ and $t=v$. Lawler [23] (see also [44]) shows that a minimum s–t-cut in a hypergraph can be computed by finding a minimum cut in an auxiliary digraph with $|V| + 2 |E|$ vertices and $2d_G + |E|$ edges, where $d_G = \sum _{e\in E}|e|$ is the sum of the cardinalities of all edges in hypergraph G. Since $d_G = O(\rho |E|)$, a minimum s–t-cut in a hypergraph can be found in $\widetilde{O}(|E|^2)$ time. By Theorem 1, using the LM method to produce the $O(|V|^{2\alpha })$ $\alpha$-approximate cuts for $\alpha =1$ and 2, respectively, leads to $AMC 1 = \widetilde{O}(|V|^3 |E|^2)$ and $AMC 2 = \widetilde{O}(|V|^5 |E|^2)$, running times that are independent of $\rho$. $\square$

Combining these algorithms and our earlier results we obtain:

Theorem 11

Given a hypergraph $G=(V,E)$, and a fixed number k of nonnegative edge cost functions $c^1,\ldots ,c^k$ such that $c^j(X)$ is positive for all cuts X in G:

• (i) If $k=2$, there exists an algorithm that constructs the optimum cost function in $O_{\rho ,5}(|V|^3 \log |V|\; MC)$ time, and all cuts defining SND and Pareto optimal points in $O_{\rho ,5}(|V|^3\log |V|\; AMC 1)$ and $O_{\rho ,5}(|V|^3$ $\log |V|\; AMC 2)$ time, respectively.

• (ii) If $k\geqslant 3$, the time needed to construct the optimum cost function and all cuts defining SND points is

  $$\begin{aligned} O_{\rho ,5}\left( |E|^{k\left\lfloor \frac{k-1}{2} \right\rfloor }\ \ |V|^{2 \left\lfloor \frac{k-1}{2} \right\rfloor }\ \ \log ^{(k-1)\left\lfloor \frac{k-1}{2} \right\rfloor + O(1)}|V|\right) \end{aligned}$$

  (10)

Proof

(i) Follows from the use of the Eisner and Severance method [9] with $\varPhi = O_{\rho ,5}(|V|^3 \log |V|)$ from Theorem 8, and from the fact, established in the proof of Lemma 7, that every Pareto optimal point is defined by a 2-approximate cut for a facet-inducing parametrized objective.

(ii) Follows from Theorem 30.2 in [10] using $d = k-1, \varPhi = O_{\rho ,5}(\widehat{\varPhi \,})$ where $\widehat{\varPhi } = |E|^k |V|^2 \log ^{k-1}|V|$ by Theorem 4, $\varPsi = O(\widehat{\varPsi \,})$ where $\widehat{\varPsi } = \widehat{\varPhi }^{\left\lfloor \frac{k-1}{2} \right\rfloor }$ by McMullen’s Upper Bound Theorem (e.g., [26, Section 7.3]; see also [40]). Indeed, using Chan’s convex hull algorithm [4], the time needed for constructing the lower convex hull from the $\varPhi$ hyperplanes is bounded by (10). Since the time MC for each “probe” (evaluation of $c^*(\mu )$ for a given $\mu \in M$) satisfies $MC = O_{\rho ,5}(\widehat{\varPhi }\,)$ when $k\geqslant 3$, the lower hull construction time (10) dominates the total time for constructing the optimum cost function. Furthermore, for each of the $\varPhi$ SND points one may produce in AMC1 time all corresponding cuts. Since $AMC 1 = O(\widehat{\varPhi }\,)$ when $k\geqslant 3$, the lower hull construction time (10) again dominates the total computation time. $\square$

Remark 12

The results in Lemma 10 and Theorem 11 are based on deterministic algorithms. The design of randomized algorithms and the study of the tradeoffs between their running time and success probability are beyond the scope of this paper and are left to future work.

6 Conclusion

We have extended Karger’s bounds [16, 17] on the number of approximate global minimum cuts from graphs to hypergraphs. This then allowed us to derive strongly polynomial bounds on the number of Supported (and for the case of two objectives, Unsupported) Pareto optimal cuts w.r.t. multiple objectives (or multiple parameters) in both hypergraphs and graphs. These bounds, when combined with existing algorithms, lead to strongly polynomial algorithms for computing all such cuts.

In addition to the open problem at the end of Sect. 3 (namely, for a fixed number $k\geqslant 3$ of criteria and fixed rank $\rho \geqslant 2$, is there a strongly polynomial bound on the total number of optimal points?) another open problem is to find a non-trivial lower bound on the complexity of parametric global minimum cut. It is easy to produce classes of instances with $\varTheta (|V|)$ different facets in the graph of $c^*$, but so far we do not have any classes of instances with superlinear complexity. It would be interesting to close this gap; or even for graphs and just two criteria, to reduce the gap between the present $\Omega (|V|)$ and $O(|V|^3 \log |V|)$ bounds.

Appendix

In this Appendix we present a proof of Theorem 1 for arbitrary $\alpha \geqslant 1$. We adapt and extend Kogan and Krauthgamer’s [21] approach and some of their notations.

We start with a simple upper bound on the minimum cut cost in a rank-$\rho$ hypergraph. For every $i=2,\dots ,\rho$ let $W_i = \sum \{c(e) : e\in E\text { and }|e|=i\}$ denote the total cost of all size-i edges, and $c(E) = \sum _{i=2}^{\rho } W_i = \sum _{e\in E} c(e)$ the total weight of all edges.

Lemma 13

([21]) The minimum cost of a cut in a rank-$\rho$ hypergraph $G = (V,E)$ with positive edge costs c, is at most $\frac{1}{|V|} \sum _{i=2}^{\rho } i\,W_i \leqslant \frac{\rho }{|V|}\, c(E)$.

Proof

An edge $e\in E$ crosses a singleton cut $C = (\{v\},V{\setminus }\{v\})$ (i.e., $e\in \delta (\{v\})$) if and only if $v\in e$. Thus an edge e crosses exactly |e| singleton cuts. If we choose a node $\mathbf{v}$ uniformly at random in V and consider the resulting (random) singleton cut $\{\mathbf{v}\}$, then

$$\begin{aligned} \min _{X\in \mathcal {C}} c(\delta (X))\le & {} \min _{v\in V} c(\delta (\{v\})) \ \le \ {\mathbb E}\left[ c(\{\mathbf{v}\})\right] \ =\ \sum _{v\in V}\frac{1}{|V|}\sum _{e \,:\, v\in e\in E} c(e)\\= & {} \frac{1}{|V|} \sum _{e\in E} |e|\, c(e) \ =\ \frac{1}{|V|}\sum _{i=2}^{\rho } i\,W_i \ \leqslant \ \frac{\rho }{|V|} \sum _{i=2}^{\rho } W_i \ =\ \frac{\rho }{|V|}\, c(E) \end{aligned}$$

and the Lemma follows. $\square$

Kogan and Krauthgamer use a probabilistic argument which extends to hypergraphs by an approach introduced by Karger [16, 19] for graph cuts. The first step is to define a generalization to hypergraphs of Karger’s randomized edge contraction algorithm. Similar generalizations for finding and counting minimum hypergraph cuts were outlined by Chekuri and Korula [5] and by Queyranne and Guiñez [38]. The algorithm below, adapted from [21], is similar to these, except that (as in [19]), it stops early so as to ensure a sufficiently high probability of generating any fixed $\alpha$-approximate cut.

Theorem 1 will be an easy consequence of the following result, which is adapted from and extends (with minor changes) Theorem 3.4 in [21]. Since we allow $2\alpha$ to be noninteger, we use, as in Karger and Stein [19, proof of Corollary 8.3], generalized binomial coefficients

$$\begin{aligned} \left( {\begin{array}{c}x\\ y\end{array}}\right) = \frac{\varGamma (x+1)}{\varGamma (y+1)\varGamma (x-y+1)} \end{aligned}$$

where, for simplicity, we assume $x > -1$ and $-1 < y < x+1$, and where the Gamma function is the Euler integral $\varGamma (x) = \int _0^{+\infty } t^{x-1} e^{-t} dt$. Since $\varGamma (t+1) = t\,\varGamma (t)$ for all $t>0$, these (generalized) binomial coefficients satisfy the recurrence

$$\begin{aligned} \left( {\begin{array}{c}x\\ y\end{array}}\right) = \frac{x}{x-y}\left( {\begin{array}{c}x-1\\ y\end{array}}\right) = \left( 1+\frac{y}{x-y}\right) \left( {\begin{array}{c}x-1\\ y\end{array}}\right) \end{aligned}$$

(11)

when $x > 0$ and $-1 < y < x$.

Theorem 14

For every real $\alpha \geqslant 1$ and every integer $\rho \geqslant 2$ there exists a constant $K(\alpha ,\rho ) > 0$ such that, for every rank-$\rho$ hypergraph $G = (V,E)$ with $|V| > \alpha r$ vertices, nonnegative edge costs c and positive minimum cut cost, and for every particular $\alpha$-approximate cut X in G, the probability that Algorithm 1 outputs X or $V{\setminus } X$ is at least $K(\alpha ,\rho ) \left( {\begin{array}{c}|V|-\alpha (\rho -2)\\ 2\alpha \end{array}}\right) ^{-1}$.

We prove Theorem 14 below, after first establishing another lemma. In the rest of this Appendix we assume that $\alpha \geqslant 1$ is a fixed real number, and $\rho \geqslant 2$ a fixed integer.

For every integer $t\geqslant 2$ let ${\mathcal G}_t$ denote the set of all edge-weighted rank-$\rho$ hypergraphs (G, c) with t vertices, nonnegative edge costs and positive minimum cut cost. Let ${\mathcal G} = \bigcup _{t\geqslant 2} {\mathcal G}_t$ denote the set of all such edge-weighted hypergraphs with any number of vertices. For $(G,c)\in {\mathcal G}_t$ and cut X in G let $p_t(X \,|\, G,c)$ denote the probability that Algorithm 1, when applied to (G, c), outputs cut X or $V{\setminus } X$. Let

$$\begin{aligned} p_t = \inf \left\{ p_t(X \,|\, G,c) \,:\, (G,c)\in {\mathcal G}_t \text { and }X\text { is an } \alpha \text {-approximate cut in }(G,c)\right\} \end{aligned}$$

Lemma 15

If $t\geqslant \left\lfloor \alpha \rho \right\rfloor +1$ and we have a positive lower bound $\widetilde{p}_u \leqslant p_u$ for every $u = t-\rho +1,\dots ,t-1$, then $p_t \geqslant (t-\alpha \rho )\min _{i=2,\dots ,\rho } \widetilde{p}_{t-i+1}/(t - \alpha (\rho -i))$.

Proof

Assume that, as stated, $t\geqslant \left\lfloor \alpha \rho \right\rfloor +1$ and $0 < \widetilde{p}_u \leqslant p_u$ for every $u = t-\rho +1,\dots ,t-1$. For any $(G,c)\in {\mathcal G}_t$ let $\varepsilon$ denote the (random) edge selected for contraction in step 3 of Algorithm 1. Let (G, c) / e denote the node-weighted hypergraph resulting from the contraction of an edge $e\in E$. Thus $(G,c)/e \in {\mathcal G}_{t-|e|+1}$. Let X be any $\alpha$-approximate cut in (G, c) and let $A(X,\, (G,c))$ represent the event that Algorithm 1, when applied to (G, c), outputs cut X or $V{\setminus } X$. Cut X will survive the current contraction if $\varepsilon \not \in \delta (X)$, otherwise it certainly cannot be output by Algorithm 1. Letting X / e denote the node subset X after contraction of edge $e\not \in \delta (X)$, conditioning over the size |e| of the contracted edge, and using the assumed lower bounds, we have

$$\begin{aligned} {{\mathrm{Prob}}}\left\{ A(X ,\, (G,c)) \right\}= & {} \sum _{e\in E{\setminus }\delta (X)} {{\mathrm{Prob}}}\left\{ A(X/e ,\, (G,c))/e\right\} {{\mathrm{Prob}}}\{\varepsilon = e\}\\= & {} \sum _{i=2}^\rho \ \sum _{e\in E{\setminus }\delta (X)\,:\,|e|=i} {{\mathrm{Prob}}}\left\{ A(X/e ,\, (G,c))/e\right\} {{\mathrm{Prob}}}\{\varepsilon = e\}\\\geqslant & {} \sum _{i=2}^\rho \widetilde{p}_{t-i+1}{{\mathrm{Prob}}}\{\varepsilon \not \in \delta (X)\text { and }|\varepsilon |=i\} \!=\! \sum _{i=2}^\rho \widetilde{p}_{t-i+1}(x_i \!-\! y_i). \end{aligned}$$

where $x_i = {{\mathrm{Prob}}}\{|\varepsilon |=i\}$ and $y_i = {{\mathrm{Prob}}}\{\varepsilon \in \delta (X)\text { and }|\varepsilon |=i\}$. Using the notations in Lemma 13 above, we have $x_i = W_i / c(E)$. Let $\widehat{w}(G,c) = \min _{X\in \mathcal {C}} c(\delta (X))$ denote the minimum cost of a cut in (G, c). By Lemma 13 we have (as in [21]):

$$\begin{aligned} \sum _{i=2}^\rho y_i= & {} {{\mathrm{Prob}}}\{\varepsilon \in \delta (X)\} = \frac{c(\delta (X))}{c(E)}\nonumber \\\leqslant & {} \frac{\alpha \,\widehat{w}(G,c)}{c(E)} \leqslant \frac{\alpha }{t} \sum _{i=2}^{\rho } \frac{i\,W_i}{c(E)} = \frac{\alpha }{t} \sum _{i=2}^{\rho } i\,x_i \end{aligned}$$

(12)

Let $\eta = t\,\min _{i=2,\dots ,\rho } \widetilde{p}_{t-i+1}/(t - \alpha (\rho -i))$, so $\eta > 0$ and for every $i=2,\dots ,\rho$

$$\begin{aligned} \widetilde{p}_{t-i+1} \geqslant \frac{t-\alpha (\rho -i)}{t}\eta \end{aligned}$$

Therefore,⁵

$$\begin{aligned} {{\mathrm{Prob}}}\left\{ A(X ,\, (G,c)) \right\}\geqslant & {} \sum _{i=2}^\rho \frac{t-\alpha (\rho -i)}{t}\eta (x_i-y_i) \end{aligned}$$

(13)

$$\begin{aligned}= & {} \frac{t-\alpha \rho }{t}\eta \sum _{i=2}^\rho (x_i-y_i) + \eta \sum _{i=2}^\rho \frac{\alpha i}{t}(x_i-y_i)\nonumber \\\geqslant & {} \frac{t-\alpha \rho }{t}\eta \sum _{i=2}^\rho x_i + \eta \sum _{i=2}^\rho \left( \frac{\alpha i}{t}x_i-y_i\right) \end{aligned}$$

(14)

$$\begin{aligned}\geqslant & {} \frac{t-\alpha \rho }{t}\eta = (t - \alpha \rho )\,\min _{i=2,\dots ,\rho } \frac{\widetilde{p}_{t-i+1}}{t - \alpha (\rho -i)} \end{aligned}$$

(15)

where in (14) we use $y\geqslant 0$ and, since $i \leqslant r, \alpha i \leqslant \alpha r \leqslant t$; and in (15) we use $\sum _{i=2}^r x_i = 1$, (12), and then the definition of $\eta$.

Since (13)–(15) holds for every $(G,c)\in {\mathcal G}_t$ and every $\alpha$-approximate cut X in (G, c), the proof of Lemma 15 is complete. $\square$

Proof of Theorem 14

For $u = |V| = \left\lfloor \alpha \rho \right\rfloor - \rho + 2,\dots ,\left\lfloor \alpha \rho \right\rfloor$, Algorithm 1 directly chooses in step 6, uniformly at random, one of the $2^u-2$ cuts in $\mathcal {C}$, so the probability it outputs cut X or $V{\setminus } X$ is exactly $\widetilde{p}_u = (2^{u-1}-1)^{-1}$.

For $t = \left\lfloor \alpha \rho \right\rfloor + 1,\dots ,\left\lfloor \alpha \rho \right\rfloor + \rho -1$ recursively define

$$\begin{aligned} \widetilde{p}_t = (t-\alpha \rho )\min _{i=2,\dots ,\rho } \widetilde{p}_{t-i+1}/(t - \alpha (\rho -i)). \end{aligned}$$

By Lemma 15 we have $p_t \geqslant \widetilde{p}_t$ for all such t. Define

$$\begin{aligned} K(\alpha ,\rho ) = \min _{t = \left\lfloor \alpha \rho \right\rfloor + 1,\dots ,\left\lfloor \alpha \rho \right\rfloor + \rho -1} \widetilde{p}_t \left( {\begin{array}{c}t-\alpha (\rho -2)\\ 2\alpha \end{array}}\right) \end{aligned}$$

and $\widehat{p}_t = K(\alpha ,\rho ) \left( {\begin{array}{c}t-\alpha (\rho -2)\\ 2\alpha \end{array}}\right) ^{-1}$, so $p_t \geqslant \widehat{p}_t > 0$ for all such t.

For $t\geqslant \left\lfloor \alpha \rho \right\rfloor + \rho$, applying Lemma 15 using $\widehat{p}_u$ in lieu of $\widetilde{p}_u$ we get

$$\begin{aligned} p_t \geqslant (t-\alpha \rho )\min _{i=2,\dots ,\rho } \frac{K(\alpha ,\rho ) \left( {\begin{array}{c}t-i+1-\alpha (\rho - 2)\\ 2\alpha \end{array}}\right) ^{-1}}{t - \alpha (\rho -i)} \end{aligned}$$

(16)

By induction on $i=2,\dots ,\rho$, equation (11) implies (as in Claim 3.6 in [21]):

$$\begin{aligned} \frac{\left( {\begin{array}{c}t-\alpha (\rho - 2)\\ 2\alpha \end{array}}\right) }{ \left( {\begin{array}{c}t-i+1-\alpha (\rho - 2)\\ 2\alpha \end{array}}\right) }= & {} \prod _{j=2}^{i} \left( 1 +\frac{2\alpha }{t-j+2-\alpha \rho }\right) \\\geqslant & {} \left( 1 +\frac{2\alpha }{t-\alpha \rho }\right) ^{i-1} \geqslant \ 1 +(i-1)\frac{2\alpha }{t-\alpha \rho }\\\geqslant & {} \frac{t - \alpha (\rho -i)}{t-\alpha \rho }\;. \end{aligned}$$

Then (16) implies

$$\begin{aligned} p_t \geqslant K(\alpha ,\rho ) \left( {\begin{array}{c}t-\alpha (\rho - 2)\\ 2\alpha \end{array}}\right) ^{-1}. \end{aligned}$$

completing the proof of Theorem 14. $\square$

Proof of Theorem 1

Theorem 14 implies that the number of $\alpha$-approximate cuts in any $(G,c) \in \mathcal {G}$, where $G=(V,E)$ is a rank-$\rho$ hypergraph, is at most $K(\alpha ,\rho )^{-1} \left( {\begin{array}{c}|V|-\alpha (\rho - 2)\\ 2\alpha \end{array}}\right)$, which is $O\left( |V|^{2\alpha }\right)$ when $\alpha \geqslant 1$ is a fixed real number and $\rho \geqslant 2$ is fixed. This proves Theorem 1. $\square$