Document Open Access Logo

Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.25.pdf
  • Filesize: 461 kB
  • 12 pages

Document Identifiers

Author Details

Arijit Bishnu
  • Indian Statistical Institute, Kolkata, India
Arijit Ghosh
  • The Institute of Mathematical Sciences, Chennai, India
Sudeshna Kolay
  • Eindhoven University of Technology, Eindhoven, Netherlands
Gopinath Mishra
  • Indian Statistical Institute, Kolkata, India
Saket Saurabh
  • The Institute of Mathematical Sciences, Chennai, India

Cite As Get BibTex

Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. Parameterized Query Complexity of Hitting Set Using Stability of Sunflowers. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.25

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Query complexity
  • Hitting set
  • Parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color Coding. In Encyclopedia of Alg., pages 335-338. Springer, 2016. Google Scholar
  2. Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. In ITCS, pages 38:1-38:21, 2018. Google Scholar
  3. Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, and Saket Saurabh. Parameterized Query Complexity of Hitting Set using Stability of Sunflowers. CoRR, abs/1807.06272, 2018. URL: http://arxiv.org/abs/1807.06272.
  4. Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams. In SODA, pages 1326-1344, 2016. Google Scholar
  5. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. P. Erdős and R. Rado. Intersection Theorems for Systems of Sets. Journal of the London Mathematical Society, s1-35(1):85-90, 1960. Google Scholar
  7. Uriel Feige. On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM J. Comput., 35(4):964-984, 2006. Google Scholar
  8. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  9. Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Struct. Algorithms, 32(4):473-493, 2008. Google Scholar
  10. Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee. Set Cover in Sub-linear Time. In SODA, pages 2467-2486, 2018. Google Scholar
  11. Kazuo Iwama and Yuichi Yoshida. Parameterized Testability. TOCT, 9(4):16:1-16:16, 2018. Google Scholar
  12. Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In SODA, pages 1123-1131, 2012. Google Scholar
  13. Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In ITCS, pages 39:1-39:16, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact