Finding vertex-surjective graph homomorphisms

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10125721" target="_blank" >RIV/00216208:11320/12:10125721 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00236-012-0164-0" target="_blank" >http://dx.doi.org/10.1007/s00236-012-0164-0</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00236-012-0164-0" target="_blank" >10.1007/s00236-012-0164-0</a>

Result language
angličtina
Original language name
Finding vertex-surjective graph homomorphisms
Original language description
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 tograph classes ${cal G}$ and ${cal H}$, respectively. We determine to what extent a certain choice of ${cal G}$ and ${cal H}$ influences its computational complexity. We observe that the problem is polynomial-time solvable if ${cal H}$ is the classof paths, whereas it is NP-complete if ${cal 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 int
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)