PaperlayerView exact revision on arXiv

Source-linked AI summary

Algebraic approach to promise constraint satisfaction

Libor Barto, Jakub Bulín, Andrei Krokhin, Jakub Opršal

arXiv:1811.00970v3cs.CCcs.LOmath.LO

TL;DR

The paper addresses the largely open complexity classification of promise CSPs, including approximate graph colouring. It develops an abstract algebraic theory based on minor conditions and algebraic Label Cover, showing that every fixed-template PCSP has this form. The theory yields NP-hardness of distinguishing k-colourable graphs from those not (2k−1)-colourable for every k ≥ 3.

  • Problem

    The complexity classification of fixed-language PCSPs remains largely open, including important approximate graph-colouring cases.

  • Method

    The paper develops a theory using bipartite minor conditions and shows every PCSP is equivalent to an algebraic version of Gap Label Cover.

  • Results

    For every k ≥ 3, distinguishing k-colourable graphs from graphs not even (2k −1)-colourable is NP-hard.

  • Takeaways & Limitations

    Minor conditions provide an abstract measure of symmetry that determines PCSP complexity and supports comparisons between different PCSPs.

  • Takeaways & Limitations

    The absence of an Olšák polymorphism is sufficient for hardness but is not a universal hardness criterion for PCSPs.

Abstract

from arXiv · show

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms --- high-dimensional symmetries of solution spaces --- to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this paper we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem, and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a "measure of symmetry" that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by improving the state-of-the-art in approximate graph colouring: we show that, for any $k\geq 3$, it is NP-hard to find a $(2k-1)$-colouring of a given $k$-colourable graph.

1. INTRODUCTION

PCSPs extend CSPs to promise settings whose complexity classification remains largely open, including approximate graph colouring. The paper develops an abstract algebraic theory based on minor conditions and applies it to hardness and tractability questions.

  • Motivation: PCSPs generalize CSPs to promise settings motivated by open approximability questions for satisfiability and graph colouring.Unlike the largely classified fixed-language finite-domain CSPs, PCSP complexity remains limited in understanding.
  • Abstract algebraic theory: The paper replaces concrete polymorphism properties with systems of minor identities that fully determine PCSP complexity.These identities provide an abstract measure of problem symmetry for comparing PCSPs.
  • Abstract algebraic theory: Bipartite minor conditions yield log-space reductions between PCSPs and characterize when one problem’s polymorphism conditions imply another’s.Every PCSP is also log-space equivalent to deciding whether a bipartite minor condition is satisfied by projections or by its polymorphisms.
  • Abstract algebraic theory: Every PCSP is equivalent to an algebraic version of Gap Label Cover based on satisfiability of systems of minor identities.This framework supports general approaches to proving NP-hardness and relates PCSP complexity across different templates.
  • Applications: The theory characterizes tractability conditions through minor identities and shows that some PCSP tractability reductions necessarily use infinite-domain CSPs.A specific PCSP is not a subproblem of any tractable finite-domain CSP despite being a subproblem of tractable infinite-domain CSPs.

2. PRELIMINARIES

This section formalises CSPs and PCSPs through relational structures, homomorphisms, and templates, then gives representative promise problems. It also states an algebraic definability theorem connecting polymorphisms, reductions, and PCSP complexity.

  • Structures and constraint languages: A constraint language is a finite set of relations on a domain, while a relational structure specifies relations of fixed arities over its domain.The paper assumes structures are finite unless specified otherwise and uses [n] and E_n for standard indexing.
  • Homomorphisms and CSPs: A homomorphism maps one relational structure to another while preserving every relation, and CSP(B) asks whether an input structure maps to the fixed template B.For graph inputs and a clique template K_k, this is exactly the standard k-colouring problem.
  • Promise CSPs: A PCSP template is a pair A → B, where the problem accepts inputs mapping to A and rejects inputs that do not map to B.The promise A → B ensures that the yes- and no-cases are disjoint; PCSP(A,A) recovers CSP(A).
  • Promise CSPs: The search version receives an input mapping to A and must find a homomorphism to B, but equivalence between decision and search remains open for general PCSP templates.The paper's results are proved for decision problems and stated to generalise to corresponding search problems.
  • Examples: The section also presents promise variants of satisfiability and hypergraph colouring, including (2+ε)-Sat, 1-in-3 versus Not-All-Equal-Sat, and several colouring problems.For example, (2+ε)-Sat asks for a normal satisfying assignment when each clause is promised to have an assignment satisfying at least k literals.
  • Examples: Approximate graph colouring is PCSP(K_k,K_c): given a k-colourable graph, the task is to find a c-colouring.Before this paper, unconditional NP-hardness was known for k versus (2k−2) colours; the paper settles k versus 2k−1 hardness for every k ≥ 3.
  • Algebraic framework: For PCSP templates over the same finite domains, ppp-definability is equivalent to inclusion of polymorphism sets and implies a polynomial-time reduction between the corresponding PCSPs.The equivalence is stated as (A′,B′) ppp-definable in (A,B) exactly when Pol(A,B) ⊆ Pol(A′,B′).

