# Finding and Counting Patterns in Sparse Graphs

arXiv: https://arxiv.org/abs/2301.02569 · HTML: https://mlsanity.com/paper/2301.02569/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2023.

## Built on by (most cited first, 1 of 1)

- [Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks](https://mlsanity.com/paper/2305.19659/) (2023)

## Abstract (arXiv)

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 otilde(m3)-time footnoteotilde hides factors that are logarithmic in the input size., constant-space algorithms for cycles of length at most 11 and otilde(m2)-time, polynomial-space algorithms for paths of length at most 10.