License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.50
URN: urn:nbn:de:0030-drops-136950
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13695/
Go to the corresponding LIPIcs Volume Portal

Lochet, William ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

Exploiting Dense Structures in Parameterized Complexity

pdf-format:
LIPIcs-STACS-2021-50.pdf (0.8 MB)

Abstract

Over the past few decades, the study of dense structures from the perspective of approximation algorithms has become a wide area of research. However, from the viewpoint of parameterized algorithm, this area is largely unexplored. In particular, properties of random samples have been successfully deployed to design approximation schemes for a number of fundamental problems on dense structures [Arora et al. FOCS 1995, Goldreich et al. FOCS 1996, Giotis and Guruswami SODA 2006, Karpinksi and Schudy STOC 2009]. In this paper, we fill this gap, and harness the power of random samples as well as structure theory to design kernelization as well as parameterized algorithms on dense structures. In particular, we obtain linear vertex kernels for Edge-Disjoint Paths, Edge Odd Cycle Transversal, Minimum Bisection, d-Way Cut, Multiway Cut and Multicut on everywhere dense graphs. In fact, these kernels are obtained by designing a polynomial-time algorithm when the corresponding parameter is at most Ω(n). Additionally, we obtain a cubic kernel for Vertex-Disjoint Paths on everywhere dense graphs. In addition to kernelization results, we obtain randomized subexponential-time parameterized algorithms for Edge Odd Cycle Transversal, Minimum Bisection, and d-Way Cut. Finally, we show how all of our results (as well as EPASes for these problems) can be de-randomized.

BibTeX - Entry

@InProceedings{lochet_et_al:LIPIcs.STACS.2021.50,
  author =	{Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Exploiting Dense Structures in Parameterized Complexity}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{50:1--50:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13695},
  URN =		{urn:nbn:de:0030-drops-136950},
  doi =		{10.4230/LIPIcs.STACS.2021.50},
  annote =	{Keywords: Dense graphs, disjoint paths, odd cycle transversal, kernels}
}

Keywords: Dense graphs, disjoint paths, odd cycle transversal, kernels
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI