Complexity of locally-injective homomorphisms to tournaments

Stefan Bard, Thomas Bellitto, Christopher Duffy, Gary MacGilliyray, Feiran Yan

Research output: Contribution to journalJournal articleResearchpeer-review

20 Downloads (Pure)

Abstract

For oriented graphs G and H, a homomorphism f : G -> H is locally-injective if, for every v is an element of V (G), it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of v. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when H is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when H is a reflexive tournament on two or fewer vertices.
Original languageEnglish
Article number4
JournalDiscrete Mathematics and Theoretical Computer Science
Volume20
Issue number2
Number of pages22
ISSN1462-7264
Publication statusPublished - 2018

    Fingerprint

Keywords

  • Complexity
  • Graph homomorphism
  • Oriented graph
  • Locally-injective homomorphism

Cite this