The DOI matches its DataCite record.
Large Cuts with Local Algorithms on Triangle-Free Graphs
Open accessAbstract
We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/\sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/\sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Another interesting result was given by Marwaha et al. [19] for uniform Maxk XOR problems, who observed better performance than the best-known classical algorithm, the local threshold algorithm [20]. The graphs associated with the problem instances in their investigation were regular and triangle-free .”
From Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems (2024) · cites this paper as [20]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 15
- [1][1] Noga Alon. Bipartite subgraphs. Combinatorica , 16(3):301-311, 1996. -
- [2][2] Paul Erd˝ os. Problems and results in graph theory and combinatorial analysis. In John Adrian Bondy and U. S. R. Murty, editors, Proc. Graph Theory and Related Topics (University of Waterloo, July 1977) , pages 153-163. Academic Press, 1979. -
- [3][3] Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. In Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007) , volume 4596 of Lecture Notes in Computer Science , pages 231-242. Springer, 2007. doi:10.1007/978-3-540-73420-8 22 . - · DOI
- [5][5] Johan H˚ astad. Some optimal inapproximability results. Journal of the ACM , 48 (4):798-859, 2001. doi:10.1145/502090.502098 . - · DOI · Paper page
- [6][6] Pierre Kelsen. Neighborhood graphs and distributed ∆ + 1-coloring. In Proc. 5th Scandinavian Workshop on Algorithm Theory (SWAT 1996) , volume 1097 of Lecture Notes in Computer Science , pages 223-233. Springer, 1996. doi:10.1007/ 3-540-61422-2 134 . -
- [7][7] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing , 37(1):319-357, 2007. doi:10.1137/S0097539705447372 . - · DOI
- [8][8] Adrian K¨ ugel. Improved exact solver for the weighted Max-SAT problem. In Daniel Le Berre, editor, Proc. Pragmatics of SAT Workshop (POS 2010) , volume 8 of EasyChair Proceedings in Computing , pages 15-27, 2012. http://www.easychair.org/ publications/?page=2003892821 . -
- [9][9] Fabian Kuhn and Roger Wattenhofer. On the complexity of distributed graph coloring. In Proc. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC 2006) , pages 7-15. ACM Press, 2006. doi:10.1145/1146381.1146387 . - · DOI
- [10][10] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing , 21(1):193-201, 1992. doi:10.1137/0221015 . - · DOI
- [11][11] Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics , 4(3):409-412, 1991. doi:10.1137/0404036 . - · DOI
- [12][12] Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences , 43(3):425-440, 1991. doi:10.1016/0022-0000(91)90023-X . - · DOI · Paper page
- [13][13] Svatopluk Poljak and Zsolt Tuza. Maximum cuts and largest bipartite subgraphs. In William Cook, L´ aszl´ o Lov´ asz, and Paul Seymour, editors, Combinatorial Optimization , volume 20 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pages 181-244. AMS, 1995. -
- [14][14] Joel Rybicki. Exact bounds for distributed graph colouring. Master's thesis, Department of Computer Science, University of Helsinki, May 2011. http://urn.fi/URN: NBN:fi-fe201106091715 . -
- [15][15] James B. Shearer. A note on bipartite subgraphs of triangle-free graphs. Random Structures & Algorithms , 3(2):223-226, 1992. doi:10.1002/rsa.3240030211 . - · DOI
- [16][16] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing , 29(6):2074-2097, 2000. doi:10.1137/S0097539797328847 . · DOI
Cited by
Müller, T., Singh, A., Wilhelm, F. K., & Bode, T. (2024) · arXiv · doi:10.48550/arxiv.2411.19388 · Cited by 5
Metadata
- Authors
- Hirvonen, J., Rybicki, J., Schmid, S., & Suomela, J.
- Affiliations
- Centre National de la Recherche Scientifique (FR)
- University of Helsinki (FI)
- Aalborg University (DK)
- Aalto University (FI)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2014
- Volume
- 24
- Issue
- 4
- ISSN
- 1077-8926 (ISSN-L)
- arXiv
- 1402.2543
- OpenAlex
- W2155864159
- Cited by
- 32
- References
- 0
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 5 · 2022: 3 · 2021: 6 · 2020: 1 · 2019: 4 · 2018: 2 · 2017: 5 · 2016: 2 · 2015: 2
- FWCI
- 2.47
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- Locations
- The Electronic Journal of Combinatorics (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- Aaltodoc (Aalto University) (submittedVersion, other-oa)
- Työväentutkimus Vuosikirja (submittedVersion, other-oa)
- VBN Forskningsportal (Aalborg Universitet) (submittedVersion, other-oa)
- arXiv (Cornell University)
- Funders
- Helsingin Yliopisto
- Aalto-Yliopisto
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Limits and Structures in Graph Theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- triangle-free graphs, d-regular graphs, bipartite subgraphs, MaxCut, local algorithms, lower bounds
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
