# On Graphs of the Cone Decompositions for the Min-Cut and Max-Cut Problems

Authors: Vladimir Bondarenko; Andrei Nikolaev
Journal: International Journal of Mathematics and Mathematical Sciences
 (2016)

---

## Abstract

We consider maximum and minimum cut problems with nonnegative weights of edges. We define the graphs of the cone decompositions and find a linear clique number for the min-cut problem and a superpolynomial clique number for the max-cut problem. These values characterize the time complexity in a broad class of algorithms based on linear comparisons.


---

## Body

## 1. Introduction

We consider the well-known maximum and minimum cut problems.Instance 1.
Given an undirected graphG=(V,E) and a weight function c:E→Z+, it is required to find such a subset S of the vertex set V (cut) that the sum of the weights of the edges from E with one endpoint in S and another in V∖S is as small as possible (minimum cut or min-cut) or as large as possible (maximum cut, max-cut).While our discussion of the cut problem [1] in this paper is focused on integral edge weights, we remark that results and their proofs remain valid with real weights.It is known that the min-cut problem with nonnegative edges is polynomially solvable: Dinic-Edmonds-Karp algorithm based on the maximum flow problem has the running time ofO(|V|3|E|) [2], Hao-Orlin modification has the running time of O(|V||E|log(|V|2/|E|)) [3], and Stoer-Wagner algorithm that does not use the flow techniques has the complexity O(|V||E|+|V|2log|V|) [4].Nevertheless, the min-cut and max-cut problems with arbitrary edges and the max-cut problem with nonnegative edges are NP-hard with no known algorithms faster than an exhaustive search [1].We will estimate the min-cut and max-cut complexity with the polyhedral approach and study the clique number of the graph of the cone decomposition for the cut problems with nonnegative edges. This value is known as a measure of complexity in a wide class of algorithms based on linear comparisons. The presented results were announced in [5]. Similar characteristics of the shortest path and 3-dimensional matching problems are considered in [6, 7].


## 2. Cut Polytope and Cone Decomposition

With every subsetS⊆Nn={1,…,n} (every cut in the complete graph on n vertices) we associate a characteristic vector according to the following rule:(1)d=n2,δS∈0,1d,δSi,j=1,ifS∩i,j=1,0,otherwise.Therefore, the coordinates of the characteristic vector (also known as the cut vector) indicate whether the corresponding edges are in the cut or not. The convex hull of all cut vectors is known as the cut polytope CUT(n) [8]: (2)CUTn=convδS:S⊆Nn⊆Rd.Max-cut and min-cut problems are reduced to the linear programming on theCUT(n) polytope with objective vector containing the weights of the edges.We introduce a dual construction. LetX be a set of points in Rd. Let x∈X. Denote (3)Kx=c∈Rd:c,x≤c,y,∀y∈X.Since K(x) is the set of solutions of a finite system of homogeneous linear inequalities, it is a convex polyhedral cone. Given that (4)⋃x∈XKx=Rd,the set of all cones K(x) is called the cone decomposition of the space Rd by the set X. Cone decomposition is similar to Voronoi diagram, exactly coinciding with it if the Euclidean norm of all points in X is equal.We consider the graph of the cone decomposition with the cones being the vertices, and two conesK(x) and K(y) are adjacent if and only if they have a common facet: (5)dimKx∩Ky=d-1.Denote byω(X) the clique number, the number of vertices in a maximum clique, of the graph of the cone decomposition. It is known [6, 9] that the complexity of the direct type algorithms, based on linear comparisons, of finding the minimum (or maximum, if we change the sign of the inequality in the definition of the cone) of a linear objective function (c,x) on the set X, or, which is the same, finding the cone K(x), which the vector c belongs to, cannot be less than the value of ω(X)-1.Indeed, if some algorithm at each step performs a single linear comparison (verification of linear inequality(c,y)≥b or (c,y)≤b), from a geometric point of view that means drawing a hyperplane and discarding a wrong half-space. But if n cones are pairwise adjacent, then for any hyperplane there exist points of at least n-1 cones in one of the half-spaces; hence, such direct type algorithm (algorithm with direct type linear decision tree [6, 9]) can separate and discard at most one wrong cone at a time in the worst case (Figure 1). Thus, ω(X)-1 is a lower bound on the height of the decision tree and on the complexity of combinatorial optimization problems in the wide class of algorithms, including sorting algorithms, greedy algorithm, dynamic programming, and branch and bound.Figure 1
Any hyperplane can separate at most one pairwise adjacent cone.We introduce four different cone decompositions: for the maximum cut and the minimum cut problems, as well as for the problems with nonnegative edges. Denote byΔn the set of vertices of the cut polytope CUT(n). Let x∈Δn. Define (6)Kmaxx=c∈Rd:c,x≥c,y,∀y∈Δn,Kminx=c∈Rd:c,x≤c,y,∀y∈Δn,Kmax+x=c∈Rd,c≥0:c,x≥c,y,∀y∈Δn,Kmin+x=c∈Rd,c≥0:c,x≤c,y,∀y∈Δn.It is known [10] that the graph of the CUT(n) polytope is complete, so the graphs of cone decompositions Kmax and Kmin are complete as well, because the adjacency of vertices means the adjacency of the corresponding cones, and, therefore, their clique numbers are exponential. However, if we consider the problem with nonnegative edges, then the situation is fundamentally different.Note that these constructions are deeply connected with the cut polyhedron [11, 12]. In particular, we reestablish the results on the min-cut in terms of cones.


