Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
ACM Transactions on Algorithms · 2020-07-31 · 16 (3) · 1-31
DOI: 10.1145/3379698 ↗At a glance
Journal article in ACM Transactions on Algorithms, published online on 2020-06-06. Written by Daniel Lokshtanov and 4 co-authors. Cited 7 times so far (Crossref); 48 references. Funded by: Parameterized Approximation, Pareto-Optimal Parameterized Algorithms, Norwegian Research Council.
Abstract (original language)
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)k k ) . k (d+1)) -1 . The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G , a set T = {s_1, t_1} , {s_2, t_2}, …. , {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 2 O(k) . In particular, G* excludes a clique of size 2 O(k) as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for S TABLE s-t S EPARATOR , S TABLE O DD C YCLE T RANSVERSAL , and S TABLE M ULTICUT on general graphs, and for S TABLE D IRECTED F EEDBACK V ERTEX S ET 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.
Funding
- Parameterized Approximation
- Pareto-Optimal Parameterized Algorithms
- Norwegian Research Council
- Swarnajayanti Fellowship
- European Research Council
- Rigorous Theory of Preprocessing
Cite
APA
Lokshtanov, D., Panolan, F., Saurabh, S., Sharma, R., & Zehavi, M. (2020). Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. ACM Transactions on Algorithms, 16(3), 1-31. https://doi.org/10.1145/3379698
Vancouver
Lokshtanov D, Panolan F, Saurabh S, Sharma R, Zehavi M. Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms. ACM Transactions on Algorithms. 2020;16(3):1-31. doi:10.1145/3379698
BibTeX
@article{Lokshtanov2020,
author = {Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
title = {Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms},
journal = {ACM Transactions on Algorithms},
year = {2020},
volume = {16},
number = {3},
pages = {1--31},
doi = {10.1145/3379698}
}
EUVIMED