P. A. Golovach
Finding vertex-surjective graph homomorphisms
Golovach, P. A.; Lidicky, B.; Martin, B.; Paulusma, D.
Authors
Contributors
Edward A. Hirsch
Editor
Juhani Karhumäki
Editor
Arto Lepistö
Editor
Michail Prilutskii
Editor
Abstract
The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes G and H , respectively. We determine to what extent a certain choice of G and H influences its computational complexity. We observe that the problem is polynomial-time solvable if H is the class of paths, whereas it is NP-complete if G is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if G is the class of trees and H is the class of trees with at most k leaves, or if G and H are equal to the class of graphs with vertex cover number at most k.
Citation
Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. In E. A. Hirsch, J. Karhumäki, A. Lepistö, & M. Prilutskii (Eds.), Computer science : theory and applications : 7th International Computer Science Symposium in Russia, CSR 2012, 3-7 July 2012, Nizhny Novgorod, Russia ; proceedings (160-171). https://doi.org/10.1007/978-3-642-30642-6_16
Publication Date | 2012 |
---|---|
Deposit Date | Mar 11, 2013 |
Pages | 160-171 |
Series Title | Lecture notes in computer science |
Series Number | 7353 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Computer science : theory and applications : 7th International Computer Science Symposium in Russia, CSR 2012, 3-7 July 2012, Nizhny Novgorod, Russia ; proceedings. |
ISBN | 9783642306419 |
DOI | https://doi.org/10.1007/978-3-642-30642-6_16 |
Public URL | https://durham-repository.worktribe.com/output/1157341 |
Additional Information | Series: Lecture Notes in Computer Science, Volume 7353 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search