THEORY SEMINAR: Please join us on Monday, January 27th at 11am, in Siebel 3401, where Arash Rafiey (Indiana State) will give a talk, “Approximability and In-approximability of H-coloring”. Please see their abstract below:
We consider the problem of finding an H-coloring of input hypergraph G (or digraph in binary case) to target hypergraph(digraph) H, denoted by HC(H). HC(H) seeks a mapping f (also called homomorphism) from the vertices of G to the vertices of H so that the image of every hyperedge(edge) in G is a hyperedge of H. The optimization version of HC(H), denoted by MHC(H), is when there is a cost function $c$ as part of the input, for every vertex $u$ of G and every vertex, $i$ of H, $c(u,i)$ is a non-negative rational number which is the cost of mapping $u$ to $i$. The goal is to find a homomorphism $f$ from G to H whose overall cost is minimized. This problem is motivated by an actual problem in the industry called the level of repairs analysis. The MHC generalized several optimization problems, such as Minimum sum $k$-coloring, multiway cut, linear programming system (Min Ones), etc. The goal is to classify hypergraphs H for which MHC(H) admits a constant factor approximation. On the positive side, we prove that MHC(H) admits a constant factor approximation if H has a bounded width. On the negative side, we show that for every hypergraph H, MHC(H) is APX-hard; no constant approximation factor better than $1.021$ exists under P not equal NP assumption.
The bounded width instances H cover most of the instances of hypergraphs for which MHC (H) admits constant approximation algorithm. However, some problems, like the system of linear equations over GF(2), are instances of MHC (H) that do not have bounded width and are hard to approximate within a constant factor. The existence of hypergraph H that does not have bounded width but \MHCHH admits constant approximation algorithm remains an interesting open problem.
Joint work with Akbar Rafiey and Kamyar Khodamoradi.