## 3. Graph of the Cone Decomposition for the Min-Cut Problem with Nonnegative Edges

Two setsA and B are called intersecting if (7)A∩B≠∅,A∖B≠∅,B∖A≠∅.Lemma 1.
ConesKmin+(x) and Kmin+(y) are adjacent if and only if cuts x and y are not intersecting.Proof.
Assume that the cutsx and y are intersecting, but the cones Kmin+(x) and Kmin+(y) are adjacent. Adjacency of the cones means that there exists a nonnegative vector c that belongs both to Kmin+(x) and Kmin+(y), but does not belong to any other cone from the cone decomposition Kmin+:(8)∃c∈Rdc≥0,∀z∈Δn∖x,y,c,x=c,y<c,z.
It is well known that the cut function of a nonnegatively weighted undirected graph is submodular [12]: (9)c,x+c,y≥c,x∪y+c,x∩y.
Since cutsx and y are intersecting, both cuts x∪y and x∩y are nonempty, and at least one of them is less than (c,x) and (c,y). So we have acontradiction: cones Kmin+(x) and Kmin+(y) are not adjacent.
Now we consider two cutsx and y that are not intersecting. Without loss of generality we assume that x⊂y. We assign the weights of edges in the following way: all edges that connect subsets x and y∖x have the total sum equal to some positive integer k, the sum of all edges connecting y¯ and y∖x is also equal to k, edges between x and y¯ have zero weight, and any other edge is equal to k+1 (Figure 2).
We have cutsx and y equal to k, cut y∖x equals 2k, and any other cut contains at least one edge of the weight k+1. Thus, by inequality (8), cones Kmin+(x) and Kmin+(y) are adjacent.Figure 2
Cutsx and y in the case of x⊂y.Theorem 2.
Clique numberω(Kmin+) of the graph of the cone decomposition for the min-cut problem with nonnegative weights of edges is linear by the number n of vertices of the original graph and equal to (10)ωKmin+=2n-3.Proof.
A familyF is called laminar if no two sets A,B∈F are intersecting. It is known [11] that a laminar family of subsets of V that does not contain ∅, V, and both a subset S and its complement V∖S has at most 2n-3 subsets. Since, by Lemma 1, a laminar family of cuts corresponds to a clique in the graph of the cone decomposition, we obtain the required value.As an example of2n-3 pairwise adjacent cones we can consider the following cuts:(i)
ncuts of the form Si={i}, where 1≤i≤n;(ii)
n-3 cuts of the form Sk={1,2,…,k}, where 2≤k≤n-2.


## 4. Graph of the Cone Decomposition for the Max-Cut Problem with Nonnegative Edges

