Minimum cost homomorphisms to digraphs

Resource type
Thesis type
(Thesis) Ph.D.
Date created
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 integer costs. The cost of the homomorphism $f$ of $D$ to $H$ is $\sum_{u\inV(D)}c_{f(u)}(u)$. The minimum cost homomorphism for a fixed digraph $H$, denoted by MinHOM($H$), asks whether or not an input digraph $D$, with nonnegative integer 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 characterization 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.
Copyright statement
Copyright is held by the author.
Scholarly level
Member of collection
Download file Size
etd4362_MKarimi.pdf 853.99 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0