Robust Factorizations and Colorings of Tensor Graphs
share
Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around SDP-based rounding. However, it is likely that important combinatorial or algebraic insights are needed in order to break the n^o(1) threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3-coloring of random graphs, and Arora and Ge studied the 3-coloring of graphs with low threshold-rank. In this work, we study graphs which arise from a tensor product, which appear to be novel instances of the 3-coloring problem. We consider graphs of the form H = (V,E) with V =V( K_3 × G) and E = E(K_3 × G) ∖ E', where E' ⊆ E(K_3 × G) is any edge set such that no vertex has more than an ϵ fraction of its edges in E'. We show that one can construct H = K_3 ×G with V(H) = V(H) that is close to H. For arbitrary G, H satisfies |E(H) Δ E(H)| ≤ O(ϵ|E(H)|). Additionally when G is a mild expander, we provide a 3-coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP-hard to 3-color H.
READ FULL TEXT