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

الملخص EN

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.