论文标题
结构性参数化，带有调制器遗忘
Structural Parameterizations with Modulator Oblivion
论文作者
论文摘要
众所周知，诸如顶点覆盖，反馈顶点集和奇数循环的问题是可以在弦图等级中解决多项式时间的问题。我们在图表中考虑了这些问题，该图的最多具有$ k $的顶点，其删除会导致和弦图，当通过$ k $进行参数时。尽管这项研究自然符合所谓的“结构参数化”的最新趋势，但在这里我们假设没有给出删除集。 解决它们的一种方法是计算$ k $大小或大约（$ f（k）$大小，用于函数$ f $）和弦顶点删除套件，然后使用图表的结构属性来设计算法。此方法至少导致$ k^{\ mathcal {o}（k）} n^{\ mathcal {o}（1）} $运行时间，当我们使用已知的参数化或近似算法来查找$ k $ sized sized cobordal deletion设置$ n $ n $ vertex图。 在这项工作中，我们设计了$ 2^{\ Mathcal {o}（k）} n^{\ Mathcal {o}（1）} $时间算法的这些问题。我们的算法不会计算和弦顶点缺失集（甚至是近似解决方案）。取而代之的是，我们构造给定图的树分解时间$ 2^{\ Mathcal {o}（k）} n^{\ Mathcal {o}（1）} $，其中每个袋子是四个集团和$ \ Mathcal {o}（o}（o}（k）$ vertices）的结合。然后，我们在此特殊的树分解上应用标准的动态编程算法。这种特殊的树分解可能具有独立的兴趣。 在给定整数$ k $的意义上说，我们的算法是自适应（鲁棒），他们检测该图是最多$ k $的和弦顶点删除尺寸的弦顶删除集还是输出特殊的树分解并解决问题。 我们还显示了在强烈的指数时间假设（SETH）下解决的问题的下限。
It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most $k$ vertices whose deletion results in a chordal graph, when parameterized by $k$. While this investigation fits naturally into the recent trend of what are called `structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a $k$-sized or an approximate ($f(k)$ sized, for a function $f$) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least $k^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ running time when we use the known parameterized or approximation algorithms for finding a $k$-sized chordal deletion set on an $n$ vertex graph. In this work, we design $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ where each bag is a union of four cliques and $\mathcal{O}(k)$ vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are adaptive (robust) in the sense that given an integer $k$, they detect whether the graph has a chordal vertex deletion set of size at most $k$ or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).
