Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs

Details Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs

2006-02-10

arxiv.org/abs/cs/0602038v2

Computer Science

Discrete Mathematics

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599980