Search Results

Documents authored by Awofeso, Christine

Artifact
Software
DOI: 10.4230/artifacts.23612
chrisateen/admissibillity-rust

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

Abstract
Cite as

Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl. chrisateen/admissibillity-rust (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23612,
   title = {{chrisateen/admissibillity-rust}}, 
   author = {Awofeso, Christine and Greaves, Patrick and Lachish, Oded and Reidl, Felix},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:71c063dd72478472ce6c4dbec0805028be8003dd;origin=https://github.com/chrisateen/admissibillity-rust;visit=swh:1:snp:855eb3980d829fc685bc267ba6b84761eed00388;anchor=swh:1:rev:73669f38ba4edcc4d6cde548504d34131004c93f}{\texttt{swh:1:dir:71c063dd72478472ce6c4dbec0805028be8003dd}} (visited on 2025-07-15)},
   url = {https://github.com/chrisateen/admissibillity-rust},
   doi = {10.4230/artifacts.23612},
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.3
A Practical Algorithm for 2-Admissibility

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

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
The 2-admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, like the weak/strong 2-colouring numbers or the maximum density of graphs that appear as 1-subdivisions, the 2-admissibility can be computed in polynomial time. However, so far these results are theoretical only and no practical implementation to compute the 2-admissibility exists. Here we present an algorithm which decides whether the 2-admissibility of an input graph G is at most p in time O(p⁴ |V(G)|) and space O(|E(G)| + p²). The simple structure of the algorithm makes it easy to implement. We evaluate our implementation on a corpus of 214 real-world networks and find that the algorithm runs efficiently even on networks with millions of edges, that it has a low memory footprint, and that indeed many networks have a small 2-admissibility.
Cite as

Christine Awofeso, Patrick Greaves, Oded Lachish, and Felix Reidl. A Practical Algorithm for 2-Admissibility. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{awofeso_et_al:LIPIcs.SEA.2025.3,
  author =	{Awofeso, Christine and Greaves, Patrick and Lachish, Oded and Reidl, Felix},
  title =	{{A Practical Algorithm for 2-Admissibility}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.3},
  URN =		{urn:nbn:de:0030-drops-232413},
  doi =		{10.4230/LIPIcs.SEA.2025.3},
  annote =	{Keywords: Sparse graphs, admissibility}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.15
Testing C_k-Freeness in Bounded Admissibility Graphs

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

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study C_k-freeness in sparse graphs from a property testing perspective, specifically for graph classes with bounded r-admissibility. Our work is motivated by the large gap between upper and lower bounds in this area: C_k-freeness is known to be testable in planar graphs [Czumaj and Sohler, 2019], but not in graphs with bounded arboricity for k > 3 [Talya Eden et al., 2024]. There are a large number of interesting graph classes that include planar graphs and have bounded arboricity (e.g. classes excluding a minor), calling for a more fine-grained approach to the question of testing C_k-freeness in sparse graph classes. One such approach, inspired by the work of Nesetril and Ossona de Mendez [Nešetřil and {Ossona de Mendez}, 2012], is to consider the graph measure of r-admissibility, which naturally forms a hierarchy of graph families A₁ ⊃ A₂ ⊃ … ⊃ A_∞ where A_r contains all graph classes whose r-admissibility is bounded by some constant. The family A₁ contains classes with bounded arboricity, the class A_∞ contains classes like planar graphs, graphs of bounded degree, and minor-free graphs. Awofeso ηl [Awofeso et al., 2025] recently made progress in this direction. They showed that C₄- and C₅-freeness is testable in A₂. They further showed that C_k-freeness is not testable in A_{⌊k/2⌋ -1} and conjectured that C_k-freeness is testable in A_{⌊k/2⌋}. In this work, we prove this conjecture: C_k-freeness is indeed testable in graphs of bounded ⌊k/2⌋-admissibility.
Cite as

Christine Awofeso, Patrick Greaves, Oded Lachish, Amit Levi, and Felix Reidl. Testing C_k-Freeness in Bounded Admissibility Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{awofeso_et_al:LIPIcs.ICALP.2025.15,
  author =	{Awofeso, Christine and Greaves, Patrick and Lachish, Oded and Levi, Amit and Reidl, Felix},
  title =	{{Testing C\underlinek-Freeness in Bounded Admissibility Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{15:1--15:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.15},
  URN =		{urn:nbn:de:0030-drops-233926},
  doi =		{10.4230/LIPIcs.ICALP.2025.15},
  annote =	{Keywords: Property Testing, Sparse Graphs, Cycle, Admissibility}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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