A practical algorithm for 3-admissibility

The 3-admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure.

We design an algorithm that decides whether the 3-admissibility of an input graph G is at most p in time O(m p^7) and space O(n p^3), where m is the number of edges in G and n the number of vertices. To the best of our knowledge, this is the first explicit algorithm to compute the 3-admissibility.

The linear dependence on the input size in both time and space complexity, coupled with an `optimistic' design philosophy for the algorithm itself, makes this algorithm practicable, as we demonstrate with an experimental evaluation on a corpus of 217 real-world networks.

Our experimental results show, surprisingly, that the 3-admissibility of most real-world networks is not much larger than the 2-admissibility, despite the fact that the former has better algorithmic properties than the latter.