EUVIMEDEUVIMED entdecken
Crossref

Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Meirav Zehavi

ACM Transactions on Algorithms · 31.07.2020 · 16 (3) · 1-31

DOI: 10.1145/3379698 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 06.06.2020. Verfasst von Daniel Lokshtanov und 4 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 48 Literaturangaben. Gefördert von: Parameterized Approximation, Pareto-Optimal Parameterized Algorithms, Norwegian Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Parameterized Approximation
  • Pareto-Optimal Parameterized Algorithms
  • Norwegian Research Council
  • Swarnajayanti Fellowship
  • European Research Council
  • Rigorous Theory of Preprocessing

Zitieren

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}
}
Kostenlos starten →