The complexity of surjective homomorphism problems-a survey

DOI10.1016/J.DAM.2012.03.029zbMATH Open1246.05104OpenAlexW1998601876MaRDI QIDQ444433FDOQ444433

Authors Manuel Bodirsky, Jan Kára, Barnaby Martin 

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 complexityconstraint satisfactionsurjective homomorphisms

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of counting surjective homomorphisms and compactions
• Surjective \(H\)-colouring: new hardness results
• Finding vertex-surjective graph homomorphisms
• Surjective \(H\)-colouring: new hardness results
• Finding vertex-surjective graph homomorphisms

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• A complete complexity classification of the role assignment problem
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Algorithms for partition of some class of graphs under compaction
• Bi‐arc graphs and the complexity of list homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras
• Coloring mixed hypertrees
• Compaction, Retraction, and Constraint Satisfaction
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• Computational Complexity of Compaction to Reflexive Cycles
• Computational complexity of compaction to irreflexive cycles
• Computing role assignments of chordal graphs
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Covering graphs with few complete bipartite subgraphs
• Finding vertex-surjective graph homomorphisms
• FindingH-partitions efficiently
• List Partitions
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• On disconnected cuts and separators
• On generating all solutions of generalized satisfiability problems
• On the Structure of Polynomial Time Reducibility
• On the algebraic structure of combinatorial problems
• Parameterizing cut sets in a graph by the number of their components
• Retractions to Pseudoforests
• The Approximability of Three-valued MAX CSP
• The Complexity of Colouring by Semicomplete Digraphs
• The Complexity of Rooted Phylogeny Problems
• The Complexity of the List Partition Problem for Graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of global cardinality constraints
• The complexity of satisfiability problems
• The external constraint 4 nonempty part sandwich problem
• The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem
• Tractable cases of the extended global cardinality constraint
• Undirected connectivity in log-space
• \(2K_{2}\) vertex-set partition into nonempty parts

Cited in

(37)

• Minimum violation vertex maps and their applications to cut problems
• A note on rainbow-free colorings of uniform hypergraphs
• Independent feedback vertex sets for graphs of bounded diameter
• Constraint satisfaction with counting quantifiers
• Coloring problems on bipartite graphs of small diameter
• Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
• The data complexity of ontology-mediated queries with closed predicates
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• Algebraic global gadgetry for surjective constraint satisfaction
• Acyclic, star, and injective colouring: bounding the diameter
• Graph partitions with prescribed patterns
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Surjective \texttt{H}-colouring over reflexive digraphs
• Disconnected cuts in claw-free graphs
• Disconnected cuts in claw-free graphs
• On rainbow-free colourings of uniform hypergraphs
• Tractability conditions for numeric CSPs
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• Colouring graphs of bounded diameter in the absence of small cycles
• Colouring graphs of bounded diameter in the absence of small cycles
• The complexity of counting surjective homomorphisms and compactions
• scientific article; zbMATH DE number 7525468 (Why is no real title available?)
• The complexity of counting surjective homomorphisms and compactions
• Finding vertex-surjective graph homomorphisms
• Obtaining online ecological colourings by generalizing first-fit
• 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• scientific article; zbMATH DE number 4162940 (Why is no real title available?)
• Generalisations of matrix partitions: complexity and obstructions
• An algebraic hardness criterion for surjective constraint satisfaction.
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Surjective \(H\)-colouring: new hardness results
• Acyclic, star, and injective colouring: bounding the diameter
• Constraint satisfaction problem: what makes the problem easy
• Partitioning \(H\)-free graphs of bounded diameter
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• Beyond Boolean surjective VCSPs

This page was built for publication: The complexity of surjective homomorphism problems-a survey

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