For digraphs $D$ and $H$, a homomorphism of $D$ to $H$ is a mapping $f:\ V(D)\dom V(H)$ such that $uv\in A(D)$ implies $f(u)f(v)\in A(H)$.

Suppose $D$ and $H$ are two digraphs, and $c_i(u)$, $u\in V(D)$, $i\in V(H)$, are nonnegative real costs. The cost of the homomorphism $f$ of $D$ to $H$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. The minimum cost homomorphism for a fixed digraph $H$, denoted by MinHOM($H$), asks whether or not an input structure $D$, with nonnegative real costs $c_i(u)$, $u\in V(D)$, $i\in V(H)$, admits a homomorphism $f$ to $H$ and if it admits one, find a homomorphism of minimum cost. Our interest is in proving a dichotomy for minimum cost homomorphism problem: we would like to prove that for each digraph $H$, MinHOM($H$) is polynomial-time solvable, or NP-hard. Gutin, Rafiey, and Yeo conjectured that such a classification exists: MinHOM($H$) is polynomial time solvable if $H$ admits a $k$-Min-Max ordering for some $k \geq 1$, and it is NP-hard otherwise.

For undirected graphs, the complexity of the problem is well understood; for digraphs, the situation appears to be more complex, and only partial results are known. In this thesis, we seek to verify this conjecture for large classes of digraphs including reflexive digraphs, locally in-semicomplete digraphs, as well as some classes of particular interest such as quasi-transitive digraphs. For all classes, we exhibit a forbidden induced subgraph characterizations of digraphs with $k$-Min-Max ordering; our characterizations imply a polynomial time test for the existence of a $k$-Min-Max ordering. Given these characterizations, we show that for a digraph $H$ which does not admit a $k$-Min-Max ordering, the minimum cost homomorphism problem is NP-hard. This leads us to a full dichotomy classification of the complexity of minimum cost homomorphism problems for the aforementioned classes of digraphs.

This is joint work with Pavol Hell and Arvind Gupta.