3. ALGEBRAIC REDUCTIONS

The section develops reductions between PCSPs and bipartite minor conditions, showing how polymorphism identities capture PCSP complexity and connect to Label Cover. It also establishes reductions in both directions and applies the framework to hardness for approximate graph colouring.

  • Reductions and minor conditions: Minion homomorphisms and bipartite minor conditions provide the central algebraic framework for reducing PCSPs to one another.The section introduces bipartite minor conditions as finite systems of minor identities over disjoint function-symbol sets.
  • Reductions and minor conditions: A bipartite minor condition assigns polymorphisms to abstract symbols so that every identity holds on all domain inputs.Triviality means satisfaction by projections, equivalently by every minion under the stated conditions.
  • Hardness application: For every k ≥ 3, a specific minor condition is absent from Pol(K_k, K_{2k−1}), yielding NP-hardness of PCSP(K_k, K_{2k−1}).This establishes that finding a (2k−1)-colouring of a k-colourable graph is NP-hard.
  • Connection to Label Cover: Bipartite minor conditions are closely related to Label Cover: labels correspond to projections, while constraints become minor identities.The construction extends satisfaction beyond projections to arbitrary functions, avoiding some combinatorial difficulties of Long-code formulations.
  • Reductions and minor conditions: Every PCSP can be reduced in log-space to deciding whether a bounded-arity bipartite minor condition is trivial, and the reduction also works in the reverse direction.The reverse reduction maps minor-condition instances back to the corresponding PCSP template.

4. RELATIONAL CONSTRUCTIONS

The section characterises algebraic reductions between PCSPs through minion homomorphisms, free structures, and relational constructions. These equivalent views provide both structural understanding and hardness-transfer tools.

  • Minion homomorphisms: A minion homomorphism from Pol(A1, B1) to Pol(A2, B2) yields a log-space reduction from PCSP(A2, B2) to PCSP(A1, B1).Thus an NP-hard target PCSP transfers hardness to any template admitting the corresponding minion homomorphism.
  • Free structures: Free structures encode n-ary functions of a minion as elements and define relations through polymorphism identities.For a finite structure A on [n], the universe of FM(A) is M(n), with relations determined by functions witnessing the required identities.
  • Free structures: There is a 1-to-1 correspondence between homomorphisms from FM(A) to B and minion homomorphisms from M to Pol(A, B).This connects relational homomorphisms with algebraic maps between polymorphism minions.
  • Relational constructions: Relaxations and pp-powers each induce minion homomorphisms, and combining these constructions preserves log-space reductions between the corresponding PCSPs.These constructions generalise familiar relational operations from CSP theory to promise templates.
  • Equivalent characterisations: The existence of a minion homomorphism is equivalent to several conditions, including shared bipartite minor identities, a free-structure homomorphism, and pp-constructibility.Theorem 4.12 also characterises it through homomorphic relaxation of a pp-power.

5. HARDNESS FROM THE PCP THEOREM

The paper derives PCSP hardness through algebraic versions of Label Cover, using minor conditions satisfied by polymorphisms to connect PCP-based gaps to reductions. This framework yields general NP-hardness criteria, including for approximate graph and hypergraph colouring.

  • Reduction framework: PCP-based inapproximability proofs commonly reduce through Label Cover, which the paper interprets algebraically as systems of minor identities.The reduction proceeds from MC, essentially Label Cover, to PCSPs via polymorphism analysis.
  • Reduction framework: MC(N) is NP-hard for each N ≥3, established by reducing from 1-in-3-Sat because the template’s polymorphisms are projections.The reduction uses the fact that the 1-in-3-Sat template has domain size 2 and a ternary relation with 3 tuples.
  • Hardness criteria: If Pol(A, B) satisfies no non-trivial bipartite minor condition of arity at most three, then PCSP(A, B) is NP-hard.The criterion follows by aligning MC(N) hardness with the polymorphism conditions required for the reduction.
  • Hardness criteria: For suitable constants K1,K2, absence of ε-robust conditions up to arity N implies NP-hardness whenever N ≥ K1ε^-K2.This criterion combines a PCP-derived Label Cover hardness theorem with the algebraic reduction.
  • Hardness criteria: If Pol(A, B) satisfies no ε-robust bipartite minor condition, then PCSP(A, B) is NP-hard.The robust condition extends the hardness framework beyond a fixed small arity.
  • Applications: The framework also yields NP-hardness for multilayered Label Cover reductions and includes PCSP(H2, Hk) for every k ≥2.The multilayered result uses a transformation to a polymorphism-based problem before reducing to the PCSP.

