# Bounds on number of cuts

Consider we have an undirected graph $G=(V,E)$ of $n$
vertices, and there are *positive* cost $c:E→R_{+}$ on the edges. We define $c(F)=∑_{e∈F}c(e)$, to be the cost
(value) of $F⊂E$.

Let $P$ be a partition of
$V$ where each partition class is
non-empty. We define $E(P)$ to
be the set of edges with end points in two different partition classes.
A set of edges $F$ is called a *$k$-cut*, if $F=E(P)$ for some $P$ such that $∣P∣≥k$.

We stress that by this definition, a $k$-cut is always a $j$-cut for $j≤k$. A *cut* is defined as a $2$-cut. A min-$k$-cut is a $k$-cut of minimum value (cost). We let $λ_{k}$ to denote the value of the
min-$k$-cut. A $α$-approximate $k$-cut is a cut of value at most $αλ_{k}$.

It is well known that the number of min-cuts in a graph is $(2n )$. [1]

Unless specifically stated, we assume $k$ is a fixed integer at least $2$, and $α$ is a fixed value at least $1$.

We can express the state alternatively.

The number of cuts $F$ such that $c(F)≤λ_{2}$ is $O(n_{2})$.

# 1 Bounds related to approximate min-cuts

What happens when we want to know about the number of cuts with value at most $αλ_{2}$?

By simply analyzing Karger’s algorithm, one can obtain the following.

The number of cuts $F$ such that $c(F)≤αλ_{2}$ is $O(n_{2α})$.

With more careful analysis using tree packing, Karger added a floor function to the exponent [2].

The number of cuts $F$ such that $c(F)≤αλ_{2}$ is $O(n_{⌊2α⌋})$.

Indeed, we do have a lower bound of $(⌊2α⌋n )$. Just consider an unweighted cycle, where min-cut has value $2$. We can pick any $⌊2α⌋$ edges, which forms a cut of value at most $α$ times the min-cut.

Note that we require $α$ to a
fixed value. This is because there is a dependency on $α$ hidden inside the big $O$. Our lower bound is absolute and does not
depending on $α$ being fixed. It
would be interesting to obtain a matching upper bound for arbitrary
$α$. Hence we can consider the
problem with **strict inequality**.

The number of cuts $F$ such that $c(F)<αλ_{2}$ is $O(n_{⌈2α⌉−1})$.

Henzinger and Williamson showed the conjecture true for all $α≤23 $ [3].

# 2 Bounds related to $α$-approximate min-$k$-cut

There are multiple ways to obtain the following theorem. For example, directly generalize Karger’s argument for cut counting.

The number of cuts $F$ such that $c(F)≤λ_{k}$ is $O(n_{2(k−1)})$.

One can show a lower bounds of the form $(kn )$. Again, a cycle would be an example of such lower bound. The min-$k$-cut has value $k$, and can be obtained by picking any $k$ edges. Recently, the upper bound has been closed (up to constant factor if $k$ is fixed) [4].

The number of cuts $F$ such that $c(F)≤λ_{k}$ is $n_{k}k_{O(k_{2})}$. Namely $O(n_{k})$ for fixed $k$.

In fact, they proved it by prorving the stronger theorem on $α$-approximate min-$k$-cuts.

The number of cuts $F$ such that $c(F)≤αλ_{k}$ is $n_{αk}k_{O(αk_{2})}$. Namely $O(n_{αk})$ for fixed $k$.

Unlike $α$-approximate min-cuts, there is no floor function in the exponent. Hence a natural conjecture would be.

The number of cuts $F$ such that $c(F)≤αλ_{k}$ is $O(n_{⌊αk⌋})$.

# 3 Bounds on (approximate) parametric cuts

Consider we have $d$ weight functions $c_{1},…,c_{d}:E→R_{≥0}$. Define $c_{μ}(e)=∑_{i=1}μ_{i}c_{i}(e)$ for $μ∈R_{≥0}$. We are interested in knowing about cuts $F$ such that $c_{μ}(F)$ is bounded by $αλ_{μ,k}$, where $λ_{μ,k}$ is the min-$k$-cut value when the cost function is $c_{μ}$.

Karger showed the following [5].

The number of cuts $F$ such that $c_{μ}(F)≤λ_{μ,2}$ for some $μ∈R_{≥0}$ is $O(n_{d+1})$.

A even more general theorem follows, allowing $α$-approximate $k$-cuts.

The number of cuts $F$ such that $c_{μ}(F)≤αλ_{μ,k}$ for some $μ∈R_{≥0}$ is $O(n_{2α(k−1)+d−1})$.

Of course, knowing the current result for number of $α$-approximate $k$-cuts, we would conjecture the following for parametric cuts.

The number of cuts $F$ such that $c_{μ}(F)≤αλ_{μ,k}$ for $μ∈R_{≥0}$ is $O(n_{αk+d−1})$.

Note, we might relax the requirement that all $c_{i}$ and $μ$ are non-negative. Aissi et. al. showed the following [6], only assuming $c_{μ}≥0$.

The number of cuts $F$ such that $c_{μ}(F)≤λ_{μ}$ for some $c_{μ}≥0$ is $O(m_{d}n_{2}g_{d−1}n)$.

Can we obtain a stronger bound for $c_{μ}≥0$?

Parametric min-cut is related to multicriteria min-cut, which also have a lot of open problems [7].

# 4 Projected cut bounds?

Let $τ_{e}=min_{U:e∈δ(U)}c(δ(U))$, i.e. the minimum value of a cut containing $e$. Fung et. al. showed a projected generalization of the cut counting bound [8] by ignore edges appeared in small cuts. Let $E_{λ}={e∣τ_{e}≥λ}$.

The number of sets of the form $F∩E_{λ}$ where $F$ is a cut such that $c(F)≤αλ$ is $O(n_{2α})$.

If we let $λ$ be the min-cut value, this is precisely the $α$-approximate cut counting bound.

We can ask if all our theorem can have a projected cut version. We don’t know if it extends to $k$-cuts (or what is the correct generalization).

# 5 What about hypergraphs?

Most of the above results in graphs generalizes to rank $r$ hypergraphs with an extra factor related to
$r$, often is $2_{r}$. See the table in [7] for a survey. However, almost all
*exact* min-cut counting problem are unknown for hypergraphs with
unbounded rank.

All the exact min-cut counting can be generalized to hypergraphs with unbounded rank.

One can construct a hypergraph where every set $∅⊊S⊊V$ induces a distinct $α$-approximate min-cut for all $α>1$, so counting $α$-approximate min-cut is unintresting for hypergraphs of unbounded rank.

# References

**A new approach to the minimum cut problem**, Journal of ACM. 43 (1996) 601–640.

**Minimum cuts in near-linear time**, J. ACM. 47 (2000) 46–76 10.1145/331605.331608.

**On the number of small cuts in a graph**, Information Processing Letters. 59 (1996) 41–44 https://doi.org/10.1016/0020-0190(96)00079-8.

**Optimal bounds for the k-cut problem**, J. ACM. 69 (2021) 10.1145/3478018.

**Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs**, Mathematical Programming. 154 (2015) 3–28 10.1007/s10107-015-0944-8.

**Multicriteria cuts and size-constrained k-cuts in hypergraphs**, Mathematical Programming. 197 (2023) 27–69 10.1007/s10107-021-01732-0.

**A general framework for graph sparsification**, SIAM Journal on Computing. 48 (2019) 1196–1223 10.1137/16M1091666.