论文标题
列表的完全复杂性分类同构图形图形图
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
论文作者
论文摘要
从图$ g $到图$ h $的同构映射是从$ v（g）$到$ v（h）$的边缘保留映射。令$ h $为带有可能循环的固定图。在列表同构问题（$ h $）表示的同构问题中，我们得到了一个图$ g $，每个顶点$ v $均以列表$ l（v）$ h $的列表分配。我们询问是否存在同构$ h $从$ g $到$ h $，它尊重列表$ l $，即，对于v（g）$中的每一个$ v \，它都认为$ h（v）\ in L（v）$。 LHOM（$ H $）的复杂性二分法已由Feder，Hell和Huang证明了[JGT 2003]。我们对问题的复杂性感兴趣，该问题是通过输入图的树宽进行参数化的。 Egri，Marx和Rzą该问题[Stacs 2018]对此问题进行了调查，他们为反射图的特殊情况$ h $获得了严格的复杂性界限。 在本文中，我们将其结果扩展并概括为\ emph {all}相关图$ h $，即，lhom {h}问题是np-hard。对于每个这样的$ h $ *可以在时间上解决$ k^{t} \ cdot n^{\ mathcal {o}（1）} $，前提是给出输入图以及宽度$ t $， *不能在时间$ $（k- \ varepsilon）^{t} \ cdot n^{\ mathcal {o}（1）} $中解决任何$ \ varepsilon> 0 $，除非Seth失败。 对于某些图$ h $，$ k（h）$的值比琐碎的上限小得多，即$ | v（h）| $。 获得匹配的上限和下界表明，我们发现的算法集集不能扩展，以便获得有界widwidth图的LHOM（$ h $）的更快算法。此外，算法或下限的证明都不是特定于树宽的。我们认为它们可以用于其他lhom（$ h $）的其他变体，例如具有不同的参数化。
A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$. Let $H$ be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom($H$), we are given a graph $G$, whose every vertex $v$ is assigned with a list $L(v)$ of vertices of $H$. We ask whether there exists a homomorphism $h$ from $G$ to $H$, which respects lists $L$, i.e., for every $v \in V(G)$ it holds that $h(v) \in L(v)$. The complexity dichotomy for LHom($H$) was proven by Feder, Hell, and Huang [JGT 2003]. We are interested in the complexity of the problem, parameterized by the treewidth of the input graph. This problem was investigated by Egri, Marx, and Rzążewski [STACS 2018], who obtained tight complexity bounds for the special case of reflexive graphs $H$. In this paper we extend and generalize their results for \emph{all} relevant graphs $H$, i.e., those, for which the LHom{H} problem is NP-hard. For every such $H$ we find a constant $k = k(H)$, such that LHom($H$) on instances with $n$ vertices and treewidth $t$ * can be solved in time $k^{t} \cdot n^{\mathcal{O}(1)}$, provided that the input graph is given along with a tree decomposition of width $t$, * cannot be solved in time $(k-\varepsilon)^{t} \cdot n^{\mathcal{O}(1)}$, for any $\varepsilon >0$, unless the SETH fails. For some graphs $H$ the value of $k(H)$ is much smaller than the trivial upper bound, i.e., $|V(H)|$. Obtaining matching upper and lower bounds shows that the set of algorithmic tools we have discovered cannot be extended in order to obtain faster algorithms for LHom($H$) in bounded-treewidth graphs. Furthermore, neither the algorithm, nor the proof of the lower bound, is very specific to treewidth. We believe that they can be used for other variants of LHom($H$), e.g. with different parameterizations.
