Improved FPT algorithms for deletion to forest-like structures

Gowda, K.N. and Lonkar, A. and Panolan, Fahad and Patel, V. and Saurabh, S. (2020) Improved FPT algorithms for deletion to forest-like structures. In: 31st International Symposium on Algorithms and Computation, ISAAC 2020, 14-18 December 2020, Virtual, Hong Kong.

Text
Improved_FPT_algorithms.pdf - Published Version
Available under License Creative Commons Attribution.
Download (674kB)

Abstract

TheFeedback Vertex Setproblem is undoubtedly one of the most well-studied problems inParameterized Complexity. In this problem, given an undirected graphGand a non-negative integerk, the objective is to test whether there exists a subsetS⊆V(G)of size at mostksuch thatG−Sis a forest. After a long line of improvement, recently, Li and Nederlof [SODA, 2020] designed arandomized algorithm for the problem running in timeO?(2.7k)1. In the Parameterized Complexityliterature, several problems aroundFeedback Vertex Sethave been studied. Some of theseincludeIndependent Feedback Vertex Set(where the setSshould be an independent set inG),Almost Forest DeletionandPseudoforest Deletion. InPseudoforest Deletion, eachconnected component inG−Shas at most one cycle in it. However, inAlmost Forest Deletion,the input is a graphGand non-negative integersk, `∈N, and the objective is to test whetherthere exists a vertex subsetSof size at mostk, such thatG−Sis`edges away from a forest. Inthis paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastestalgorithms for all these problems.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid.org/0000-0001-6213-8687

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

Funding This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 819416) and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Uncontrolled Keywords:

Almost forest, Cut and count, Independent feedback vertex set, Parameterized complexity, Pseudo forest, Treewidth

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

23 Nov 2022 09:57

Last Modified:

23 Nov 2022 10:00