The complexity of surjective homomorphism problems-a survey
From MaRDI portal
Publication:444433
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Tractable cases of the extended global cardinality constraint
- Complexity classifications of Boolean constraint satisfaction problems
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Undirected connectivity in log-space
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- On the algebraic structure of combinatorial problems
- Complexity of conservative constraint satisfaction problems
- Title not available (Why is that?)
- On generating all solutions of generalized satisfiability problems
- Computing role assignments of chordal graphs
- A complete complexity classification of the role assignment problem
- The Complexity of the List Partition Problem for Graphs
- Title not available (Why is that?)
- List Partitions
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Algorithms for partition of some class of graphs under compaction
- Compaction, Retraction, and Constraint Satisfaction
- FindingH-partitions efficiently
- Computational Complexity of Compaction to Reflexive Cycles
- Computational complexity of compaction to irreflexive cycles
- Covering graphs with few complete bipartite subgraphs
- The Approximability of Three-valued MAX CSP
- On disconnected cuts and separators
- Coloring mixed hypertrees
- Finding Vertex-Surjective Graph Homomorphisms
- Computing vertex-surjective homomorphisms to partially reflexive trees
- The complexity of global cardinality constraints
- Retractions to Pseudoforests
- The Complexity of Rooted Phylogeny Problems
- Parameterizing cut sets in a graph by the number of their components
- The Complexity of Colouring by Semicomplete Digraphs
- The external constraint 4 nonempty part sandwich problem
- \(2K_{2}\) vertex-set partition into nonempty parts
Cited In (36)
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Title not available (Why is that?)
- Disconnected cuts in claw-free graphs
- Tractability conditions for numeric CSPs
- 3-coloring \(C_4\) or \(C_3\)-free diameter two graphs
- Algorithms and almost tight results for 3-colorability of small diameter graphs
- Coloring problems on bipartite graphs of small diameter
- Graph partitions with prescribed patterns
- The Complexity of Counting Surjective Homomorphisms and Compactions
- Generalisations of matrix partitions: complexity and obstructions
- Title not available (Why is that?)
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Acyclic, star, and injective colouring: bounding the diameter
- Algebraic global gadgetry for surjective constraint satisfaction
- Surjective \(H\)-colouring: new hardness results
- Finding vertex-surjective graph homomorphisms
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- Independent feedback vertex sets for graphs of bounded diameter
- Acyclic, star, and injective colouring: bounding the diameter
- Minimum Violation Vertex Maps and Their Applications to Cut Problems
- A note on rainbow-free colorings of uniform hypergraphs
- Constraint Satisfaction with Counting Quantifiers
- Colouring graphs of bounded diameter in the absence of small cycles
- Colouring graphs of bounded diameter in the absence of small cycles
- Title not available (Why is that?)
- Title not available (Why is that?)
- Partitioning \(H\)-free graphs of bounded diameter
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- Obtaining online ecological colourings by generalizing first-fit
- Title not available (Why is that?)
- An algebraic hardness criterion for surjective constraint satisfaction.
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Constraint satisfaction problem: what makes the problem easy
- On rainbow-free colourings of uniform hypergraphs
- Title not available (Why is that?)
- Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
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)
