# Bounds on number of cuts

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 \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}|\geq 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 ${n\choose 2} = 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.

Theorem1

The number of cuts $F$ such that $c(F)\leq \lambda_2$ is $O(n^2)$.

# 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.

Theorem2

The number of cuts $F$ such that $c(F)\leq \alpha \lambda_2$ is $O(n^{2\alpha})$.

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

Theorem3

The number of cuts $F$ such that $c(F)\leq \alpha \lambda_2$ is $O(n^{\floor{2\alpha}})$.

Indeed, we do have a lower bound of ${n \choose \floor{2\alpha}}$. Just consider an unweighted cycle, where min-cut has value $2$. We can pick any $\floor{2\alpha}$ 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.

Conjecture4

The number of cuts $F$ such that $c(F)< \alpha \lambda_2$ is $O(n^{\ceil{2\alpha}-1})$.

Henzinger and Williamson showed the conjecture true for all $\alpha\leq \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.

Theorem5

The number of cuts $F$ such that $c(F)\leq \lambda_k$ is $O(n^{2(k-1)})$.

There were many attempts, and people can only obtain lower bounds of the form ${n\choose k}$. 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.

Conjecture6

The number of cuts $F$ such that $c(F)\leq \lambda_k$ is $O(n^k)$.

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

Theorem7

The number of cuts $F$ such that $c(F)\leq \lambda_k$ is $\hat{O}(n^k)$.

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

Theorem8

The number of cuts $F$ such that $c(F)\leq \frac{(2-\epsilon)\lambda_k}{k}$ is $O(n)$.

Conjecture9

The number of cuts $F$ such that $c(F)< \frac{2\lambda_k}{k}$ is $O(n)$.

Note this theorem is basically shows we can also obtain interesting results for $\alpha = \frac{2-\epsilon}{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].

Theorem10

The number of cuts $F$ such that $c(F)\leq \alpha \lambda_k$ is $O(n^{\floor{\alpha 2(k-1)}})$.

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

Conjecture11

The number of cuts $F$ such that $c(F)< \alpha \lambda_k$ is $O(n^{\ceil{\alpha k}-1})$.

# 3 Bounds on parametric cuts

Now, let’s consider parametric cuts. Consider we have $d$ weight functions $c_1,\ldots,c_d:E\to \R_{\geq 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].

Theorem12

The number of cuts $F$ such that $c_\mu(F)\leq \lambda_{\mu,2}$ for some $\mu\in \R_{\geq 0}^d$ is $O(n^{d+1})$.

A even more general theorem follows.

Theorem13

The number of cuts $F$ such that $c_\mu(F)\leq \alpha \lambda_{\mu,k}$ for some $\mu\in \R_{\geq 0}^d$ is $O(n^{2\alpha(k-1)+d-1})$.

Hence, we would have the following conjecture.

Conjecture14

The number of cuts $F$ such that $c_\mu(F)< \alpha \lambda_{\mu,k}$ for some $\mu\in \R_{\geq 0}^d$ is $O(n^{\ceil{\alpha k}+d-2})$.

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

Theorem15

The number of cuts $F$ such that $c_\mu(F)\leq \lambda_{\mu}$ for some $c_\mu\geq 0$ is $O(m^d n^2\log^{d-1} n)$.

The following would be even stronger conjecture.

Conjecture16

The number of cuts $F$ such that $c_\mu(F) < \alpha \lambda_{\mu,k}$ for some $c_\mu\geq 0$ is $O(n^{\ceil{\alpha k}+d-2})$.

# 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 = \set{ e | \tau_e \geq x }$.

Theorem17

The number of sets of the form $F\cap E_\lambda$ where $F$ is a cut such that $c(F)\leq \alpha \lambda$ is $O(n^{2\alpha})$.

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} = \set{e | \tau_{\mu,k,e} \geq \lambda}$.

Conjecture18

The number of sets of the form $F\cap E_{\mu,k,\lambda}$ where $F$ is a cut such that $c_{\mu}(F)< \alpha \lambda$ for some $c_\mu\geq 0$ is $O(n^{\ceil{\alpha k}+d-2})$.

# References

[1] D. Karger, C. Stein, A new approach to the minimum cut problem, Journal of ACM. 43 (1996) 601–640.

[2] D.R. Karger, Minimum cuts in near-linear time, J. ACM. 47 (2000) 46–76 10.1145/331605.331608.

[3] M. Henzinger, D.P. Williamson, 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.

[4] A. Gupta, E. Lee, J. Li, The Karger-Stein Algorithm is Optimal for $k$-cut, arXiv E-Prints. (2019) arXiv:1911.09165.

[5] C. Chekuri, K. Quanrud, C. Xu, LP Relaxation and Tree Packing for Minimum k-cuts, in: J.T. Fineman, M. Mitzenmacher (Eds.), 2nd Symposium on Simplicity in Algorithms (Sosa 2019), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018: pp. 7:1–7:18 10.4230/OASIcs.SOSA.2019.7.

[6] D.R. Karger, Enumerating parametric global minimum cuts by random interleaving, in: Proceedings of the Forty-Eighth Annual Acm Symposium on Theory of Computing, ACM, New York, NY, USA, 2016: pp. 542–555 10.1145/2897518.2897578.

[7] H. Aissi, A.R. Mahjoub, S.T. McCormick, M. Queyranne, 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.

[8] W.-S. Fung, R. Hariharan, N.J.A. Harvey, D. Panigrahi, A general framework for graph sparsification, SIAM Journal on Computing. 48 (2019) 1196–1223 10.1137/16M1091666.

Posted by Chao Xu on .
Tags: Graph Theory.