Faster MAX-CUT on Bounded Threshold Rank Graphs Article Swipe

MAKE IMPACT

Anderson, Prashanti , Hopkins, Samuel B. , Rajaraman, Amit , Steurer, David · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2511.11499

We design new algorithms for approximating 2CSPs on graphs with bounded threshold rank, that is, whose normalized adjacency matrix has few eigenvalues larger than $\varepsilon$, smaller than $-\varepsilon$, or both. Unlike on worst-case graphs, 2CSPs on bounded threshold rank graphs can be $(1+O(\varepsilon))$-approximated efficiently. Prior approximation algorithms for this problem run in time exponential in the threshold rank and $1/\varepsilon$. Our algorithm has running time which is polynomial in $1/\varepsilon$ and exponential in the threshold rank of the label-extended graph, and near-linear in the input size. As a consequence, we obtain the first $(1+O(\varepsilon))$ approximation for MAX-CUT on bounded threshold rank graphs running in $\mathrm{poly}(1/\varepsilon)$ time. We also improve the state-of-the-art running time for 2CSPs on bounded threshold-rank graphs from polynomial in input size to near-linear via a new comparison inequality between the threshold rank of the label-extended graph and base graph. Our algorithm is a simple yet novel combination of subspace enumeration and semidefinite programming.

Type

preprint

Landing Page

https://doi.org/10.48550/arxiv.2511.11499

OA Status

green

OpenAlex ID

https://openalex.org/W7105897810

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7105897810

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2511.11499

Digital Object Identifier

Title

Faster MAX-CUT on Bounded Threshold Rank Graphs

Work title

Type

preprint

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-14

Full publication date if available

Authors

Anderson, Prashanti, Hopkins, Samuel B., Rajaraman, Amit, Steurer, David

List of authors in order

Landing page

https://doi.org/10.48550/arxiv.2511.11499

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://doi.org/10.48550/arxiv.2511.11499

Direct OA link when available

Concepts

Bounded function, Mathematics, Combinatorics, Rank (graph theory), Discrete mathematics, Eigenvalues and eigenvectors, Adjacency matrix, Exponential function, Polynomial, Subspace topology, Simple (philosophy), Graph, Low-rank approximation, Treewidth, Matrix (chemical analysis), Time complexity, Approximation algorithm, 1-planar graph, Indifference graph, Semidefinite programming, Exponential time hypothesis, Adjacency list, Matrix polynomial, Chordal graph, Metric (unit), Linear subspace, Graph theory, Exponential growth, Simple graph

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload