Skip to main content

2012 | OriginalPaper | Buchkapitel

Finding Vertex-Surjective Graph Homomorphisms

verfasst von : Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma

Erschienen in: Computer Science – Theory and Applications

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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

${\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 class of 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 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

${\cal G}$

is the class of trees and

${\cal H}$

is the class of trees with at most

k

leaves, or if

${\cal G}$

and

${\cal H}$

are equal to the class of graphs with vertex cover number at most

k

.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Finding Vertex-Surjective Graph Homomorphisms
verfasst von
Petr A. Golovach
Bernard Lidický
Barnaby Martin
Daniël Paulusma
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-30642-6_16