Finding vertex-surjective graph homomorphisms

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Finding vertex-surjective graph homomorphisms

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Finding vertex-surjective graph homomorphisms

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

Kód důvěrnosti údajů

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

Název periodika

Acta Informatica

ISSN

0001-5903

e-ISSN

—

Svazek periodika

49

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

14

Strana od-do

381-394

Kód UT WoS článku

000308722500002

EID výsledku v databázi Scopus

—