DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2025.12

Results on H-Freeness Testing in Graphs of Bounded r-Admissibility

Authors: Christine Awofeso, Patrick Greaves, Oded Lachish, and Felix Reidl

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract

We study the property of H-freeness in graphs with known bounded average degree, i.e. the property of a graph not containing some graph H as a subgraph. H-freeness is one of the fundamental graph properties that has been studied in the property testing framework. Levi [Reut Levi, 2021] showed that triangle-freeness is testable in graphs of bounded arboricity, which is a superset of e.g. planar graphs or graphs of bounded degree. Complementing this result is a recent preprint [Talya Eden et al., 2024] by Eden ηl which shows that, for every r ≥ 4, C_r-freeness is not testable in graphs of bounded arboricity. We proceed in this line of research by using the r-admissibility measure that originates from the field of structural sparse graph theory. Graphs of bounded 1-admissibility are identical to graphs of bounded arboricity, while graphs of bounded degree, planar graphs, graphs of bounded genus, and even graphs excluding a fixed graph as a (topological) minor have bounded r-admissibility for any value of r [Nešetřil and Ossona de Mendez, 2012]. In this work we show that H-freeness is testable in graphs with bounded 2-admissibility for all graphs H of diameter 2. Furthermore, we show the testability of C₄-freeness in bounded 2-admissible graphs directly (with better query complexity) and extend this result to C₅-freeness. Using our techniques it is also possible to show that C₆-freeness and C₇-freeness are testable in graphs with bounded 3-admissibility. The formal proofs will appear in the journal version of this paper. These positive results are supplemented with a lower bound showing that, for every r ≥ 4, C_r-freeness is not testable for graphs of bounded (⌊r/2⌋ - 1)-admissibility. This lower bound will appear in the journal version of this paper. This implies that, for every r > 0, there exists a graph H of diameter r+1, such that H-freeness is not testable on graphs with bounded r-admissibility. These results lead us to the conjecture that, for every r > 4, and t ≤ 2r+1, C_t-freeness is testable in graphs of bounded r-admissibility, and for every r > 2, H-freeness for graphs H of diameter r is testable in graphs with bounded r-admissibility.

Cite as

Christine Awofeso, Patrick Greaves, Oded Lachish, and Felix Reidl. Results on H-Freeness Testing in Graphs of Bounded r-Admissibility. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{awofeso_et_al:LIPIcs.STACS.2025.12,
  author =	{Awofeso, Christine and Greaves, Patrick and Lachish, Oded and Reidl, Felix},
  title =	{{Results on H-Freeness Testing in Graphs of Bounded r-Admissibility}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.12},
  URN =		{urn:nbn:de:0030-drops-228378},
  doi =		{10.4230/LIPIcs.STACS.2025.12},
  annote =	{Keywords: Property Testing, Sparse Graphs, Degeneracy, Admissibility}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2023.14

Computing Complexity Measures of Degenerate Graphs

Authors: Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract

We show that the VC-dimension of a graph can be computed in time n^{⌈log d+1⌉} d^{O(d)}, where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specific subset of vertices inside of a (small) query set. The construction of this data structure takes time O(d2^dn), afterwards queries can be computed efficiently using fast Möbius inversion. This data structure turns out to be useful for a range of tasks, especially for finding bipartite patterns in degenerate graphs, and we outline an efficient algorithm for counting the number of times specific patterns occur in a graph. The largest factor in the running time of this algorithm is O(n^c), where c is a parameter of the pattern we call its left covering number. Concrete applications of this algorithm include counting the number of (non-induced) bicliques in linear time, the number of co-matchings in quadratic time, as well as a constant-factor approximation of the ladder index in linear time. Finally, we supplement our theoretical results with several implementations and run experiments on more than 200 real-world datasets - the largest of which has 8 million edges - where we obtain interesting insights into the VC-dimension of real-world networks.

Cite as

Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing Complexity Measures of Degenerate Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.IPEC.2023.14,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Greaves, Patrick and Muzi, Irene and Reidl, Felix},
  title =	{{Computing Complexity Measures of Degenerate Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.14},
  URN =		{urn:nbn:de:0030-drops-194333},
  doi =		{10.4230/LIPIcs.IPEC.2023.14},
  annote =	{Keywords: vc-dimension, datastructure, degeneracy, enumerating}
}

Search Results

Documents authored by Greaves, Patrick

Results on H-Freeness Testing in Graphs of Bounded r-Admissibility

Abstract

Cite as

Computing Complexity Measures of Degenerate Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message