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 always a $j$-cut for $j\le k$. A cut is defined as 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. A $\alpha$-approximate $k$-cut is a cut of value at most $\alpha {\lambda }_k$.

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

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 approximate min-cuts

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 added a floor function to the exponent [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 would be interesting to obtain a matching upper bound for arbitrary $\alpha$. 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 $\alpha$-approximate min-$k$-cut

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

One can show a 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. Recently, the upper bound has been closed (up to constant factor if $k$ is fixed) [4].

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

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

3 Bounds on (approximate) 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)$ for $\mu \in {\mathbb{R}}_{\ge 0}^d$. We are 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 [5].

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

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

Note, we might relax the requirement that all $c_i$ and $\mu$ are non-negative. Aissi et. al. showed the following [6], only assuming $c^{\mu }\ge 0$.

Can we obtain a stronger bound for $c^{\mu }\ge 0$?

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

4 Projected cut bounds?

Let ${\tau }_e={\min }_{U:e\in \delta (U)}c(\delta (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_{\lambda }=\left\{e|{\tau }_e\ge \lambda \right\}$.

If we let $\lambda$ be the min-cut value, this is precisely the $\alpha$-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.

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

References