Search Results

Documents authored by Greaves, Patrick


Document
Computing Complexity Measures of Degenerate Graphs

Authors: Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
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.

Cite as

Pål Grønås Drange, Patrick Greaves, Irene Muzi, and Felix Reidl. Computing Complexity Measures of Degenerate Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{drange_et_al:LIPIcs.IPEC.2023.14,
  author =	{Drange, P\r{a}l Gr{\o}n\r{a}s and Greaves, Patrick and Muzi, Irene and Reidl, Felix},
  title =	{{Computing Complexity Measures of Degenerate Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.14},
  URN =		{urn:nbn:de:0030-drops-194333},
  doi =		{10.4230/LIPIcs.IPEC.2023.14},
  annote =	{Keywords: vc-dimension, datastructure, degeneracy, enumerating}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail