DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.73

Testing the Independent Set Property in Hypergraphs

Authors: Elena Grigorescu, Shreya Nasa, and Cameron Seth

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

The optimal sample complexity of testing if an n-vertex graph has an independent set of size ρ n, or is ε-far from having an independent set of size ρ n, was established to be Õ(ρ³/ε²), in a notable result by Blais and Seth (SICOMP 2025). In contrast, for q-uniform hypergraphs, there is a significant gap between the best known upper and lower bounds, and there has been no progress on the problem for the last two decades. In this work, we prove a new upper bound of Õ(qρ^{2q-3}/{ε²(q-2)!²}) on the sample complexity of testing the ρ-independent set property. The previous best known upper bound was Õ(2^q q! ρ^{2q}/ε³), due to Langberg (RANDOM 2004). This establishes the optimal dependence on ε and gives an exponential improvement in the dependence on q. We prove our result via a new application of the hypergraph container method.

Cite as

Elena Grigorescu, Shreya Nasa, and Cameron Seth. Testing the Independent Set Property in Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grigorescu_et_al:LIPIcs.APPROX/RANDOM.2026.73,
  author =	{Grigorescu, Elena and Nasa, Shreya and Seth, Cameron},
  title =	{{Testing the Independent Set Property in Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{73:1--73:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.73},
  URN =		{urn:nbn:de:0030-drops-277907},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.73},
  annote =	{Keywords: independent set, property testing, hypergraph container method, hypergraph}
}

Search Results

Documents authored by Nasa, Shreya

Testing the Independent Set Property in Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message