Lemma 3.
ConesKmax+(x) and Kmax+(y) are adjacent if and only if one of the following conditions is true: (i)
cutsx and y are intersecting;(ii)
the difference between two cutsx and y has exactly one element: (11)x∖y=1,ory∖x=1,orx¯∖y=1,ory¯∖x=1.Proof.
We consider two cutsx and y that are not intersecting and have more than one element in the difference. Without loss of generality, we assume that x⊂y. We divide the set y∖x into two subsets A and B, since it has at least two vertices, and consider two additional cuts z=x∪A and t=x∪B (Figure 3).
Hence, by submodularity of the cut function, we have(12)c,z+c,t≥c,x=z∩t+c,y=z∪t.Thus, cones Kmax+(x) and Kmax+(y) can not be adjacent.
Now we assume that cutsx and y are intersecting and assign the weights in such way that all the edges, connecting sets x∩y and x¯∩y¯, have positive weights with the total sum equal to some integer k; similarly, the edges, connecting sets x∩y¯ and x¯∩y, also have positive weights with the same total sum k, while all the remaining edges are equal to zero (Figure 4).
Cutsx and y have the weight equal to 2k. Since 2k is the total weight of all edges in the graph, no other cuts can have weight exceeding 2k. As for the cuts equal to 2k, they have to split vertex sets x∩y and x¯∩y¯, as well as x∩y¯ and x¯∩y. Only cuts x and y meet this requirement. Thus, cones Kmax+(x) and Kmax+(y) are adjacent.
The last configuration has cutsx and y not intersecting with exactly one element in the difference. Without loss of generality, we assume that x⊂y and y∖x={w}, where w∈V. We assign the weights of the edges in the following way: the weight of all edges connecting w and x is equal to k, the same is for the edges connecting w and y, every edge between x and y¯ has the weight k+1, with the total number of these edges denoted by m, and the weights of all other edges are assigned to be zero (Figure 5).
The total weight of all edges in the graph is equal tom(k+1)+2k. The weight of both cuts x and y is m(k+1)+k. If some cut z does not include at least one edge of the weight k+1, then it is less than x and y: (13)c,z≤m-1k+1+2k=mk+1+k-1.Thus, any maximum cut should split vertex sets x and y¯, while vertex w can be included (cut y) or excluded (cut x). Hence, cones Kmax+(x) and Kmax+(y) are adjacent.Figure 3
Cutsx, y, z, and t.Figure 4
Intersecting cutsx and y.Figure 5
Cutsx and y with one element in the difference.Theorem 4.
Clique numberω(Kmax+) of the graph of the cone decomposition for the max-cut problem with nonnegative weights of edges is superpolynomial by the number n of vertices of the original graph and equals(14)ωKmax+=nn2-1≥2n2n1-2n+2,for even n and(15)ωKmax+=nn-12≥2n2n-11-1n+1,for odd n.Proof.
The adjacency criterion of Lemma3 is very similar to the Erdös-Ko-Rado theorem about the largest number of pairwise intersecting subsets. Therefore, we will use the construction from the Katona short proof [13].
First of all, we will consider only subsetsS⊂V=Nn={1,2,3,…,n} of the size |S|≤⌊n/2⌋. Otherwise, we can replace S with its complement V∖S that will have the required number of vertices.
Suppose we have some familyA of cuts with pairwise adjacent cones. We arrange the elements of Nn into any cyclic order and consider the sets from A that form intervals within this cyclic order. The question is how many intervals of the cyclic order may belong to A. For example, consider the cyclic order {1,2,…,n} and the interval S={1,2,…,s}. There are two intervals {1,2,…,s-1} and {2,…,s} inside S and two intervals {1,2,…,s,s+1} and {n,1,…,s} containing S, with cones adjacent to Kmax+(S). From these four intervals, only two may be pairwise adjacent. Then, for any i∈{2,…,s} there are at most two adjacent intervals, starting at i, with one element in the difference, {i,…,t} and {i,…,t,t+1}, and two adjacent intervals, ending at i-1, {q,…,i-1} and {q-1,q,…,i-1}. Again from these four intervals only two may be pairwise adjacent. Thus, there are 2(s-1)+2=2s intervals in the cyclic order with the cones adjacent to Kmax+(S).
Letn be equal to 2k+1. Since s≤k, at most 2k+1 intervals for a single cyclic order may belong to the family A. We will count the number of pairs (S,C), where S is a set in A and C is a cyclic order for which S is an interval, in two ways. First, for each set S we may generate C by choosing one of s! permutations of S and (2k+1-s)! permutations of the remaining elements. The smallest value is for s=k. And second, there are (2k)! cyclic orders, each of which has at most 2k+1 intervals of A. Thus, we have (16)Ak!k+1!≤S,C≤2k+12k!,A≤2k+1!k!k+1!=2k+1k.
We consider two random cutsx and y of the size k. Since they have the same size, x and y cannot be nested. Therefore, if they do not intersect, then x⊂y¯,|y¯∖x|=2k+1-k-k=1, and cones Kmax+(x) and Kmax+(y) are adjacent. Thus, the set of all possible 2k+1k cuts of the size k form a clique in the graph of the cone decomposition, and we have (17)ωKmax+=nn-12,for odd n.
Letn be equal to 2k. We again consider the cyclic order and estimate the maximum number of intervals with pairwise adjacent cones. Since any interval of the size s may be adjacent to at most 2s intervals, the maximum value will be for s=k. However, there are only k intervals of the size k that form a cut, as all other intervals of the size k will be complementary to them. So we have to include some smaller intervals as well. We assume that A contains only intervals of the sizes k and k-1, and at most 2k-1 intervals for a single cyclic order may belong to the family A.
We divideA into two subsets Ak and Ak-1, containing only cuts of the corresponding size. Cuts of Ak and Ak-1 cannot be nested, as they have the same size, and the difference with complementary cuts are not equal to one. Therefore, they are pairwise intersecting. Considering that(18)2k-1k-1+2k-1k-2=2kk-1.
By Erdös-Ko-Rado theorem we have(19)Ak≤2k-1k-1,Ak-1≤2k-1k-2,A=Ak+Ak-1≤2kk-1.
We consider all the cuts of the sizesk and k-1 that include vertex 1. If two such cuts x and y do not intersect, then, without loss of generality, x⊂y and |y∖x|=k-(k-1)=1. There are exactly 2k-1k-1+2k-1k-2 of such cuts, so we have (20)A=2kk-1.
Now suppose that there exists a familyB of cuts with pairwise adjacent cones that contains intervals of the size less than k-1 and is greater than A. Then, for any cyclic order with at least one interval of the size less than k-1 there are at most 2k-3 intervals that may belong to the family B. At the same time, for a smaller cut S we can construct more cyclic orders C containing S as an interval. And so we get thecontradiction: (21)2k-12k-1!=S∈A,C,S∈A,C<S∈B,C,S∈B,C<2k-12k-1!.
Thus, the familyA of k and k-1 sized cuts with pairwise adjacent cones is the largest, and (22)ωKmax+=nn2-1for even n.
We can estimate these values using the central binomial coefficient:(23)2nn≥4n4n,nn2-1=n/2n-n/2+1nn2=nn+2nn2,ωKmax+=nn2-1≥2n2n1-2n+2,for even n and(24)nn-12=nn-n-1/2n-1n-12=2nn+1n-1n-12,ωKmax+=nn-12≥2n2n-11-1n+1,for odd n.


## 5. Conclusion

Min-cut and max-cut problems with arbitrary weights of edges and max-cut problem with nonnegative edges are NP-hard, while there are efficient polynomial algorithms for the min-cut problem with nonnegative edges. This situation corresponds to the geometric properties of the problem. Clique number of the graph of the cone decomposition is known as the lower bound on complexity in the class of algorithms that are based on linear comparisons. Graphs of the cone decompositions for the cut problems with arbitrary edges are complete, so their clique numbers are exponential. Clique number for the max-cut problem with nonnegative edges is superpolynomial and for the min-cut problem with nonnegative edges is linear.Note that both obtained values are below the complexity of the best known algorithms for the cut problems with nonnegative edges. Hence, at least on this approach, there are no geometric obstacles to the construction of the more efficient algorithms.Described results are based on the properties of the cut problem. For other combinatorial problems, it can be different.Theorem 5.
If all points of the setX⊂{0,1}d belong to a sphere centered at the origin (25)a=b,∀a,b∈X,and for a pair of points x,y∈X cones Kmax(x) and Kmax(y) are adjacent, then nonnegative cones Kmax+(x) and Kmax+(y) are adjacent as well.
The same is true for conesKmin(x) and Kmin(y) and nonnegative cones Kmin+(x) and Kmin+(y).Proof.
Consider a set of pointsX⊂{0,1}d such that (26)a=b,∀a,b∈X.
Suppose that for a pair of pointsx and y of X cones Kmax(x) and Kmax(y) are adjacent: (27)c,x=c,y>c,z,∃c∈Rd,∀z∈X∖x,y.
Then there exists a vectorc+∈Rd (c+≥0) such that (28)c+=c+c~,wherec~=C1,1,1,…,1∈Rd.
Now we have that(29)c,x=c,y>c,z,∀z∈X∖x,yc+-c~,x>c+-c~,z,c+,x-c~,x>c+,z-c~,z,x=z⟹c~,x=c~,z,c+,x=c+,y>c+,z.
ConesKmax+(x) and Kmax+(y) are adjacent.
ForKmin+ cones proof can be obtained from the above by changing the sign in the corresponding inequality.As a result, for the problem where Euclidean norm of the characteristic vectors is a constant, graphs of the cone decompositions with arbitrary objective vectors and nonnegative objective vectors will completely coincide, and, hence, the same problem on the minimum and maximum will have the same characteristics.This is true, for example, for the traveling salesman problem, where all the possible solutions can be encoded as 0/1 vectors with exactlyn units, or the spanning tree problem, where all the possible solutions have n-1 units. Indeed, all four instances of the traveling salesman problem (minimum with arbitrary edges, minimum with nonnegative edges, maximum with arbitrary edges, and maximum with nonnegative edges) are known to be NP-hard, while all four instances of the spanning tree problem are polynomially solvable. At the same time, for the path problem in the graph with nonnegative edges the path can contain any number of edges, and possible solutions do not belong to a sphere centered at the origin, so, as well as for the cut problem, the shortest path problem is polynomially solvable, while the longest path problem is NP-hard [1].



---

*Source: 7863650-2016-02-01.xml*