论文标题
通过删除边缘和顶点列表同构：有限 - 树的紧密复杂性界限
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
论文作者
论文摘要
本文的目的是调查列表同构引起的优化问题的家族，并了解如果我们将问题限制为有界树的图表，最好的算法是什么。对于固定的$ H $，优化问题LHOMVD（$ H $）的输入是图形$ g $，列表$ L（V）$，其任务是找到具有最小尺寸的$ x $ thertices的$ x $，以至于$（g-x，l）$具有列表的list list andomorphism atmorphism至$ h $。我们类似地定义了Edge-Dosletion变体LHOMED（$ H $）。这种表现力的问题系列包括基本上等同于基本问题的成员，例如顶点覆盖，最大切割，奇数循环横向和边缘/顶点多路切割。 对于这两个变体，我们首先表征这些图表$ h $，这些图表使问题多项式时间可解决，并表明该问题对于其他固定的$ H $都是NP-HARD。其次，作为我们的主要结果，我们确定问题为NP-HARD的每张图$ H $，是最小的常数$ C_H $，以便可以在时间$ c^t_h \ cdot n^{o（1）$在时间$ c^t_h \ cdot n^{o（1）} $中解决$ g $ w $ g $ w width $ t $的$ g $ t $的最大尺寸，是$ i（h）的最大尺寸。无与伦比的社区。对于Vertex-Deotion变体LHOMVD（$ H $），我们表明，最小的常数为$ i（h）+1 $，每$ H $。 对于边缘版本而言，情况更为复杂。对于每一个$ h $，如果给出了宽度$ t $的树分解，就可以在时间$ i（h）^t \ cdot n^{o（1）} $中解决lhomed（$ h $）。但是，$ h $的特定类型的分解存在表明，有图形$ h $可以更有效地解决lhomed（$ h $）的求解，并且最佳可能的常数可以任意小于$ i（h）$。尽管如此，我们确定了这种最佳常数，并且（假设塞思）对每个固定的$ h $都证明了紧密的界限。
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict the problem to bounded-treewidth graphs. For a fixed $H$, the input of the optimization problem LHomVD($H$) is a graph $G$ with lists $L(v)$, and the task is to find a set $X$ of vertices having minimum size such that $(G-X,L)$ has a list homomorphism to $H$. We define analogously the edge-deletion variant LHomED($H$). This expressive family of problems includes members that are essentially equivalent to fundamental problems such as Vertex Cover, Max Cut, Odd Cycle Transversal, and Edge/Vertex Multiway Cut. For both variants, we first characterize those graphs $H$ that make the problem polynomial-time solvable and show that the problem is NP-hard for every other fixed $H$. Second, as our main result, we determine for every graph $H$ for which the problem is NP-hard, the smallest possible constant $c_H$ such that the problem can be solved in time $c^t_H\cdot n^{O(1)}$ if a tree decomposition of $G$ having width $t$ is given in the input.Let $i(H)$ be the maximum size of a set of vertices in $H$ that have pairwise incomparable neighborhoods. For the vertex-deletion variant LHomVD($H$), we show that the smallest possible constant is $i(H)+1$ for every $H$. The situation is more complex for the edge-deletion version. For every $H$, one can solve LHomED($H$) in time $i(H)^t\cdot n^{O(1)}$ if a tree decomposition of width $t$ is given. However, the existence of a specific type of decomposition of $H$ shows that there are graphs $H$ where LHomED($H$) can be solved significantly more efficiently and the best possible constant can be arbitrarily smaller than $i(H)$. Nevertheless, we determine this best possible constant and (assuming the SETH) prove tight bounds for every fixed $H$.
