The Art Gallery Guardian

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)G=(V,E) of nn vertices, and there are positive cost c:ER+c:E\to \R^+ on the edges. We define c(F)=eFc(e)c(F)=\sum_{e\in F}c(e), to be the cost (value) of FEF\subset E.

Let P\mathcal{P} be a partition of VV where each partition class is non-empty. We define E(P)E(\mathcal{P}) to be the set of edges with end points in two different partition classes. A set of edges FF is called a kk-cut, if F=E(P)F=E(\mathcal{P}) for some P\mathcal{P} such that Pk|\mathcal{P}|\geq k.

We stress that by this definition, a kk-cut is a k1k-1-cut. A cut is a 22-cut. A min-kk-cut is a kk-cut of minimum value (cost). We let λk\lambda_k to denote the value of the min-kk-cut.

It is well known that the number of min-cuts in a graph is (n2)=O(n2){n\choose 2} = O(n^2). [1]

In the entire article, unless specifically stated, we assume kk is a fixed integer at least 22, and α\alpha is a fixed value at least 11.

We can express the state alternatively.

Theorem1

The number of cuts FF such that c(F)λ2c(F)\leq \lambda_2 is O(n2)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 αλ2\alpha \lambda_2?

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

Theorem2

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

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

Theorem3

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

Indeed, we do have a lower bound of (n2α){n \choose \floor{2\alpha}}. Just consider an unweighted cycle, where min-cut has value 22. We can pick any 2α\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 OO. 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 FF such that c(F)<αλ2c(F)< \alpha \lambda_2 is O(n2α1)O(n^{\ceil{2\alpha}-1}).

Henzinger and Williamson showed the conjecture true for all α32\alpha\leq \frac{3}{2} [3].

2 Bounds related to min-kk-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 FF such that c(F)λkc(F)\leq \lambda_k is O(n2(k1))O(n^{2(k-1)}).

There were many attempts, and people can only obtain lower bounds of the form (nk){n\choose k}. Again, a cycle would be an example of such lower bound. The min-kk-cut has value kk, and can be obtained by picking any kk edges. The gap is pretty large. Hence one would tempt to conjecture the following.

Conjecture6

The number of cuts FF such that c(F)λkc(F)\leq \lambda_k is O(nk)O(n^k).

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

Theorem7

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

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

Theorem8

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

Conjecture9

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

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

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

Theorem10

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

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

Conjecture11

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

3 Bounds on parametric cuts

Now, let’s consider parametric cuts. Consider we have dd weight functions c1,,cd:ER0c_1,\ldots,c_d:E\to \R_{\geq 0}. Define cμ(e)=i=1dμici(e)c_\mu(e) = \sum_{i=1}^d \mu_i c_i(e). We interested in knowing about cuts FF such that cμ(F)c_\mu(F) is bounded by αλμ,k\alpha \lambda_{\mu,k}, where λμ,k\lambda_{\mu,k} is the min-kk-cut value when the cost function is cμc_\mu.

Karger showed the following [6].

Theorem12

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

A even more general theorem follows.

Theorem13

The number of cuts FF such that cμ(F)αλμ,kc_\mu(F)\leq \alpha \lambda_{\mu,k} for some μR0d\mu\in \R_{\geq 0}^d is O(n2α(k1)+d1)O(n^{2\alpha(k-1)+d-1}).

Hence, we would have the following conjecture.

Conjecture14

The number of cuts FF such that cμ(F)<αλμ,kc_\mu(F)< \alpha \lambda_{\mu,k} for some μR0d\mu\in \R_{\geq 0}^d is O(nαk+d2)O(n^{\ceil{\alpha k}+d-2}).

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

Theorem15

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

The following would be even stronger conjecture.

Conjecture16

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

4 Projected cut bounds

Let τe=minU:eδ(U)c(δ(U))\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λ={eτex}E_\lambda = \set{ e | \tau_e \geq x }.

Theorem17

The number of sets of the form FEλF\cap E_\lambda where FF is a cut such that c(F)αλc(F)\leq \alpha \lambda is O(n2α)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 kk-cuts. However, we can expect the following ultimate conjecture.

Let τμ,k,e\tau_{\mu,k,e} be the minimum over all cμ(F)c_{\mu}(F), where FF is a kk-cut containing ee. Let Eμ,k,λ={eτμ,k,eλ}E_{\mu,k,\lambda} = \set{e | \tau_{\mu,k,e} \geq \lambda}.

Conjecture18

The number of sets of the form FEμ,k,λF\cap E_{\mu,k,\lambda} where FF is a cut such that cμ(F)<αλc_{\mu}(F)< \alpha \lambda for some cμ0c_\mu\geq 0 is O(nαk+d2)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 kk-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.