Minimum cost homomorphisms to reflexive digraphs

Arvind Gupta*, Pavol Hell, Mehdi Karimi, Arash Rafiey

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

13 Citations (Scopus)

Abstract

For a fixed digraph H, the minimum cost homomorphism problem, MinHOM(H), asks whether an input digraph G, with given costs c i (u), u∈ ∈V(G), i∈ ∈V(H), and an integer k, admits a homomorphism to H of total cost not exceeding k. Minimum cost homomorphism problems encompass many well studied optimization problems such as list homomorphism problems, retraction and precolouring extension problems, chromatic partition optimization, and applied problems in repair analysis. For undirected graphs the complexity of the problem, as a function of the parameter H, is well understood; for digraphs, the situation appears to be more complex, and only partial results are known. We focus on the minimum cost homomorphism problem for reflexive digraphs H. It is known that MinHOM(H) is polynomial if H has a Min-Max ordering. We prove that for any other reflexive digraph H, the problem MinHOM(H) is NP-complete. (This was earlier conjectured by Gutin and Kim.) Apart from undirected graphs, this is the first general class of digraphs for which such a dichotomy has been proved. Our proof involves a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering, and implies a polynomial test for the existence of a Min-Max ordering in a reflexive digraph H.

Original languageEnglish
Title of host publicationLATIN 2008
Subtitle of host publicationTheoretical Informatics - 8th Latin American Symposium, Proceedings
Pages182-193
Number of pages12
DOIs
Publication statusPublished - 12 May 2008
Event8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil
Duration: 7 Apr 200811 Apr 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4957 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th Latin American TheoreticalINformatics Symposium, LATIN 2008
Country/TerritoryBrazil
CityBuzios
Period7/04/200811/04/2008

Keywords

  • Dichotomy
  • Homomorphism
  • Minimum cost homomorphism
  • NP-completeness
  • Polynomial time algorithm
  • Reflexive digraph

Fingerprint

Dive into the research topics of 'Minimum cost homomorphisms to reflexive digraphs'. Together they form a unique fingerprint.

Cite this