More Like this

1. Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts

   He, Zhongtian ; Huang, Shang-En ; Saranurak, Thatchaphol ( January 2024 , SIAM (Society for Industrial and Applied Mathematics))
2. Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts

   https://doi.org/10.1137/1.9781611977912.60  

   He, Zhongtian ; Huang, Shang-En ; Saranurak, Thatchaphol ( January 0204 , Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms)
3. Matrix product states and the quantum max-flow/min-cut conjectures

   https://doi.org/10.1063/1.5026985  

   Gesmundo, Fulvio ; Landsberg, J. M. ; Walter, Michael ( October 2018 , Journal of Mathematical Physics)
4. 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
5. Quasi-Stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality

   https://doi.org/10.14778/3574245.3574264  

   Kayali, Moe ; Suciu, Dan ( December 2022 , Proceedings of the VLDB Endowment)

   We propose quasi-stable coloring , an approximate version of stable coloring. Stable coloring, also called color refinement, is a well-studied technique in graph theory for classifying vertices, which can be used to build compact, lossless representations of graphs. However, its usefulness is limited due to its reliance on strict symmetries. Real data compresses very poorly using color refinement. We propose the first, to our knowledge, approximate color refinement scheme, which we call quasi-stable coloring. By using approximation, we alleviate the need for strict symmetry, and allow for a tradeoff between the degree of compression and the accuracy of the representation. We study three applications: Linear Programming, Max-Flow, and Betweenness Centrality, and provide theoretical evidence in each case that a quasi-stable coloring can lead to good approximations on the reduced graph. Next, we consider how to compute a maximal quasi-stable coloring: we prove that, in general, this problem is NP-hard, and propose a simple, yet effective algorithm based on heuristics. Finally, we evaluate experimentally the quasi-stable coloring technique on several real graphs and applications, comparing with prior approximation techniques. 

   more » « less