Minimum Cost Homomorphism Dichotomy for Oriented Cycles |
| |
Authors: | Gregory Gutin Arash Rafiey Anders Yeo |
| |
Institution: | 1.Department of Computer Science Royal Holloway,University of London,Egham,UK;2.School of Computing Science,Simon Fraser University,Burnaby,Canada |
| |
Abstract: | For digraphs D and H, a mapping f : V(D) → V(H) is a homomorphism of D to H if uv ∈ A(D) implies f(u) f(v) ∈ A(H). If, moreover, each vertex u ∈ V(D) is associated with costs c
i
(u), i ∈ V(H), then the cost of the homomorphism f is ∑
u ∈V(D)
c
f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem for
H (abbreviated MinHOM(H)). The problem is to decide, for an input graph D with costs c
i
(u), u ∈ V(D), i ∈ V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost. We obtain a dichotomy classification for the time complexity of MinHOM(H) when H is an oriented cycle. We conjecture a dichotomy classification for all digraphs with possible loops. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|