Recently there are some advances on counting the number of min-cut in graphs.

Consider we have an undirected graph $G=(V,E)$ of $n$ vertices, and there are positive cost $c:E\to {\mathbb{R}}^{+}$ on the edges. We define $c(F)={\sum }_{e\in F}c(e)$, to be the cost (value) of $F\subset E$.

Let $\mathcal{P}$ be a partition of $V$ where each partition class is non-empty. We define $E(\mathcal{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(\mathcal{P})$ for some $\mathcal{P}$ such that $|\mathcal{P}|\ge k$.

We stress that by this definition, a $k$-cut is a $k-1$-cut. A cut is a $2$-cut. A min-$k$-cut is a $k$-cut of minimum value (cost). We let ${\lambda }_k$ to denote the value of the min-$k$-cut.

It is well known that the number of min-cuts in a graph is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=O(n^2)$. [1]

In the entire article, unless specifically stated, we assume $k$ is a fixed integer at least $2$, and $\alpha$ is a fixed value at least $1$.

We can express the state alternatively.

1 Bounds related to scaling of the min-cut

What happens when we want to know about the number of cuts with value at most $\alpha {\lambda }_2$?

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

With more careful analysis using tree packing, Karger obtained the following [2].

Indeed, we do have a lower bound of $\left(\genfrac{}{}{0ex}{}{n}{\lfloor 2\alpha \rfloor }\right)$. Just consider an unweighted cycle, where min-cut has value $2$. We can pick any $\lfloor 2\alpha \rfloor$ edges, which forms a cut of value at most $\alpha$ times the min-cut.

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

Henzinger and Williamson showed the conjecture true for all $\alpha \le \frac{3}{2}$ [3].

2 Bounds related to min-$k$-cut

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

There were many attempts, and people can only obtain lower bounds of the form $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. 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. The gap is pretty large. Hence one would tempt to conjecture the following.

Recently, Gupta, Lee and Li almost closes the gap [4].

Here $\hat{O}$ hides a factor smaller than any $n^{ϵ}$. While closing the gap, they showed thhe following interesting theorem.

Note this theorem is basically shows we can also obtain interesting results for $\alpha =\frac{2-ϵ}{k}<1$.

How about approximate min-$k$-cuts? Chekuri, Quanrud and I extended the tree packing analysis of Karger, and obtained the following result for $k$-cuts [5].

Combining the Conjecture 6 and Conjecture 4, we get a unified conjecture, even for $\alpha <1$.

3 Bounds on parametric cuts

Now, let’s consider parametric cuts. Consider we have $d$ weight functions $c_1,\dots ,c_d:E\to {\mathbb{R}}_{\ge 0}$. Define $c_{\mu }(e)={\sum }_{i=1}^d{\mu }_i{c}_i(e)$. We interested in knowing about cuts $F$ such that $c_{\mu }(F)$ is bounded by $\alpha {\lambda }_{\mu ,k}$, where ${\lambda }_{\mu ,k}$ is the min-$k$-cut value when the cost function is $c_{\mu }$.

Karger showed the following [6].

A even more general theorem follows.

Hence, we would have the following conjecture.

Note, we might relax the requirement that all $c_i$ and $\mu$ are non-negative. Aissi et. al. showed the following [7].

The following would be even stronger conjecture.

4 Projected cut bounds

Let ${\tau }_e={\min }_{U:e\in \delta (U)}c(\delta (U))$. Fung et. al. showed a projected generalization of the cut counting bound [8]. Let $E_{\lambda }=\left\{e|{\tau }_e\ge x\right\}$.

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

We can of course ask if all our theorem can be applied to projected cuts. We don’t even know if it extends to $k$-cuts. However, we can expect the following ultimate conjecture.

Let ${\tau }_{\mu ,k,e}$ be the minimum over all $c_{\mu }(F)$, where $F$ is a $k$-cut containing $e$. Let $E_{\mu ,k,\lambda }=\left\{e|{\tau }_{\mu ,k,e}\ge \lambda \right\}$.

References