A Color-Avoiding Approach to Subgraph Counting in Bounded Expansion Classes.

Felix Reidl
Blair D. Sullivan
Abstract: We present an algorithm to count the number of occurrences of a pattern graph $H$ on $h$ vertices as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs in linear time, if $G$ belongs to a nowhere dense class it runs in almost-linear time. Our design choices are motivated by the need for an approach that can be engineered into a practical implementation for sparse host graphs.

Specifically, we introduce a decomposition of the pattern $H$ called a counting dag $\vec C(H)$ which encodes an order-aware, inclusion-exclusion counting method for $H$. Given such a counting dag and a suitable linear ordering $\mathbb{G}$ of $G$ as input, our algorithm can count the number of times $H$ appears as an induced subgraph in $G$ in time $O(|\vec C| \cdot h \text{wcol}_{h}(\mathbb{G})^{h-1} |G|)$, where ${\text{wcol}}h(\mathbb{G})$ denotes the maximum size of the weakly $h$-reachable sets in $\mathbb{G}$. This implies, combined with previous results, an algorithm with running time $O((3h^2 \text{wcol}{h}(G))^{h^2} |G|)$ which only takes $H$ and $G$ as input.

We note that with a small modification, our algorithm can instead use strongly $h$-reachable sets with running time $O(|\vec C| \cdot h \text{col}_{h}(\mathbb{G})^{h-1} |G|)$, resulting in an overall complexity of $O(h (3\text{col}_h(G))^{h^2} |G|)$ when only given $H$ and $G$.

Because orderings with small weakly/strongly reachable sets can be computed relatively efficiently in practice (Nadara et al.: in J Exp Algorithmics 103:14:1–14:16, 2018), our algorithm provides a promising alternative to algorithms using the traditional $p$-treedepth coloring framework (O’Brien and Sullivan in: Experimental evaluation of counting subgraph isomorphisms in classes of bounded expansion, CoRR, arXiv:1712.06690, 2017). We describe preliminary experimental results from an initial open source implementation which highlight its potential.

Cite this paper

@article{DBLP:journals/algorithmica/ReidlS23, author = {Felix Reidl and Blair D. Sullivan}, title = {A Color-Avoiding Approach to Subgraph Counting in Bounded Expansion Classes}, journal = {Algorithmica}, volume = {85}, number = {8}, pages = {2318--2347}, year = {2023}, url = {https://doi.org/10.1007/s00453-023-01096-1}, doi = {10.1007/S00453-023-01096-1}, timestamp = {Fri, 18 Aug 2023 08:46:23 +0200}, biburl = {https://dblp.org/rec/journals/algorithmica/ReidlS23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }

Felix Reidl

Felix is a Senior Lecturer at Birkbeck. His speciality is the design of algorithms for sparse graphs.