Toward a Dichotomy for Approximation of $H$-coloring
Toward a Dichotomy for Approximation of $H$-coloring
复制标题
走向$H$着色近似的二分法
DOI：
10.4230/lipics.icalp.2019.91
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Thiago Santos
中科院分区：
文献类型：
--
作者：
Akbar Rafiey;A. Rafiey;Thiago Santos
给定两个（di）图G，H和一个代价函数$c：V（G）\times V（H）\to\mathbb {Q}_{\geq 0}\cup\{+\infty\}$，在最小代价同态问题MinHOM（H）中，目标是找到一个同态$f：V（G）\to V（H）$（也称为H-着色），使$\sum\limits_{v\in V（G）} c（v，f（v））$最小化。这个问题的精确最小化的复杂性是很好理解的[34]，并且MinHOM（H）是多项式时间可解的有向图类H是所有有向图的一个小子集。
在本文中，我们考虑的MinHOM在一个常数因子的近似。对于有向图，如果H包含有向图星状三元组（DAT），则MinHOM（H）是不可逼近的。我们向近似情况的二分法分类迈出了重要的一步。当H是一个图时，我们给出了MinHOM（H）的一个二分法.对于有向图，我们提供了两类重要的有向图的常数因子近似算法，即双弧有向图（具有保守半格多态性或最小序的有向图）和k-弧有向图（具有扩展最小序的有向图）。具体而言，我们表明：
1. \textbf {Dichotomy for Graphs：} MinHOM（H）有$2| V（高）|如果图H是保守多数多态图（即H是双弧图），则它是不可逼近的;
2. MinHOM（H）有一个$|V（高）|当H是双弧有向图时的^2 $-逼近算法;
3. MinHOM（H）有一个$|V（高）|有向k-弧图的^2 $-近似算法。
总之，我们显示了这些结果的重要性，并提供了见解，实现二分法分类近似的情况下。我们的常数因子取决于H的大小。然而，我们的算法的实现提供了一个更好的近似比。它留下了开放的研究分类的有向图H，其中MinHOM（H）允许一个常数因子近似算法，是独立于H。
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), goal is 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 exact minimization of this problem is well understood [34], 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. For 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. For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a conservative semi-lattice polymorphism or min-ordering), and k-arc digraphs (digraphs with an extended min-ordering). Specifically, we show that:
1. \textbf{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;
2. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a bi-arc digraph;
3. 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 H.
登录
查看更多内容
最小可排序有向图
影响因子：
0.8
作者：
Hell, Pavol;Huang, Jing;McConnell, Ross M.;Rafiey, Arash
通讯作者：
Rafiey, Arash
DOI：
10.1145/1806689.1806789
发表时间：
2010-03
期刊：
--
影响因子：
--
作者：
M. Dyer;David Richerby
通讯作者：
M. Dyer;David Richerby
通用价值 CSP 的复杂性
DOI：
10.1109/focs.2015.80
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Kolmogorov V
通讯作者：
Kolmogorov V
有价值的约束满足问题的二值化
影响因子：
0.8
作者：
Cohen D
通讯作者：
Cohen D