Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs

Details Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-Transitive Digraphs

2007-12-05

arxiv.org/abs/0712.0804v1

Computer Science

Discrete Mathematics

Scientific paper

For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\ V(G)\dom V(H)$ such that $uv\in A(G)$ implies $f(u)f(v)\in A(H)$. If, moreover, each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of a homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed digraph $H$, the minimum cost homomorphism problem for $H$, denoted MinHOM($H$), can be formulated as follows: Given an input digraph $G$, together with costs $c_i(u)$, $u\in V(G)$, $i\in V(H)$, decide 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 such as the minimum cost chromatic partition and repair analysis problems. We focus on the minimum cost homomorphism problem for locally semicomplete digraphs and quasi-transitive digraphs which are two well-known generalizations of tournaments. Using graph-theoretic characterization results for the two digraph classes, we obtain a full dichotomy classification of the complexity of minimum cost homomorphism problems for both classes.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-311404