论文标题
张量图的可靠性因素和颜色
Robust Factorizations and Colorings of Tensor Graphs
论文作者
论文摘要
自Karger，Motwani和Sudan的开创性结果以来，用于近似3色的算法主要集中在基于SDP的圆形周围。但是，为了打破$ n^{o（1）} $阈值，可能需要重要的组合或代数见解。在图形着色中发展新理解的一种方法是研究图形的特殊子类。例如，Blum研究了随机图的3色，Arora和GE研究了阈值级较低的图形的3色。 在这项工作中，我们研究了由张量产品产生的图形，这似乎是三色问题的新实例。我们考虑$ h =（v，e）$的图形，$ v = v（k_3 \ times g）$和$ e = e = e（k_3 \ times g）\ setminus e'$，其中$ e'\ subseteq e（k_3 \ times g）$是任何边缘的设置，使得没有更多的顶点更重要的是$ un $ e $ e $ e'$ e'我们表明，可以用$ v（\ widetilde {h}）= v（h）$构造$ \ wideTilde {h} = k_3 \ times \ times \ wideTilde {g} $，接近$ h $。对于任意$ g $，$ \ widetilde {h} $满足$ | e（h）Δe（\ widetilde {h}）| \ leq o（ε| e（h）|）$。此外，当$ g $是一个温和的扩展器时，我们在多项式时间内以$ h $的价格提供3色。这些结果部分概括了Imrich的精确张量分解算法。另一方面，在$ g $上没有任何假设，我们表明它是NP-HARD至3色$ h $。
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 \times G)$ and $E = E(K_3 \times G) \setminus E'$, where $E' \subseteq E(K_3 \times 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 $\widetilde{H} = K_3 \times \widetilde{G}$ with $V(\widetilde{H}) = V(H)$ that is close to $H$. For arbitrary $G$, $\widetilde{H}$ satisfies $|E(H) ΔE(\widetilde{H})| \leq 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$.
