Minimum cost homomorphisms to reflexive digraphs

Arvind Gupta; Pavol Hell; Mehdi Karimi; Arash Rafiey

doi:10.1007/978-3-540-78773-0_16

Minimum cost homomorphisms to reflexive digraphs

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

^*Corresponding author for this work

Comprehensive Cancer Centre

Simon Fraser University

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-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 language	English
Title of host publication	LATIN 2008
Subtitle of host publication	Theoretical Informatics - 8th Latin American Symposium, Proceedings
Pages	182-193
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-78773-0_16
Publication status	Published - 12 May 2008
Event	8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil Duration: 7 Apr 2008 → 11 Apr 2008

Publication series

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

Conference

Conference	8th Latin American TheoreticalINformatics Symposium, LATIN 2008
Country/Territory	Brazil
City	Buzios
Period	7/04/2008 → 11/04/2008

Keywords

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

Access to Document

10.1007/978-3-540-78773-0_16

Cite this

Gupta, A., Hell, P., Karimi, M., & Rafiey, A. (2008). Minimum cost homomorphisms to reflexive digraphs. In LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings (pp. 182-193). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4957 LNCS). https://doi.org/10.1007/978-3-540-78773-0_16

@inbook{7a237f1d6221443797e6dde6e5793fda,

title = "Minimum cost homomorphisms to reflexive digraphs",

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.",

keywords = "Dichotomy, Homomorphism, Minimum cost homomorphism, NP-completeness, Polynomial time algorithm, Reflexive digraph",

author = "Arvind Gupta and Pavol Hell and Mehdi Karimi and Arash Rafiey",

year = "2008",

month = may,

day = "12",

doi = "10.1007/978-3-540-78773-0_16",

language = "English",

isbn = "3540787720",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "182--193",

booktitle = "LATIN 2008",

note = "8th Latin American TheoreticalINformatics Symposium, LATIN 2008 ; Conference date: 07-04-2008 Through 11-04-2008",

}

Gupta, A, Hell, P, Karimi, M & Rafiey, A 2008, Minimum cost homomorphisms to reflexive digraphs. in LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4957 LNCS, pp. 182-193, 8th Latin American TheoreticalINformatics Symposium, LATIN 2008, Buzios, Brazil, 7/04/2008. https://doi.org/10.1007/978-3-540-78773-0_16

Minimum cost homomorphisms to reflexive digraphs. / Gupta, Arvind; Hell, Pavol; Karimi, Mehdi et al.
LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. 2008. p. 182-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4957 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

TY - CHAP

T1 - Minimum cost homomorphisms to reflexive digraphs

AU - Gupta, Arvind

AU - Hell, Pavol

AU - Karimi, Mehdi

AU - Rafiey, Arash

PY - 2008/5/12

Y1 - 2008/5/12

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

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

KW - Dichotomy

KW - Homomorphism

KW - Minimum cost homomorphism

KW - NP-completeness

KW - Polynomial time algorithm

KW - Reflexive digraph

UR - http://www.scopus.com/inward/record.url?scp=43049120284&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78773-0_16

DO - 10.1007/978-3-540-78773-0_16

M3 - Conference paper

AN - SCOPUS:43049120284

SN - 3540787720

SN - 9783540787723

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 182

EP - 193

BT - LATIN 2008

T2 - 8th Latin American TheoreticalINformatics Symposium, LATIN 2008

Y2 - 7 April 2008 through 11 April 2008

ER -

Minimum cost homomorphisms to reflexive digraphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this