Toward a Dichotomy for Approximation of H-coloring
share
The minimum cost homomorphism problem (MinHOM) is a natural optimization problem for homomorphisms to a fixed (di)graph H. Given an input (di)graph G, with a cost associated with mapping any vertex of G to any vertex of H, one seeks to minimize the sum of costs of the assignments over all homomorphisms of G to H. The complexity of this problem is well understood [27], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. Therefore, we are interested in the approximation of MinHOM within a constant factor. Regarding digraphs, MinHOM(H) is not approximable if H contains a 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. In the digraphs case, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with min-ordering), and k-arc digraphs (with extended min-ordering). Specifically, we show that: Dichotomy for Graphs: MinHOM(H) has a 2|V(H)|-approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a bi-arc graph); otherwise, it is inapproximable; MinHOM(H) has a |V(H)|^2-approximation algorithm if H is a bi-arc digraph; MinHOM(H) has a |V(H)|^2-approximation algorithm if H is a k-arc digraph. We draw a conclusion, by showing why these results are important in closing the classification, as well as, providing a road map in achieving such a classification. 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 approximation algorithm that is independent of |V(H)|.
READ FULL TEXT