The complexity of surjective homomorphism problems—a survey

Manuel Bodirsky, Jan Kára, Barnaby Martin

Type: Article

Publication Date: 2012-04-20

Citations: 65

DOI: https://doi.org/10.1016/j.dam.2012.03.029

View Publication

Locations

Discrete Applied Mathematics - View
arXiv (Cornell University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View

Similar Works

Action	Title	Year	Authors
+	The complexity of locally injective homomorphisms	2010	Gary MacGillivray Jacobus Swarts
+	The Complexity of Surjective Homomorphism Problems -- a Survey	2011	Manuel Bodirsky Jan Kára Barnaby Martin
+	Complexity of homomorphisms to direct products of graphs	2002	Judit Büki Csaba Szabó
+ PDF Chat	The Complexity of the List Homomorphism Problem for Graphs	2011	László Egri Andrei Krokhin Benoît Larose Pascal Tesson
+ PDF Chat	The complexity of homomorphism factorization	2021	Kevin M. Berg
+ PDF Chat	On the Complexity of Matroid Isomorphism Problem	2010	B. V. Raghavendra Rao M. N. Jayalal Sarma
+	Enumerating homomorphisms	2011	Andreǐ A. Bulatov Víctor Dalmau Martin Grohe Dániel Marx
+	The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzażewski Conjecture	2024	Ambroise Baril Miguel Couceiro Victor Lagerkvist
+ PDF Chat	The complexity of tropical graph homomorphisms	2017	Florent Foucaud Ararat Harutyunyan Pavol Hell Sylvain Legay Yannis Manoussakis Reza Naserasr
+	Computational Aspects of the Isomorphism Problem	1999	Frauke M. Bleher Wolfgang Kimmerle Klaus W. Roggenkamp Martin Wursthor
+	Complexity Dichotomies for Counting Graph Homomorphisms	2015	Jin‐Yi Cai Xi Chen Pinyan Lu
+	Complexity Dichotomies for Counting Graph Homomorphisms	2016	Jin‐Yi Cai Xi Chen Pinyan Lu
+	The complexity of counting graph homomorphisms (extended abstract)	2000	Martin Dyer Catherine Greenhill
+	The isomorphism problem for group rings: A survey	1985	Robert Sandling
+	The Complexity of some exact and approximate isomorphism problems[HBNI Th80]	2014	Yadu Vasudev
+ PDF Chat	Complexity Classification of Counting Graph Homomorphisms Modulo a Prime Number	2024	Andreǐ A. Bulatov Amirhossein Kazeminia
+	Complexity of Bilinear Problems	2009	Markus Bläser
+	Complexity problems in enumerative combinatorics	2018	Igor Pak
+	#P-complete problems and linear representations (Representation theory and related combinatorics)	2016	伯元松木
+	Enumerative combinatorics of maps	2017	Mireille Bousquet‐Mélou

Works That Cite This (52)

Action	Title	Year	Authors
+ PDF Chat	Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs	2020	Gregor Matl Stanislav Živný
+ PDF Chat	Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs	2013	George B. Mertzios Paul G. Spirakis
+ PDF Chat	Algorithms and Almost Tight Results for $$3$$ 3 -Colorability of Small Diameter Graphs	2014	George B. Mertzios Paul G. Spirakis
+	Beyond Boolean Surjective VCSPs	2019	Gregor Matl Stanislav Živný
+ PDF Chat	Complexity of C-coloring in hereditary classes of graphs	2023	Maria Chudnovsky Shenwei Huang Paweł Rzążewski Sophie Spirkl Mingxian Zhong
+	A note on rainbow-free colorings of uniform hypergraphs	2023	Ran Gu Hui Lei Yongtang Shi Yiqiao Wang
+ PDF Chat	Finding vertex-surjective graph homomorphisms	2012	Petr A. Golovach Bernard Lidický Barnaby Martin Daniël Paulusma
+ PDF Chat	Generalisations of matrix partitions: Complexity and obstructions	2024	Alexey Barsukov Mamadou Moustapha Kanté
+ PDF Chat	Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter	2022	Barnaby Martin Daniël Paulusma Siani Smith
+	Disconnected cuts in claw-free graphs	2020	Barnaby Martin Daniël Paulusma Erik Jan van Leeuwen

Works Cited by This (22)

Action	Title	Year	Authors
+	Approximation for Maximum Surjective Constraint Satisfaction Problems	2011	Walter D. Bach Hang Zhou
+ PDF Chat	Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees	2011	Petr A. Golovach Daniël Paulusma Jian Song
+	The P versus NP–complete dichotomy of some challenging problems in graph theory	2011	Celina M.H. de Figueiredo
+ PDF Chat	The Approximability of Three-valued MAX CSP	2006	Peter Jönsson Mikael Klasson Andrei Krokhin
+	Computational complexity of compaction to irreflexive cycles	2004	Narayan Vikas
+	Coloring mixed hypertrees	2005	Daniel Kráľ Jan Kratochvı́l Andrzej Proskurowski Heinz‐Jürgen Voss
+	List Homomorphisms and Circular Arc Graphs	1999	Tomás Feder Pavol Hell Jing Huang
+	Computational Complexity of Compaction to Reflexive Cycles	2002	Narayan Vikas
+	A complete complexity classification of the role assignment problem	2005	Jiřı́ Fiala Daniël Paulusma
+	A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results	2005	Narayan Vikas