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.

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 Creators	ORCiD
Panolan, Fahad	https://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