# Finding vertex-surjective graph homomorphisms

Conference paper

Golovach, P., Lidický, B., Martin, B. and Paulusma, D. 2012. Finding vertex-surjective graph homomorphisms.

*7th International Computer Science Symposium (CSR 2012).*Nizhny Novgorod, Russia 03 - 07 Jul 2012 Springer. pp. 160-171 https://doi.org/10.1007/978-3-642-30642-6_16

Type | Conference paper |
---|---|

Title | Finding vertex-surjective graph homomorphisms |

Authors | Golovach, P., Lidický, B., Martin, B. and Paulusma, D. |

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. |

Research Group | Foundations of Computing group |

Conference | 7th International Computer Science Symposium (CSR 2012) |

Page range | 160-171 |

ISSN | 0302-9743 |

ISBN | |

Hardcover | 9783642306419 |

Publisher | Springer |

Publication dates | |

Print | 2012 |

Publication process dates | |

Deposited | 20 Dec 2012 |

Output status | Published |

Additional information | Golovach P.A., Lidický B., Martin B., Paulusma D. (2012) Finding Vertex-Surjective Graph Homomorphisms. In: Hirsch E.A., Karhumäki J., Lepistö A., Prilutskii M. (eds) Computer Science – Theory and Applications. CSR 2012. Lecture Notes in Computer Science, vol 7353. Springer, Berlin, Heidelberg |

Digital Object Identifier (DOI) | https://doi.org/10.1007/978-3-642-30642-6_16 |

Language | English |

Book title | Computer Science -- Theory and Applications |

https://repository.mdx.ac.uk/item/83wzv

##### 29

total views##### 0

total downloads##### 0

views this month##### 0

downloads this month