More Like this

1. Separating MAX 2-AND, MAX DI-CUT and MAX CUT

   https://doi.org/10.1109/FOCS57990.2023.00023  

   Brakensiek, Joshua; Huang, Neng; Potechin, Aaron; Zwick, Uri (November 2023, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS))

   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 SDP-based approximation algorithm of Goemans and Williamson. The currently best approximation algorithm for MAX DI-CUT, i.e., the MAX CUT problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UGC-hardness result for it, showing that 0.87446 ≤ αDI-CUT ≤ 0.87461, where αDI-CUT is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND 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 DI-CUT each constraint is of the form \neg{x1}∧x2, where x1 and x2 are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that α2AND < 0.87435 and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND, showing that 0.87414 ≤ α2AND ≤ 0.87435. Our upper bound on MAX DI-CUT is achieved via a simple, analytical proof. The lower bounds on MAX DI-CUT and MAX 2-AND (the new approximation algorithms) use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs. 

   more » « less
2. On the Cut-Query Complexity of Approximating Max-Cut

   https://doi.org/10.4230/LIPICS.ICALP.2024.115  

   Plevrakis, Orestis; Ragavan, Seyoon; Weinberg, S Matthew (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [Rubinstein et al., 2018]. Graph algorithms in this cut query model and other query models have recently been studied for various other problems such as min-cut, connectivity, bipartiteness, and triangle detection. Max-cut in the cut query model can also be viewed as a natural special case of submodular function maximization: on query S ⊆ V, the oracle returns the total weight of the cut between S and V\S. Our first main technical result is a lower bound stating that a deterministic algorithm achieving a c-approximation for any c > 1/2 requires Ω(n) queries. This uses an extension of the cut dimension to rule out approximation (prior work of [Graur et al., 2020] introducing the cut dimension only rules out exact solutions). Secondly, we provide a randomized algorithm with Õ(n) queries that finds a c-approximation for any c < 1. We achieve this using a query-efficient sparsifier for undirected weighted graphs (prior work of [Rubinstein et al., 2018] holds only for unweighted graphs). To complement these results, for most constants c ∈ (0,1], we nail down the query complexity of achieving a c-approximation, for both deterministic and randomized algorithms (up to logarithmic factors). Analogously to general submodular function maximization in the same model, we observe a phase transition at c = 1/2: we design a deterministic algorithm for global c-approximate max-cut in O(log n) queries for any c < 1/2, and show that any randomized algorithm requires Ω(n/log n) queries to find a c-approximate max-cut for any c > 1/2. Additionally, we show that any deterministic algorithm requires Ω(n²) queries to find an exact max-cut (enough to learn the entire graph). 

   more » « less
3. Max cut and semidefinite rank

   https://doi.org/10.1016/j.orl.2024.107067  

   Mirka, Renee; Williamson, David P (March 2024, Operations Research Letters)

   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 Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n-1 . Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs. 

   more » « less
4. Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut

   https://doi.org/10.1145/3651148  

   Cheng, Yu; Li, Max; Lin, Honghao; Tai, Zi-Yi; Woodruff, David P.; Zhang, Jason (May 2024, Proceedings of the ACM on Management of Data)

   In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 ± ε)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires Ω(n²) bits even for constant ε. To circumvent this, recent works study β-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most β times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous Ømega(n √β/ε) lower bound in the for-each model to ~Ω (n √β /ε) and we improve the previous Ω(n β/ε) lower bound in the for-all model to Ω(n β/ε²). This resolves the main open questions of (Cen et al., ICALP, 2021). The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an ΩL(min m, m/ε²k R) lower bound for this problem, which improves the previous ΩL(m/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+ε)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors. 

   more » « less
5. Approximation Algorithm for Norm Multiway Cut

   https://doi.org/10.4230/LIPIcs.ESA.2023.32  

   Carlson, Charlie; Jafarov, Jafar; Makarychev, Konstantin; Makarychev, Yury; Shan, Liren (August 2023, Proceedings of the European Symposium on Algorithms)

   Gørtz, Inge Li; Farach-Colton, 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_p-norm 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 Dense-vs-Random Conjecture. 

   more » « less