Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and et al, . (2020) Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. In: ACM Transactions on Algorithms.

[img] Text
Algorithms.pdf - Published Version
Available under License Creative Commons Attribution.

Download (940kB)

Abstract

We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d-degenerate graph G and an integer k, outputs an independent set Y, such that for every independent set X in G of size at most k, the probability that X is a subset of Y is at least (((d+1)kk) . k(d+1))-1. The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G, a set T = s1, t1 , s2, t2, .... , s , t of terminal pairs, and an integer k, returns an induced subgraph G∗ of G that maintains all the inclusion minimal multicuts of G of size at most k and does not contain any (k+2)-vertex connected set of size 2O(k). In particular, G∗ excludes a clique of size 2O(k) as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for STABLE s-t SEPARATOR, STABLE ODD CYCLE TRANSVERSAL, and STABLE MULTICUT on general graphs, and for STABLE DIRECTED FEEDBACK VERTEX SET on d-degenerate graphs, resolving two problems left open by Marx et al. [ACM Transactions on Algorithms, 2013{. All of our algorithms can be derandomized at the cost of a small overhead in the running time. © 2020 ACM.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/0000-0001-6213-8687
Item Type: Conference or Workshop Item (Paper)
Additional Information: A preliminary version of this article has appeared in the proceedings of SODA 2018. 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), Pareto-Optimal Parameterized Algorithms (ERC Starting Grant 715744), Parameterized Approximation (ERC Starting Grant 306992), and Rigorous Theory of Preprocessing (ERC Advanced Investigator Grant 267959), and from the Norwegian Research Council via grant MULTIVAL. Saket Saurabh also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.
Uncontrolled Keywords: Independece covering family; parameterized algorithms; stable multicut; stable OCT; stable s-t separator
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 28 Oct 2022 04:25
Last Modified: 28 Oct 2022 04:25
URI: http://raiith.iith.ac.in/id/eprint/11085
Publisher URL: http://doi.org/10.1145/3379698
OA policy: https://v2.sherpa.ac.uk/id/publication/10668
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 11085 Statistics for this ePrint Item