Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles
Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles
复制标题
DOI：
10.1007/s00453-007-9148-9
复制
发表时间：
2008-08
期刊：
影响因子：
1.1
通讯作者：
Venkatesh Raman;Saket Saurabh
中科院分区：
文献类型：
--
作者：
Venkatesh Raman;Saket Saurabh
我们表明，对于一般图上的各种参数化复杂度类来说很难的几个问题，在没有小环的图上变得固定参数可处理。更具体地说，我们给出了支配集、t-顶点覆盖（其中我们需要至少覆盖边）及其在周长至少为 5 的图上的几个变体的固定参数可处理算法。已知这些问题对于一般图中的 somei≥1 来说是 W[i]-困难的。我们还表明，支配集问题对于二分图来说是 W[2]-困难的，因此对于自由三角形图来说也是如此。在独立集及其几个变体的情况下，我们表明即使在自由三角形图中，这些问题也是固定参数可处理的。相比之下，我们展示了密集子图问题，其中人们有兴趣在具有至少边缘的 k 顶点上找到诱导子图，由 k 参数化，即使在周长至少为 6 的图上也是 W[1]-困难。最后，我们为周长至少为 5 的图的支配集问题给出了 O(logp) 比率近似算法，其中 p 是图的最佳支配集的大小。这改进了该问题之前的 O(logn) 因子近似算法，其中 是输入图的顶点数。
We show that several problems that are hard for various parameterized complexity classes on general graphs, become fixed parameter tractable on graphs with no small cycles.More specifically, we give fixed parameter tractable algorithms forDominating Set,t-Vertex Cover(where we need to cover at leasttedges) and several of their variants on graphs with girth at least five. These problems are known to beW[i]-hard for somei≥1 in general graphs. We also show that theDominating Setproblem isW[2]-hard for bipartite graphs and hence for triangle free graphs.In the case ofIndependent Setand several of its variants, we show these problems to be fixed parameter tractable even in triangle free graphs. In contrast, we show that theDense Subgraphproblem where one is interested in finding an induced subgraph onkvertices having at leastledges, parameterized byk, isW[1]-hard even on graphs with girth at least six.Finally, we give anO(logp) ratio approximation algorithm for theDominating Setproblem for graphs with girth at least 5, wherepis the size of an optimum dominating set of the graph. This improves the previousO(logn) factor approximation algorithm for the problem, wherenis the number of vertices of the input graph.