DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2023.40

Finding and Counting Patterns in Sparse Graphs

Authors: Balagopal Komarath, Anant Kumar, Suchismita Mishra, and Aditi Sethia

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract

We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse for many patterns. As an application to finding and counting fixed-size patterns, we discover Õ(m³)-time, constant-space algorithms for cycles of length at most 11 and Õ(m²)-time, polynomial-space algorithms for paths of length at most 10.

Cite as

Balagopal Komarath, Anant Kumar, Suchismita Mishra, and Aditi Sethia. Finding and Counting Patterns in Sparse Graphs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{komarath_et_al:LIPIcs.STACS.2023.40,
  author =	{Komarath, Balagopal and Kumar, Anant and Mishra, Suchismita and Sethia, Aditi},
  title =	{{Finding and Counting Patterns in Sparse Graphs}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.40},
  URN =		{urn:nbn:de:0030-drops-176921},
  doi =		{10.4230/LIPIcs.STACS.2023.40},
  annote =	{Keywords: Subgraph Detection and Counting, Homomorphism Polynomials, Treewidth and Treedepth, Matchings}
}

Search Results

Documents authored by Mishra, Suchismita

Finding and Counting Patterns in Sparse Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message