2 papers
cs.DS2026
Expander Decomposition with Almost Optimal Overhead
Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak
We present the first polynomial-time algorithm for computing a near-optimal \emph{flow}-expander decomposition. Given a graph and a parameter , our algorithm removes at mos…
cs.DS2026
Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
Nikhil Bansal, Neng Huang, Euiwoong Lee
We present a polynomial-time algorithm that colors any 3-colorable -vertex graph using colors, improving upon the previous best bound of $\widetilde{O}(n^{0.197…