# Computing complexity measures of degenerate graphs

arXiv: https://arxiv.org/abs/2308.08868 · HTML: https://mlsanity.com/paper/2308.08868/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2023.

## Built on by (most cited first, 1 of 1)

- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)

## Abstract (arXiv)

We show that the VC-dimension of a graph can be computed in time nlog d+1 dO(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(d2dn), afterwards queries can be computed efficiently using fast M"obius 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 algorithms for counting the number of times specific patterns occur in a graph. The largest factor in the running time of this algorithm is O(nc), 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.