Computing complexity measures of degenerate graphs

Felix Reidl
Patrick Greaves
Irene Muzi
Pål Grønås Drange
Abstract: We show that the VC-dimension of a graph can be computed in time $n^{\lceil\log d+1\rceil} 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 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(n^c)$, where~$c$ is a parameter of the pattern we call its \emph{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 this paper

@article{DBLP:journals/corr/abs-2308-08868, author = {P{\aa}l Gr{\o}n{\aa}s Drange and Patrick Greaves and Irene Muzi and Felix Reidl}, title = {Computing complexity measures of degenerate graphs}, journal = {CoRR}, volume = {abs/2308.08868}, year = {2023}, url = {}, doi = {10.48550/ARXIV.2308.08868}, eprinttype = {arXiv}, eprint = {2308.08868}, timestamp = {Sat, 30 Sep 2023 10:10:52 +0200}, biburl = {}, bibsource = {dblp computer science bibliography,} }

Felix Reidl

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

Patrick Greaves

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