The complexity of surjective homomorphism problems-a survey

DOI10.1016/j.dam.2012.03.029zbMath1246.05104MaRDI QIDQ444433

Jan Kára, Barnaby Martin, Manuel Bodirsky

Publication date: 14 August 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.03.029

zbMATH Keywords

computational complexity; constraint satisfaction; surjective homomorphisms

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Minimum Violation Vertex Maps and Their Applications to Cut Problems, Constraint Satisfaction with Counting Quantifiers, The Complexity of Counting Surjective Homomorphisms and Compactions, Colouring graphs of bounded diameter in the absence of small cycles, Acyclic, star, and injective colouring: bounding the diameter, Colouring graphs of bounded diameter in the absence of small cycles, Acyclic, star, and injective colouring: bounding the diameter, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, Complexity of \(C_k\)-coloring in hereditary classes of graphs, Constraint satisfaction problem: what makes the problem easy, 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs, A note on rainbow-free colorings of uniform hypergraphs, Algorithms and almost tight results for 3-colorability of small diameter graphs, An algebraic hardness criterion for surjective constraint satisfaction., Tractability conditions for numeric CSPs, Computing vertex-surjective homomorphisms to partially reflexive trees, Finding vertex-surjective graph homomorphisms, Coloring problems on bipartite graphs of small diameter, Obtaining online ecological colourings by generalizing first-fit, Independent feedback vertex sets for graphs of bounded diameter, On rainbow-free colourings of uniform hypergraphs, Surjective \(H\)-colouring: new hardness results, Partitioning \(H\)-free graphs of bounded diameter, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Disconnected cuts in claw-free graphs, Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Graph partitions with prescribed patterns, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The external constraint 4 nonempty part sandwich problem
• Computational complexity of compaction to irreflexive cycles
• Computing role assignments of chordal graphs
• A complete complexity classification of the role assignment problem
• \(2K_{2}\) vertex-set partition into nonempty parts
• Covering graphs with few complete bipartite subgraphs
• List homomorphisms to reflexive graphs
• On the algebraic structure of combinatorial problems
• List homomorphisms and circular arc graphs
• On disconnected cuts and separators
• Tractable cases of the extended global cardinality constraint
• Coloring mixed hypertrees
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Finding Vertex-Surjective Graph Homomorphisms
• Complexity of conservative constraint satisfaction problems
• Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
• The complexity of global cardinality constraints
• Retractions to Pseudoforests
• Algorithms for Partition of Some Class of Graphs under Compaction
• The Complexity of Rooted Phylogeny Problems
• The Complexity of the List Partition Problem for Graphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Undirected connectivity in log-space
• Parameterizing Cut Sets in a Graph by the Number of Their Components
• The Complexity of Colouring by Semicomplete Digraphs
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On generating all solutions of generalized satisfiability problems
• List Partitions
• Compaction, Retraction, and Constraint Satisfaction
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Bi‐arc graphs and the complexity of list homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The Approximability of Three-valued MAX CSP