Computing complexity measures of degenerate graphs

Pål Grønås Drange, Patrick Greaves, Irene Muzi +1

We show that the VC-dimension of a graph can be computed in time $n^{\log d+1}{d}^{O(d)}$, where $d$ is the degeneracy of the input graph. The core idea of our algorithm is a data s…