Improving Vertex Cover as a Graph Parameter
Improving Vertex Cover as a Graph Parameter
复制标题
改进顶点覆盖作为图参数
DOI：
10.46298/dmtcs.2136
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Ganian
中科院分区：
文献类型：
--
作者：
R. Ganian
参数化算法通常用于有效地解决图形上的NP - 硬性问题。在这种情况下，顶点封面被用作处理图形问题的强大参数，即使通过树宽度参数化，这些问题也很难解决。但是，顶点覆盖物的缺点是严重限制了可允许的图形类。我们介绍了称为Twin-Cover的顶点封面的概括，并表明当通过Twin-Cover参数化时，存在着广泛的困难问题，存在FPT算法。双包覆盖比顶点盖的优点在于，它对图形结构施加较小的限制，即使在密集的图上也达到低值。除了引入参数本身之外，本文还提供了许多由Twin-Cover参数化的新FPT算法，其中特别强调了即使通过树宽参数进行参数化时，这些问题也不在FPT中。它还表明，MS1模型检查可以在通过双覆盖的基本fpt时间参数中进行，并讨论内核化场。
Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a generalization of vertex cover called twin-cover and show that FPT algorithms exist for a wide range of difficult problems when parameterized by twin-cover. The advantage of twin-cover over vertex cover is that it imposes a lesser restriction on the graph structure and attains low values even on dense graphs. Apart from introducing the parameter itself, this article provides a number of new FPT algorithms parameterized by twin-cover with a special emphasis on solving problems which are not in FPT even when parameterized by tree-width. It also shows that MS1 model checking can be done in elementary FPT time parameterized by twin-cover and discusses the field of kernelization.