Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is αCUT ≃ 0.87856, obtained by the celebrated SDPbased approximation algorithm of Goemans and Williamson. The currently best approximation algorithm for MAX DICUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DICUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DICUT and a new UGChardness result for it, showing that 0.87446 ≤ αDICUT ≤ 0.87461, where αDICUT is the best approximation ratio that can be obtained in polynomial time for MAX DICUT under UGC. The new upper bound separates MAX DICUT from MAX CUT, resolving a question raised by Feige and Goemans.
A natural generalization of MAX DICUT is the MAX 2AND problem in which each constraint is of the form z1∧z2, where z1 and z2 are literals, i.e., variables or their negations (In MAX DICUT each constraint is of the form \neg{x1}∧x2, where x1 and x2 are variables.) Austrin separated MAX 2AND from MAX CUT by showing that α2AND < 0.87435 and conjectured that MAX 2AND and MAX DICUT have the same approximation ratio. Our new lower bound on MAX DICUT refutes this conjecture, completing the separation of the three problems MAX 2AND, MAX DICUT and MAX CUT. We also obtain a new lower bound for MAX 2AND, showing that 0.87414 ≤ α2AND ≤ 0.87435.
Our upper bound on MAX DICUT is achieved via a simple, analytical proof. The lower bounds on MAX DICUT and MAX 2AND (the new approximation algorithms) use experimentallydiscovered distributions of rounding functions which are then verified via computerassisted proofs.
more »
« less
Simultaneous MaxCut Is Harder to Approximate Than MaxCut
A systematic study of simultaneous optimization of constraint satisfaction problems was initiated by Bhangale et al. [ICALP, 2015]. The simplest such problem is the simultaneous MaxCut. Bhangale et al. [SODA, 2018] gave a .878minimum approximation algorithm for simultaneous MaxCut which is almost optimal assuming the Unique Games Conjecture (UGC). For single instance MaxCut, GoemansWilliamson [JACM, 1995] gave an α_GWapproximation algorithm where α_GW ≈ .87856720... which is optimal assuming the UGC. It was left open whether one can achieve an α_GWminimum approximation algorithm for simultaneous MaxCut. We answer the question by showing that there exists an absolute constant ε₀ ≥ 10^{5} such that it is NPhard to get an (α_GW ε₀)minimum approximation for simultaneous MaxCut assuming the Unique Games Conjecture.
more »
« less
 Award ID(s):
 1813438
 NSFPAR ID:
 10181527
 Date Published:
 Journal Name:
 35th Computational Complexity Conference (CCC 2020)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the GoemansWilliamson max cut SDP by showing the existence of an optimal dual solution with rank n1 . Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs.more » « less

Gørtz, Inge Li ; FarachColton, Martin ; Puglisi, Simon J ; Herman, Grzegorz (Ed.)We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced l_pnorm Multiway Cut, a generalization of the problem, in which the goal is to minimize the l_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} n log^{1/2 + 1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4ε} approximation algorithm for every ε > 0 assuming the Hypergraph DensevsRandom Conjecture.more » « less

Tauman Kalai, Yael (Ed.)Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, nearlinear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a nearlinear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vectormatrixvector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cuttoggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cuttoggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cuttoggling algorithm can achieve (almost) the same running time as its primal cycletoggling counterpart.more » « less

null (Ed.)Finding locally optimal solutions for MAXCUT and MAX k CUT are wellknown PLScomplete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worstcase instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the runtime of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for maxcut in arbitrary graphs is quasipolynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for maxcut in complete graphs is ( O Φ 5 n 15.1 ), where Φ is an upper bound on the random edgeweight density and Φ is the number of vertices in the input graph. While Angel, Bubeck, Peres, and Wei’s result showed the first polynomial smoothed complexity, they also conjectured that their runtime bound is far from optimal. In this work, we make substantial progress toward improving the runtime bound. We prove that the smoothed complexity of FLIP for maxcut in complete graphs is O (Φ n 7.83 ). Our results are based on a carefully chosen matrix whose rank captures the runtime of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for MAX3CUT in complete graphs is polynomial and for MAX  k  CUT in arbitrary graphs is quasipolynomial. We believe that our techniques should also be of interest toward showing smoothed polynomial complexity of FLIP for MAX  k  CUT in complete graphs for larger constants k .more » « less