License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.25
URN: urn:nbn:de:0030-drops-99735
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9973/
Go to the corresponding LIPIcs Volume Portal

Bishnu, Arijit ; Ghosh, Arijit ; Kolay, Sudeshna ; Mishra, Gopinath ; Saurabh, Saket

Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers

pdf-format:
LIPIcs-ISAAC-2018-25.pdf (0.5 MB)

Abstract

In this paper, we study the query complexity of parameterized decision and optimization versions of Hitting-Set. We also investigate the query complexity of Packing. In doing so, we use generalizations to hypergraphs of an earlier query model, known as BIS introduced by Beame et al. in ITCS'18. The query models considered are the GPIS and GPISE oracles. The GPIS and GPISE oracles are used for the decision and optimization versions of the problems, respectively. We use color coding and queries to the oracles to generate subsamples from the hypergraph, that retain some structural properties of the original hypergraph. We use the stability of the sunflowers in a non-trivial way to do so.

BibTeX - Entry

@InProceedings{bishnu_et_al:LIPIcs:2018:9973,
  author =	{Arijit Bishnu and Arijit Ghosh and Sudeshna Kolay and Gopinath Mishra and Saket Saurabh},
  title =	{{Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9973},
  URN =		{urn:nbn:de:0030-drops-99735},
  doi =		{10.4230/LIPIcs.ISAAC.2018.25},
  annote =	{Keywords: Query complexity, Hitting set, Parameterized complexity}
}

Keywords: Query complexity, Hitting set, Parameterized complexity
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

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