Exploring the gap between treedepth and vertex cover through vertex integrity
Exploring the gap between treedepth and vertex cover through vertex integrity
复制标题
通过顶点完整性探索树深度和顶点覆盖之间的差距
DOI：
10.1016/j.tcs.2022.03.021
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Otachi Yota
中科院分区：
文献类型：
--
作者：
Gima Tatsuya;Hanaka Tesshu;Kiyomi Masashi;Kobayashi Yasuaki;Otachi Yota
对于树宽有界的图上难以解决的问题，两个图参数树深和顶点覆盖数已被用来获得细粒度的算法和复杂性的结果。虽然在这方面的研究是成功的，我们仍然需要一个系统的方法进行进一步的研究，因为有界顶点覆盖数的图形成一个相当小的子类的有界树深的图。为了填补这个空白，我们使用另一个图形参数，顶点完整性，它被放置在上面提到的两个参数之间。对于几个图的问题，我们推广的固定参数的易处理性结果的顶点覆盖数参数的顶点完整性。我们还显示了一些更精细的复杂性对比，显示硬度与顶点的完整性或树深。
For problems intractable on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained algorithmic and complexity results. Although the studies in this direction are successful, we still need a systematic way for further investigations because the graphs of bounded vertex cover number form a rather small subclass of graphs of bounded treedepth. To fill this gap, we use another graph parameter, vertex integrity, which is placed between the two parameters mentioned above. For several graph problems, we generalize fixed-parameter tractability results parameterized by vertex cover number to the ones parameterized by vertex integrity. We also show some finer complexity contrasts by showing hardness with respect to vertex integrity or treedepth.