Name
Abstract | ||
|---|---|---|
For graphs G and H, a mapping f:V(G)-V(H) is a homomorphism of G to H if uv@?E(G) implies f(u)f(v)@?E(H). If, moreover, each vertex u@?V(G) is associated with costs c"i(u),i@?V(H), then the cost of the homomorphism f is @?"u"@?"V"("G")c"f"("u")(u). For each fixed graph H, we have the minimum cost homomorphism problem, written as MinHOM(H). The problem is to decide, for an input graph G with costs c"i(u),u@?V(G),i@?V(H), whether there exists a homomorphism of G to H and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well-studied optimization problems. We prove a dichotomy of the minimum cost homomorphism problems for graphs H, with loops allowed. When each connected component of H is either a reflexive proper interval graph or an irreflexive proper interval bigraph, the problem MinHOM(H) is polynomial time solvable. In all other cases the problem MinHOM(H) is NP-hard. This solves an open problem from an earlier paper. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ejc.2007.11.012 | Eur. J. Comb. |
Keywords | Field | DocType |
fixed graph h,minimum cost graph homomorphisms,open problem,well-studied optimization problem,graphs h,problem minhom,graphs g,input graph g,minimum cost,reflexive proper interval graph,minimum cost homomorphism problem,graph homomorphism,optimization problem,connected component,interval graph,polynomial time | Discrete mathematics,Combinatorics,Open problem,Bound graph,Interval graph,Vertex (geometry),Graph homomorphism,Homomorphism,Connected component,Reflexive relation,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 0195-6698 |
Citations | PageRank | References |
26 | 0.91 | 25 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gregory Gutin | 1 | 1583 | 142.47 |
| Pavol Hell | 2 | 2638 | 288.75 |
| Arash Rafiey | 3 | 339 | 28.08 |
| Anders Yeo | 4 | 1225 | 108.09 |