Colouring, constraint satisfaction, and complexity

DOI10.1016/J.COSREV.2008.10.003zbMATH Open1302.68251OpenAlexW2199961663WikidataQ56389140 ScholiaQ56389140MaRDI QIDQ458466FDOQ458466

Pavol Hell, J. Nešetřil

Publication date: 7 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2008.10.003

Recommendations

• From graph coloring to constraint satisfaction: there and back again
• \(H\)-coloring dichotomy revisited
• Constraint satisfaction problems: complexity and algorithms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On the complexity of H-coloring

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• A retraction problem in graph theory
• A graph coloring algorithm for large scale scheduling problems
• On colorings of graphs without short cycles
• On sparse graphs with given colorings and homomorphisms.
• Graph products, Fourier analysis and spectral techniques
• Absolute retracts of bipartite graphs
• Hereditarily hard \(H\)-colouring problems
• Dichotomies for classes of homomorphism problems involving unary functions
• Complexity of tree homomorphisms
• A dichotomy for minimum cost graph homomorphisms
• Forbidden lifts (NP and CSP for combinatorialists)
• A dualistic approach to bounding the chromatic number of a graph
• Retractions onto series-parallel posets
• Minimum cost and list homomorphisms to semicomplete digraphs
• Absolute planar retracts and the four colour conjecture
• Finite posets and topological spaces in locally finite varieties
• Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
• Two algorithms for general list matrix partitions
• Many Facets of Dualities
• Absolute Retracts and Varieties of Reflexive Graphs
• Note on projective graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Dinur’s proof of the PCP theorem
• First-order Definable Retraction Problems for Posets and Reflexive Graphs
• A Dichotomy Theorem on Fixed Points of Several Nonexpansive Mappings
• Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
• Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
• Title not available (Why is that?)
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Title not available (Why is that?)
• A graph formulation of a school scheduling algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Acyclic Homomorphisms and Circular Colorings of Digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• Title not available (Why is that?)
• Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
• The PCP theorem by gap amplification
• Products of absolute retracts
• The NP-completeness column: An ongoing guide
• Colorings and homomorphisms of degenerate and bounded degree graphs
• On the complexity of colouring by superdigraphs of bipartite graphs
• List homomorphisms of graphs with bounded degrees
• The effect of two cycles on the complexity of colourings by directed graphs
• Title not available (Why is that?)
• Interval digraphs: An analogue of interval graphs
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decomposition by clique separators
• On the complexity of H-coloring
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Tree-depth, subgraph coloring and homomorphism bounds
• Cuts and bounds
• Complexity classifications of Boolean constraint satisfaction problems
• Proof verification and the hardness of approximation problems
• Expander graphs and their applications
• Varieties with few subalgebras of powers
• On the Structure of Polynomial Time Reducibility
• Title not available (Why is that?)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Title not available (Why is that?)
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The strong perfect graph theorem
• On the algebraic structure of combinatorial problems
• Characterising tractable constraints
• Conjunctive-query containment and constraint satisfaction
• A new tractable class of constraint satisfaction problems
• Independent sets in graph powers are almost contained in juntas
• Projectivity and independent sets in powers of graphs
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Applications of product colouring
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A new line of attack on the dichotomy conjecture
• Generalized Majority-Minority Operations are Tractable
• Tractability and Learnability Arising from Algebras with Few Subpowers
• A Characterisation of First-Order Constraint Satisfaction Problems
• A Simple Algorithm for Mal'tsev Constraints
• Full Constraint Satisfaction Problems
• Dualities for Constraint Satisfaction Problems
• The core of a graph
• Folding
• Closed systems of functions and predicates
• Title not available (Why is that?)
• Title not available (Why is that?)
• Networks of constraints: Fundamental properties and applications to picture processing
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Partitioning chordal graphs into independent sets and cliques
• Nombre chromatique et plus longs chemins d'un graphe
• On sentences which are true of direct unions of algebras
• Chromatically optimal rigid graphs
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• On digraph coloring problems and treewidth duality
• List Partitions
• The Complexity of the Extendibility Problem for Finite Posets
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Title not available (Why is that?)
• \(H\)-coloring dichotomy revisited
• Title not available (Why is that?)
• Title not available (Why is that?)
• Zur algebraischen Begründung der Graphentheorie. I
• Matrix partitions of perfect graphs
• On realizations of point determining graphs, and obstructions to full homomorphisms
• Digraph matrix partitions and trigraph homomorphisms
• Linear time low tree-width partitions and algorithmic consequences
• Mathematical Foundations of Computer Science 2003
• Star-cutsets and perfect graphs
• Efficient characterizations of \(n\)-chromatic absolute retracts
• List homomorphisms and circular arc graphs
• Title not available (Why is that?)
• Absolute reflexive retracts and absolute bipartite retracts
• List homomorphisms to reflexive graphs
• Near-Unanimity Functions and Varieties of Reflexive Graphs
• Bi‐arc graphs and the complexity of list homomorphisms
• Title not available (Why is that?)
• On classes of relations and graphs determined by subobjects and factorobjects
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Title not available (Why is that?)
• Polynomial graph-colorings
• Precoloring extension. I: Interval graphs
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Title not available (Why is that?)
• Computational Complexity of Compaction to Reflexive Cycles
• Title not available (Why is that?)
• Duality and Polynomial Testing of Tree Homomorphisms
• List matrix partitions of chordal graphs
• A polynomial-time algorithm for near-unanimity graphs
• Structural Properties of Sparse Graphs
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Precoloring Extension III: Classes of Perfect Graphs
• The complexity of \(H\)-colouring of bounded degree graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Colouring by Semicomplete Digraphs
• A combinatorial algorithm for MAX CSP

Cited In (35)

• Title not available (Why is that?)
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• In praise of homomorphisms
• Title not available (Why is that?)
• Hybrid Tractable Classes of Constraint Problems
• Graph partitions with prescribed patterns
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Tractability in constraint satisfaction problems: a survey
• Title not available (Why is that?)
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Homogeneous 1‐based structures and interpretability in random structures
• The Complexity of Valued CSPs
• Binary constraint satisfaction problems defined by excluded topological minors
• Title not available (Why is that?)
• The \(C_{k}\)-extended graft construction
• Connected obstructions to full graph homomorphisms
• ON CONSTRAINTS AND DIVIDING IN TERNARY HOMOGENEOUS STRUCTURES
• A tetrachotomy of ontology-mediated queries with a covering axiom
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Dualities in full homomorphisms
• Binary simple homogeneous structures are supersimple with finite rank
• NP-Completeness of Spreading Colored Points
• A new line of attack on the dichotomy conjecture
• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• On planar valued CSPs
• The 1-Color Problem and the Brylawski Model
• Reflexive graphs with near unanimity but no semilattice polymorphisms
• The Parallel Complexity of Coloring Games
• The complexity of grid coloring
• The Power of Linear Programming for General-Valued CSPs
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• Necessary Conditions for Tractability of Valued CSPs
• Obstructions to partitions of chordal graphs
• Backdoor Sets for CSP.
• A Galois Connection for Valued Constraint Languages of Infinite Size

This page was built for publication: Colouring, constraint satisfaction, and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458466)