Full Constraint Satisfaction Problems

DOI10.1137/S0097539703427197zbMath1111.68115OpenAlexW1989984435MaRDI QIDQ5470753

Tomás Feder, Pavol Hell

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703427197

zbMATH Keywords

NP-complete problemsgraph homomorphismsbounded degreeslist homomorphismsmatrix partitionsdichotomy conjecturequasi-polynomial algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

Tractability in constraint satisfaction problems: a survey ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Obstructions to partitions of chordal graphs ⋮ Counting List Matrix Partitions of Graphs ⋮ Adaptable and conflict colouring multigraphs with no cycles of length three or four ⋮ Clique versus independent set ⋮ On the adaptable chromatic number of graphs ⋮ Matrix partitions of perfect graphs ⋮ The adaptable choosability number grows with the choosability number ⋮ Colouring, constraint satisfaction, and complexity ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ An asymptotically tight bound on the adaptable chromatic number ⋮ The complexity of tropical graph homomorphisms ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Rainbow graph splitting ⋮ Graph partitions with prescribed patterns ⋮ An upper bound on adaptable choosability of graphs ⋮ Connected obstructions to full graph homomorphisms ⋮ Adapted list coloring of planar graphs ⋮ Adaptable chromatic number of graph products ⋮ Matrix Partitions with Finitely Many Obstructions ⋮ List matrix partitions of chordal graphs

This page was built for publication: Full Constraint Satisfaction Problems