6. HARDNESS FROM OTHER PCSPS

The section derives hardness results for PCSPs by reducing from approximate hypergraph colouring through bipartite minor conditions, then applies the framework to graph colouring and homomorphism problems.

  • Hardness from approximate hypergraph colouring: The absence of an Olšák function is equivalent to admitting a minion homomorphism to a hypergraph-colouring polymorphism minion.This equivalence supplies the algebraic criterion used for the reductions.
  • Hardness from approximate hypergraph colouring: Every finite template without an Olšák polymorphism defines an NP-hard PCSP.The proof combines the minion-homomorphism characterization with the hardness of approximate hypergraph colouring.
  • Hardness of approximate graph colouring and homomorphism: The proof constructs a graph G containing a 2k-clique by gluing triples of vertices in the sixth power of K_k.For k = 3, the resulting construction contains a 6-clique.
  • Hardness of approximate graph colouring and homomorphism: For every k ≥ 3, distinguishing k-colourable graphs from graphs not even (2k −1)-colourable is NP-hard.In particular, colouring a 3-colourable graph with 5 colours is NP-hard, improving earlier bounds for small k.
  • Hardness of approximate graph colouring and homomorphism: PCSP(C5, K3) is NP-hard because its polymorphisms do not contain an Olšák function.This establishes hardness for distinguishing graphs mapping to C5 from graphs that are not 3-colourable.
  • Implications of hardness of approximate graph colouring: The framework also gives broader hardness consequences for odd cycles, non-bipartite graph homomorphisms, and templates failing suitable loop conditions.It further characterizes when universal hardness without Siggers polymorphisms is equivalent to hardness of all approximate graph-colouring cases.

7. TRACTABILITY FROM SOME CSPS

The section characterizes tractability through polymorphism identities and minion homomorphisms for several algorithms, including local consistency, basic linear programming, and affine integer relaxation.

  • General framework: PCSP tractability conditions generally require infinite sets of bipartite minor identities, beyond a single nontrivial condition.The sole excluded trivial case is a condition implying a constant operation.
  • General framework: The paper characterizes known algorithms rather than providing new concrete tractability results.The characterizations describe when algorithms based on local consistency or relaxations apply to PCSPs.
  • Local consistency: Width 1 is equivalent to totally symmetric polymorphisms of all arities, a minion homomorphism from Horn 3-SAT, and pp-constructibility from its template.Width 1 corresponds to solvability by generalized arc consistency.
  • Local consistency: Bounded width is preserved under minion homomorphisms between PCSP templates.This preservation is established through homomorphic relaxations and pp-powers.
  • Linear programming relaxations: BLP solves a PCSP exactly when its polymorphisms contain symmetric functions of all arities, equivalently admitting the corresponding minion homomorphism and pp-construction.The characterization is stated for the basic linear programming relaxation.
  • Affine integer relaxation: AIP solves a PCSP exactly when its polymorphisms contain alternating functions of all odd arities, with equivalent minion-homomorphism and pp-constructibility formulations.This provides the analogous algebraic characterization for affine integer relaxation.

8. MORE ON TRACTABILITY OF 1-IN-3- VS. NAE-SAT

This section proves that tractable 1-in-3-versus-NAE-SAT cannot arise from a finite tractable CSP template, using cyclic polymorphisms and matrix-based arguments. The proof establishes tameness for increasingly structured matrices and derives a contradiction from two tame matrices with different areas.

  • Setup: The template (T, H2) is tractable but cannot be pp-constructed from any finite template D whose CSP is tractable.If (T, H2) were pp-constructible from finite D, then CSP(D) would be NP-complete.
  • Setup: Assuming CSP(D) is not NP-complete yields cyclic polymorphisms of every prime arity p > |D|.The proof fixes a cyclic polymorphism s of prime arity p > 60|D| and builds a p^2-ary operation t by composing copies of s.
  • Matrix framework: The operation t evaluates a p × p matrix by applying s to its columns and then to the resulting row.The proof restricts attention to zero-one matrices and compares them through their images under the homomorphism д.
  • Almost rectangles: Every almost rectangle is tame, including the two matrices X1 and X2 used in the final contradiction.The construction gives λ(X1) < 1/3, λ(X2) > 1/3, and t(X1) = t(X2), contradicting the non-equivalence of the all-zero and all-one matrices.
  • Matrix framework: A cover of three zero-one matrices cannot have all three matrices д-equivalent, because t preserves the ternary relation and д maps it to a not-all-equal relation.This supplies the key non-equivalence constraint used throughout the matrix argument.
  • Tameness: Every tuple ⟨i⟩ is tame, while ⟨0⟩ and ⟨p^2⟩ are not д-equivalent.The proof uses cyclicity and p^2 = 3q + 1 to establish the required equivalence pattern among these tuples.

