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.ICALP.2021.93
URN: urn:nbn:de:0030-drops-141626
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14162/
Go to the corresponding LIPIcs Volume Portal

Levi, Reut

Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n)

pdf-format:
LIPIcs-ICALP-2021-93.pdf (0.8 MB)

Abstract

We study the problem of testing triangle freeness in the general graph model. This problem was first studied in the general graph model by Alon et al. (SIAM J. Discret. Math. 2008) who provided both lower bounds and upper bounds that depend on the number of vertices and the average degree of the graph. Their bounds are tight only when d_max = O(d) and ̄{d} ≤ √n or when ̄{d} = Θ(1), where d_max denotes the maximum degree and ̄{d} denotes the average degree of the graph. In this paper we provide bounds that depend on the arboricity of the graph and the average degree. As in Alon et al., the parameters of our tester is the number of vertices, n, the number of edges, m, and the proximity parameter ε (the arboricity of the graph is not a parameter of the algorithm). The query complexity of our tester is Õ(Γ/ ̄{d} + Γ)⋅ poly(1/ε) on expectation, where Γ denotes the arboricity of the input graph (we use Õ(⋅) to suppress O(log log n) factors). We show that for graphs with arboricity O(√n) this upper bound is tight in the following sense. For any Γ ∈ [s] where s = Θ(√n) there exists a family of graphs with arboricity Γ and average degree ̄{d} such that Ω(Γ/ ̄{d} + Γ) queries are required for testing triangle freeness on this family of graphs. Moreover, this lower bound holds for any such Γ and for a large range of feasible average degrees .

BibTeX - Entry

@InProceedings{levi:LIPIcs.ICALP.2021.93,
  author =	{Levi, Reut},
  title =	{{Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n)}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{93:1--93:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14162},
  URN =		{urn:nbn:de:0030-drops-141626},
  doi =		{10.4230/LIPIcs.ICALP.2021.93},
  annote =	{Keywords: Property Testing, Triangle-Freeness}
}

Keywords: Property Testing, Triangle-Freeness
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

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