Finding Colorings in One-Sided Expanders

Rares-Darius Buhai [email protected] ETH Zurich Yiding Hua [email protected] ETH Zurich David Steurer [email protected] ETH Zurich Andor Vári-Kakas [email protected] ETH Zurich · 2025

Read Finding Colorings in One-Sided Expanders by Rares-Darius Buhai [email protected] ETH Zurich Yiding Hua [email protected] ETH Zurich David Steurer [email protected] ETH Zurich Andor Vári-Kakas [email protected] ETH Zurich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02825.txt.

Description

Rares-Darius Buhai and three co-authors give new algorithms and hardness results for coloring and independent set problems on one sided expander graphs. Expanders are sparse yet highly connected graphs that appear across computer science. On a 3-colorable regular one sided expander, their method finds in polynomial time either a large independent set or a near complete proper 3-coloring.

That result improves a recent breakthrough that found much smaller independent sets in such graphs. A fast approximation for vertex cover on strong expanders also improves on past factors. A new stratification of coloring by matrices yields a sharp split. When the matrix has repeated rows the problem is hard, and when it does not, their algorithms solve it fast.

Catalog record

CREATORRares-Darius Buhai [email protected] ETH Zurich Yiding Hua [email protected] ETH Zurich David Steurer [email protected] ETH Zurich Andor Vári-Kakas [email protected] ETH Zurich
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE173 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-02825

Browse the full library · About the Tower of Babel