首页> 外文期刊>Algorithmica >An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion
【24h】

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion

机译:改进的FPT算法和用于删除路径宽度一个顶点的二次核

获取原文
获取原文并翻译 | 示例

摘要

The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied Feedback Vertex Set (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196-207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7~kn~(O(1)) In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65~kn~(O(1)), thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251-260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomasse (ACM Trans. Algorithms 6(2), 2010).
机译:路径宽度一个顶点删除(POVD)问题询问,给定一个无向图G和一个整数k,是否可以从G删除最多k个顶点,以便其余图的路径宽度最多为1。这个问题可以认为是自然的。广泛研究的反馈顶点集(FVS)问题的一种变体,其中最多删除k个顶点必须导致其余图的树宽最多为1(即,森林)。最近,Philip等人。 (WG,Lecture Notes in Computer Science,vol.6410,pp.196-207,2010)启动了对POVD的参数化复杂度的研究,显示了四次核和在7〜kn〜(O(1 ))在本文中,我们通过显示二次核和时间复杂度为4.65〜kn〜(O(1))的算法来改善这些结果,与Dell和van Melkebeek(STOC)的一般结果相比,可以获得几乎严格的内核化界限,第251-260页,ACM,纽约,2010年)。由于托马斯(Thomasse),用于内核化的技术基于FVS的二次内核(ACM Trans。Algorithms 6(2),2010)。

著录项

  • 来源
    《Algorithmica》 |2012年第1期|p.170-188|共19页
  • 作者单位

    Faculty of Mathematics, Computer Science and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland;

    Faculty of Mathematics, Computer Science and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland;

    Faculty of Mathematics, Computer Science and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland;

    Faculty of Mathematics, Computer Science and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    fixed parameter tractability; kernelization; pathwidth; caterpillar graph;

    机译:固定参数易处理性;内核化;路径宽度;毛毛虫图;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号