A practical algorithm for 2-admissibility

Published
Christine Awofeso
Patrick Greaves
Oded Lachish
Felix Reidl
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^4 |V(G)|)$ and space $O(|E(G)| + p^2)$. 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.

Christine Awofeso

Christine is an Algo Lab PhD student. She is working on implementing algorithms for measuring graph sparsity.

Felix Reidl

Felix is a Senior Lecturer at Birkbeck. His speciality is the design of algorithms for sparse graphs.

Oded Lachish

Oded is a Reader at Birkbeck. His speciality are analysis of algorithms, in particular using the probabilistic method.

Patrick Greaves

Patrick is an Algo Lab PhD student. He is working on researching and implementing algorithms to compute sparsity measures.