Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs

Simple item page
dc.creatorGutin, G.
dc.creatorHell, P.
dc.creatorRafiey, A.
dc.creatorYeo, A.
dc.date2006-02-10
dc.date2006-02-14
dc.date.accessioned2026-07-07T07:02:29Z
dc.date.available2026-07-07T07:02:29Z
dc.descriptionFor graphs $G$ and $H$, a mapping $f: V(G)\dom V(H)$ is a homomorphism of $G$ to $H$ if $uv\in E(G)$ implies $f(u)f(v)\in E(H).$ If, moreover, each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of the homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed graph $H$, we have the {\em minimum cost homomorphism problem}, written as MinHOM($H)$. The problem is to decide, for an input graph $G$ with costs $c_i(u),$ $u \in V(G), i\in 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 describe 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. Along the way, we prove a new characterization of the class of proper interval bigraphs.
dc.identifierhttps://arxiv.org/abs/cs/0602038
dc.identifierhttp://arxiv.org/abs/cs/0602038
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/108618
dc.subjectDiscrete Mathematics
dc.subjectArtificial Intelligence
dc.titleMinimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs
dc.typetext

Files

Collections

arXiv