Answers are grounded in this paper and cite their sources.
We present a polynomial-time approximation scheme (PTAS) for all Boolean arity-two maximum constraint satisfaction problems (Boolean Max-2-CSP) where the constraint graph is either interval or has bounded rank-width. This class of problems includes, for example, Max-Cut, Max-DiCut, Max-2-Lin(2), and Max-2-SAT. In particular, this settles the approximability of Max-Cut on interval graphs. To achieve these results, we show the following. 1. For any ε > 0, there is an n^ O(r ε⁻²)-time (1 - ε)-approximation for Boolean Max-2-CSP on graphs of rank-width at most r. 2. There is a polynomial-time algorithm that, for any interval graph $G = (V, E)$ and ε > 0, finds a subgraph $H = (V, F)$ of G such that |F| ≥ (1 - ε) |E| and H has rank-width at most poly(ε⁻¹). Our techniques additionally extend to all bounded-alphabet arity-two max CSPs.
No takes yet. Share an insight, caveat, or question.
DeHaan et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: