A Sublinear Treewidth Exponent for Binary Constraint Satisfaction
We give a deterministic algorithm for binary constraint satisfaction whose exponent in the input size is sublinear in treewidth on a class of graphs with unbounded treewidth. There are a class G of graphs of bounded maximum degree, a constant c, and a function f such that one algorithm correctly decides every binary CSP instance and, on instances I with primal graph G ∈ G, runs in time f(G) · ||I||^(c · tw(G) / sqrt(log tw(G))) . This contradicts the literal formulation of Conjecture 1.4 of Marx (2010). The algorithm follows from a domain-uniform counting bound: for every fixed maximum…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2611.00004
curl -X POST /api/v1/records/hexagon/2611.00004/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00004/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'