9. ALGEBRAIC CONSTRUCTIONS

This section translates relational constructions of PCSP templates into operations on polymorphism minions. It shows that pp-constructibility is equivalent to membership under finite powers and reflections, and also to the existence of a minion homomorphism.

  • Framework: The theory focuses on finite-domain minions as an algebraic generalisation of the clone-based approach to PCSPs.The section develops the connection between minion operations and pp-constructions.
  • Framework: A template transformation corresponds to expansion, finite power, or reflection of its polymorphism minion.These minion operations provide algebraic counterparts to the relational constructions used earlier.
  • Relational-algebraic correspondence: A template is ppp-definable, a strict relaxation of a pp-power, or a relaxation of a pp-definable structure exactly when its minion satisfies the corresponding expansion, finite-power, or reflection relation.Lemma 9.2 establishes these three correspondences.
  • Minion homomorphisms: Two minions satisfy M′ ∈ ERPfin M exactly when there is a minion homomorphism from M to M′.The proof constructs suitable powers and reflections from a minion homomorphism.
  • Main equivalence: For templates, pp-constructibility, membership M′ ∈ ERPfin M, and a minion homomorphism M → M′ are equivalent.Consequently, pp-constructibility yields a log-space reduction between the associated PCSPs.

10. BIPARTITE MINOR CONDITIONS SATISFIED IN Pol(Kk, Kc)

This section uses bipartite minor conditions to compare promise graph-colouring problems. It recovers hardness below 2k colours, analyzes the threshold 2k−1, and proves further separations among colouring templates.

  • Framework: Bipartite minor conditions provide the main tool for comparing the polymorphism minions of graph-colouring templates.The approach distinguishes PCSPs even when their polymorphisms satisfy nontrivial conditions.
  • Hardness threshold: For c ≤ 2k−2, PCSP(Kk, Kc) is hard because its polymorphism minion maps to the projection minion P2.Thus all bipartite minor conditions satisfied in these templates are trivial.
  • Threshold behaviour: Pol(Kk, K2k) contains an Olšák function, showing that nontrivial minor conditions persist at the 2k-colour threshold.The paper constructs an explicit operation from Kk to K2k with this property.
  • Threshold behaviour: For any ε > 0, Pol(Kk, K2k) satisfies an ε-robust bipartite minor condition.The construction uses iterated ternary majority operations and a family of Boolean inputs.
  • Separations: For every k ≥ 3, some c ≥ k prevents a minion homomorphism from Pol(Kk, Kc) to any Pol(Kk′, Kc′) with k < k′ ≤ c′.For k = 3, the paper records the sharper result that Pol(K3, K6) has no such homomorphism.
  • Separations: For any c ≥ k > 2, some C > c prevents a minion homomorphism from Pol(Kk, KC) to Pol(Kk, Kc).This gives separations even when the source and target have the same lower colour parameter k.

11. CONCLUSION

The paper presents bipartite minor conditions as an algebraic framework for PCSP complexity and applies it to approximate graph colouring. It concludes that major classification and algorithmic questions remain open, including finite-template and infinite-domain issues.

  • Contributions: Bipartite minor conditions in Pol(A, B) determine the complexity of PCSP(A, B) within the paper’s general theory.The theory is presented as an abstract algebraic account of PCSPs with fixed templates.
  • Open problems: The PCSP complexity landscape remains largely unknown, including Boolean PCSPs and graph homomorphism special cases.The paper identifies these classifications as important open problems.
  • Open problems: Hardness sources in PCSP appear more varied than in CSP, and further restrictions on bipartite minor conditions are needed to explain NP-hardness.The paper notes that current hardness arguments use variants of Gap Label Cover and may require new reductions.
  • Algorithms and domains: For PCSP(T, H2), no finite structure D exists with T → D → H2 and tractable CSP(D), although infinite-domain examples exist.The paper gives D = (Z; x + y + z = 1) as one infinite example.
  • Algorithms and domains: It is unclear how to transfer the “few subpowers” algorithm to PCSPs, so tractable PCSPs may require a different algorithmic approach.The paper also calls for continued characterization of the power of individual PCSP algorithms.
Loading 1811.00970v3…