Tight Running Time Lower Bounds for Vertex Deletion Problems
Tight Running Time Lower Bounds for Vertex Deletion Problems
复制标题
DOI：
10.1145/3186589
复制
发表时间：
2018-05-01
影响因子：
0.7
通讯作者：
Komusiewicz, Christian
中科院分区：
文献类型：
--
作者：
Komusiewicz, Christian
对于图类Pi， Pi顶点删除问题以无向图G = （V， E）和整数k作为输入，并询问是否存在一组最多k个顶点的集合，可以从G中删除，使得结果图是…根据Lewis和Yannakakis b[17]的经典结果，pi顶点缺失对所有遗传特性都是np困难的。我们对原来的np -硬度结构进行了调整，证明在指数时间假设（ETH）下，可以得到紧复杂度的结果。我们证明了pi -顶点删除不允许2（o(n)）时间算法，其中n是g中的顶点数。我们还获得了包含输入图中边数m的运行时间界限的二分类。一方面，如果Pi包含所有无边图，则不存在2（o(n+m)）时间的Pi顶点删除算法。另一方面，如果存在一个不包含在的固定无边图。和遏制。可以在2（O(n)）或2（O(m)）时间内确定，则可以分别在2（O（根m）） + O(n)或2(O(m)) + O(n)时间内求解Pi-Vertex Deletion。我们还考虑了输入图G的域上的限制条件。例如，我们得到了如果G是平面的，且pi -顶点删除不能在2(o(√n)))时间内解决。是遗传的，包含和排除无限多个平面图。最后，对于删除的顶点集必须生成连通图的问题变体，我们提供了类似的结果。
For a graph class Pi, the Pi-Vertex Deletion problem has as input an undirected graph G = (V, E) and an integer k and asks whether there is a set of at most k vertices that can be deleted from G such that the resulting graph is a member of.. By a classic result of Lewis and Yannakakis [17], Pi-Vertex Deletion is NP-hard for all hereditary properties.. We adapt the original NP-hardness construction to show that under the exponential time hypothesis (ETH), tight complexity results can be obtained. We show that Pi-Vertex Deletion does not admit a 2(o(n))-time algorithm where n is the number of vertices in G. We also obtain a dichotomy for running time bounds that include the number m of edges in the input graph. On the one hand, if Pi contains all edgeless graphs, then there is no 2(o(n+m))-time algorithm for Pi-Vertex Deletion. On the other hand, if there is a fixed edgeless graph that is not contained in. and containment in. can be determined in 2(O(n)) time or 2(o(m)) time, then Pi-Vertex Deletion can be solved in 2(O(root m)) + O(n) or 2(o(m)) + O(n) time, respectively. We also consider restrictions on the domain of the input graph G. For example, we obtain that Pi-Vertex Deletion cannot be solved in 2(o(root n)) time if G is planar and. is hereditary and contains and excludes infinitely many planar graphs. Finally, we provide similar results for the problem variant where the deleted vertex set has to induce a connected graph.