2026-08-07T04:49:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19433 2024-03-06T11:04:02Z ddc:004 open_access

Computing Complexity Measures of Degenerate Graphs Drange, Pål Grønås Greaves, Patrick Muzi, Irene Reidl, Felix vc-dimension datastructure degeneracy enumerating 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 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 algorithm 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pål Grønås Drange and Patrick Greaves and Irene Muzi and Felix Reidl 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.14 urn:nbn:de:0030-drops-194333 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.14 eng https://creativecommons.org/licenses/by/4.0/legalcode