Pith. Sign in

REVIEW

The approximability of MAX CSP with fixed-value constraints

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Vladimir Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin

Computational Complexity · Submitted 21 Feb 2006 · 41 references

Pith's verdict: Strong dichotomy result for Max CSP with fixed values; the proof is explicit but the |D|=4 Case 3 rests on an unshipped exhaustive search, so it needs one more verification pass.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 3 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv IDcs/0602075 (version 1)
Pith IDXFVU7KJX, Pith's permanent record of this paper and its review
CitationAndrei Krokhin, Mikael Klasson, Peter Jonsson, Vladimir Deineko. "The approximability of MAX CSP with fixed-value constraints." arXiv:cs/0602075 (2006). https://pith.science/paper/XFVU7KJX
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

For maximum constraint satisfaction problems with fixed-value constraints, supermodularity on some chain exactly separates polynomial-time solvable from APX-complete cases.

The reading

This paper aims to settle the approximability of maximum constraint satisfaction problems (Max CSP) in which the allowed constraints include every fixed-value predicate of the form x=a. The central claim is a strict dichotomy: for any finite set F of predicates on a finite domain D, the problem Max CSP(F ∪ C_D) is either solvable exactly in polynomial time (for the weighted version) or is APX-complete, meaning it has no polynomial-time approximation scheme unless P=NP. The dividing line is supermodularity: tractability holds exactly when all predicates in F are supermodular with respect to some linear ordering (chain) on D. The hardness side is shown to persist even when each variable occurs in only a bounded number of constraints, and the polynomial-time boundary can be recognised in polynomial time.

What carries the argument

The central object is supermodularity on a chain: a predicate f is supermodular if f(a)+f(b) ≤ f(min(a,b))+f(max(a,b)) holds componentwise, which for binary predicates is equivalent to the matrix of f being anti-Monge. Two reduction techniques carry the argument: strict implementations, which replace a constraint by a small gadget of constraints over auxiliary variables while preserving the approximation ratio up to an additive constant; and domain restriction, which forces variables into a sub-domain when a unary predicate is available. The proof also hinges on a combinatorial lemma (Proposition 5.3) showing that if a set of binary predicates is not simultaneously supermodular on any chain, then a sub-domain of at most four elements and a sub-collection of at most three predicates already witness this failure; this reduces the classification to a finite, computer-checkable case analysis on the four-element domain.

Extended reading notes

Core claim

The paper proves a dichotomy theorem (Theorem 5.4): if a finite set F of predicates over a finite domain D is supermodular on some chain of D, then weighted Max CSP(F ∪ C_D) is in PO; otherwise, Max CSP(F ∪ C_D) − B (the bounded-occurrence version) is APX-complete. The tractable direction is inherited from known supermodularity results. For the hard direction, the paper shows that any non-supermodular F can be transformed, through strict implementations and domain restrictions, into a set that expresses the disequality predicate neq_2 on a two-element domain, thereby simulating Max Cut, which is APX-complete on cubic graphs. The proof reduces the infinite family of possible F to a finite case analysis: by a matrix-theoretic result, a witness to non-supermodularity can be found among at most three binary predicates on a sub-domain of size at most four; the remaining cases are disposed of by an exhaustive computer search that lists all minimal obstructions and supplies explicit strict implementations for each.

Load-bearing premise

The load-bearing premise is that the computer-generated case analysis is correct: specifically, that it enumerates every minimal non-supermodular set of binary predicates on a four-element domain and correctly establishes that no such set of size three exists.

Editorial extensions

If this is right

  • Every problem of the form Max CSP(F ∪ C_D) is either in PO or APX-complete, with no intermediate approximability classes.
  • APX-completeness holds even for instances where each variable occurs only a bounded number of times, so the hardness is not an artefact of large scopes.
  • For any fixed domain D, the tractable cases can be recognised in polynomial time by testing whether F is supermodular on some chain.
  • For digraph list H-colouring optimisation, the tractable digraphs are exactly those whose adjacency matrix is anti-Monge under some ordering of the vertices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same dichotomy might hold for wider families of conservative constraint sets (e.g., F ∪ U_D with all unary predicates) on arbitrary finite domains, but the paper only establishes it when all fixed-value constraints are present.
  • The matrix-theoretic reduction (bad submatrix of size at most 4) suggests a polynomial-time recognition algorithm for simultaneous anti-Monge permutability of a constant-size family of matrices, which could be of independent combinatorial interest.
  • An independent reimplementation of the exhaustive search for the |F|=3 nonexistence claim would provide a strong check on the proof; the authors note they also have a lengthy combinatorial proof, which is not included.
  • The dichotomy's reliance on supermodularity suggests that submodular/supermodular optimisation algorithms are the only source of exact tractability in this class, reinforcing a pattern observed for three-element domains.
Original abstract

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this paper, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form x=a), is either solvable exactly in polynomial-time or else is APX-complete, even if the number of occurrences of variables in instances are bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,399 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.25 · human participants 0.01 · controlled comparison 0.01 · randomized assignment 0.01 · states quantitative result 0.10 · compares with prior results 0.10 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this paper, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form x=a), is either solvable exactly in polynomial-time or else is APX-complete, even if the number of occurrences of variables in instances are bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. background 1.00 0.04 0.02 asserted 0.98
s1 This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. background 1.00 0.04 0.02 asserted 1.00
s2 In this paper, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form x=a), is either solvable exactly in polynomial-time or else is APX-complete, even if the number of occurrences of variables in instances are bounded. result 0.87 0.96 0.95 asserted 1.00
s3 Moreover, we present a simple description of all polynomial-time solvable cases of our problem. contribution 0.84 0.96 0.06 asserted 1.00
s4 This description relies on the well-known algebraic combinatorial property of supermodularity. method 0.90 0.50 0.03 asserted 0.99

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. A list of predicates on {0, 1, 2, 3} which are supermodular on the chain 0 < 1 < 2 < 3. The predicates are represented by tables of values. A square matrix M is called anti-Monge (or a-Monge, for short)2 if M(i, s) + M(r, j) ≤ M(i, j) + M(r, s) for all i < r and j < s. It is well known (and easy to check) that matrices 2Other names used for such matrices are inverse Monge and dual Monge. 10
Figure 2. The optimized list of 27 predicates from the proof o
Figure 3. Schematic representation of submatrices and alge

Figures reproduced from arXiv:cs/0602075 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.