Minimum cost homomorphism dichotomy for locally in-semicomplete digraphs

A. Gupta*, Mehdi Karimi, E. J. Kim, A. Rafiey

*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

For digraphs G and H, a homomorphism of G to H is a mapping such that uv∈ ∈A(G) implies f(u)f(v)∈ ∈A(H). In the minimum cost homomorphism problem we associate costs c i (u), u∈ ∈V(G), i∈ ∈V(H) with the mapping of u to i and the cost of a homomorphism f is defined Σu∈V(G) c f(u)(u) accordingly. Here the minimum cost homomorphism problem for a fixed digraph H, denoted by MinHOM(H), is to check whether there exists a homomorphism of G to H and to obtain one of minimum cost, if one does exit. The minimum cost homomorphism problem is now well understood for digraphs with loops. For loopless digraphs only partial results are known. In this paper, we find a full dichotomy classification of MinHom(H), when H is a locally in-semicomplete digraph. This is one of the largest classes of loopless digraphs for which such dichotomy classification has been proved. This paper extends the previous result for locally semicomplete digraphs.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - Second International Conference, COCOA 2008, Proceedings
Pages374-383
Number of pages10
DOIs
Publication statusPublished - 22 Sept 2008
Event2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008 - St. John's, NL, Canada
Duration: 21 Aug 200824 Aug 2008

Publication series

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

Conference

Conference2nd International Conference on Combinatorial Optimization and Applications, COCOA 2008
Country/TerritoryCanada
CitySt. John's, NL
Period21/08/200824/08/2008

Cite this