Faster deterministic algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING

被引：0

作者：

Tsur, Dekel ^{[1
]}

机构：

[1] Ben Gurion Univ Negev, Dept Comp Sci, Beer Sheva, Israel

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2022年 / 44卷 / 05期

关键词：

Graph algorithms; Parameterized complexity; Branching algorithms; PARAMETERIZED ALGORITHM; FPT ALGORITHM; VERTEX; DELETION; KERNEL;

D O I：

10.1007/s10878-022-00917-3

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In the CO-PATH PACKING (resp., CO-PATH/CYCLE PACKING) problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph which is a collection of induced paths (resp., induced paths and cycles). In this paper we give deterministic O* (3(k))-time algorithms for CO-PATH PACKING and CO-PATH/CYCLE PACKING.

引用

收藏

页码：3701 / 3710

页数：10

相关论文

共 27 条

[1] Parameterised Algorithms for Deletion to Classes of DAGs [J].

Agrawal, Akanksha ;

Saurabh, Saket ;

Sharma, Roohani ;

Zehavi, Meirav .

THEORY OF COMPUTING SYSTEMS, 2018, 62 (08) :1880-1909

[2] Kernels for deletion to classes of acyclic digraphs [J].

Agrawal, Akanksha ;

Saurabh, Saket ;

Sharma, Roohani ;

Zehavi, Meirav .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 92 :9-21

[3]

Aoike Y, 2020, ARXIV

[4] On Bounded-Degree Vertex Deletion parameterized by treewidth [J].

Betzler, Nadja ;

Bredereck, Robert ;

Niedermeier, Rolf ;

Uhlmann, Johannes .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (1-2) :53-60

[5] Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property [J].

Bonnet, Edouard ;

Brettell, Nick ;

Kwon, O-joung ;

Marx, Daniel .

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, 2016, 9941 :233-244

[6]

Cerveny R., 2021, ARXIV

[7] Fixed-parameter algorithms for vertex cover P3 [J].

Chang, Maw-Shang ;

Chen, Li-Hsuan ;

Hung, Ling-Ju ;

Rossmanith, Peter ;

Su, Ping-Chen .

DISCRETE OPTIMIZATION, 2016, 19 :12-22

[8]

Chen ZZ, 2010, LECT NOTES COMPUT SC, V6124, P90, DOI 10.1007/978-3-642-14355-7_10

[9] An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion [J].

Cygan, Marek ;

Pilipczuk, Marcin ;

Pilipczuk, Michal ;

Wojtaszczyk, Jakub Onufry .

ALGORITHMICA, 2012, 64 (01) :170-188

[10] A generalization of Nemhauser and Trotter's local optimization theorem [J].

Fellows, Michael R. ;

Guo, Jiong ;

Moser, Hannes ;

Niedermeier, Rolf .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2011, 77 (06) :1141-1158