PIMS - SFU Theory Seminar: Akbar Rafiey

Given two (di)graphs $G$, $H$ and a cost function $c:V(G)\times V(H) \to \mathbb{Q}_{\geq 0}\cup\{+\infty\}$, in the minimum cost homomorphism problem, MinHOM($H$), we are interested in finding a homomorphism $f:V(G)\to V(H)$ (a.k.a $H$-coloring) that minimizes $\sum\limits_{v\in V(G)}c(v,f(v))$. The complexity of \emph{exact minimization} of this problem is well understood due to Hell and Rafiey 2012, and the class of digraphs $H$, for which the MinHOM($H$) is polynomial time solvable is a small subset of all digraphs.

In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM($H$) is not approximable if $H$ contains a \emph{digraph asteroidal triple (DAT)}. We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM($H$) when $H$ is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a \emph{conservative semi-lattice polymorphism} or \emph{min-ordering}), and
$k$-arc digraphs (digraphs with an \emph{extended min-ordering}). Specifically, we show that:

a) \textbf{Dichotomy for Graphs:} MinHOM($H$) has a $2|V(H)|$-approximation algorithm if graph $H$ admits a \emph{conservative majority polymorphims} (i.e. $H$ is a \emph{bi-arc graph}), otherwise, it is inapproximable;

b) MinHOM($H$) has a $|V(H)|^2$-approximation algorithm if $H$ is a bi-arc digraph;

c) MinHOM($H$) has a $|V(H)|^2$-approximation algorithm if $H$ is a $k$-arc digraph.

In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of $H$. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs $H$, where MinHOM($H$) admits a constant factor approximation algorithm that is independent of $|V(H)|$. Join work with Arash Rafiey and Tiago Santos