A faster parameterized algorithm for PSEUDOFOREST DELETION

被引：15

作者：

Bodlaender, Hans L. ^{[1
,2
]}

Ono, Hirotaka ^{[3
]}

Otachi, Yota ^{[4
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, POB 80089, NL-3508 TB Utrecht, Netherlands

[2] Univ Technol Eindhoven, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands

[3] Nagoya Univ, Grad Sch Informat, Chikusa Ku, Furo Cho, Nagoya, Aichi 4648601, Japan

[4] Kumamoto Univ, Fac Adv Sci & Technol, Chuo Ku, 2-39-1 Kurokami, Kumamoto 8608555, Japan

来源：

DISCRETE APPLIED MATHEMATICS | 2018年 / 236卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Graph algorithms; Fixed parameter tractability; Pseudoforest; Feedback vertex set; Treewidth; FEEDBACK VERTEX SET; SMALL TREEWIDTH;

D O I：

10.1016/j.dam.2017.10.018

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3(k)nk(0(1))) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7.56(k)n(0(1))-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：42 / 56

页数：15

共 17 条

[1] A 2-approximation algorithm for the undirected feedback vertex set problem [J].

Bafna, V ;

Berman, P ;

Fujito, T .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) :289-297

[2] Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem [J].

Becker, A ;

Geiger, D .

ARTIFICIAL INTELLIGENCE, 1996, 83 (01) :167-188

[3] Randomized algorithms for the loop cutset problem [J].

Becker, A ;

Bar-Yehuda, R ;

Geiger, D .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 12 :219-234

[4] Fourier Meets Mobius: Fast Subset Convolution [J].

Bjorklund, Andreas ;

Husfeldt, Thore ;

Kaski, Petteri ;

Koivisto, Mikko .

STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, :67-74

[5] Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth [J].

Bodlaender, Hans L. ;

Cygan, Marek ;

Kratsch, Stefan ;

Nederlof, Jesper .

INFORMATION AND COMPUTATION, 2015, 243 :86-111

[6] Reduction algorithms for graphs of small treewidth [J].

Bodlaender, HL ;

van Antwerpen-de Fluiter, B .

INFORMATION AND COMPUTATION, 2001, 167 (02) :86-119

[7] A linear-time ie algorithm for finding three-decompositions of small treewidth [J].

Bodlaender, HL .

SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1305-1317

[8]

BODLAENDER HL, 2016, LIPICS, V63

[9] Solving connectivity problems parameterized by treewidth in single exponential time (Extended abstract) [J].

Cygan, Marek ;

Nederlof, Jesper ;

Pilipczuk, Marcin ;

Pilipczuk, Michal ;

van Rooij, Johan M. M. ;

Wojtaszczyk, Jakub Onufry .

2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :150-159

[10] PLANAR F-DELETION: Approximation, Kernelization and Optimal FPT Algorithms (Extended Abstract) [J].

Fomin, Fedor V. ;

Lokshtanov, Daniel ;

Misra, Neeldhara ;

Saurabh, Saket .

2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, :470-479

← 1 2 →