License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.3
URN: urn:nbn:de:0030-drops-177454
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17745/
Go to the corresponding LIPIcs Volume Portal

Seshadhri, C.

Some Vignettes on Subgraph Counting Using Graph Orientations (Invited Talk)

pdf-format:
LIPIcs-ICDT-2023-3.pdf (0.7 MB)

Abstract

Subgraph counting is a fundamental problem that spans many areas in computer science: database theory, logic, network science, data mining, and complexity theory. Given a large input graph G and a small pattern graph H, we wish to count the number of occurrences of H in G. In recent times, there has been a resurgence on using an old (maybe overlooked?) technique of orienting the edges of G and H, and then using a combination of brute-force enumeration and indexing. These orientation techniques appear to give the best of both worlds. There is a rigorous theoretical explanation behind these techniques, and they also have excellent empirical behavior (on large real-world graphs). Time and again, graph orientations help solve subgraph counting problems in various computational models, be it sampling, streaming, distributed, etc. In this paper, we give some short vignettes on how the orientation technique solves a variety of algorithmic problems.

BibTeX - Entry

@InProceedings{seshadhri:LIPIcs.ICDT.2023.3,
  author =	{Seshadhri, C.},
  title =	{{Some Vignettes on Subgraph Counting Using Graph Orientations}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{3:1--3:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17745},
  URN =		{urn:nbn:de:0030-drops-177454},
  doi =		{10.4230/LIPIcs.ICDT.2023.3},
  annote =	{Keywords: subgraph counting, graph degeneracy, homomorphism counting, graph algorithms}
}

Keywords: subgraph counting, graph degeneracy, homomorphism counting, graph algorithms
Collection: 26th International Conference on Database Theory (ICDT 2023)
Issue Date: 2023
Date of publication: 17.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI