Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs

Details Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs

2005-09-28

arxiv.org/abs/cs/0509091v1

Computer Science

Discrete Mathematics

Scientific paper

For digraphs $D$ and $H$, a mapping $f: V(D)\dom V(H)$ is a {\em homomorphism of $D$ to $H$} if $uv\in A(D)$ implies $f(u)f(v)\in A(H).$ For a fixed directed or undirected graph $H$ and an input graph $D$, the problem of verifying whether there exists a homomorphism of $D$ to $H$ has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced very recently by the authors and M. Tso. Suppose we are given a pair of digraphs $D,H$ and a positive integral cost $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$. The cost of a homomorphism $f$ of $D$ to $H$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. Let $H$ be a fixed digraph. The minimum cost homomorphism problem for $H$, MinHOMP($H$), is stated as follows: For input digraph $D$ and costs $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$, verify whether there is a homomorphism of $D$ to $H$ and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of \MiP for $H$ being a semicomplete digraph. In this paper we extend the classification to semicomplete $k$-partite digraphs, $k\ge 3$, and obtain such a classification for bipartite tournaments.

Affiliated with

Also associated with

No associations

Rating

Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs 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 Semicomplete Multipartite Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-238594