A color-avoiding approach to subgraph counting in bounded expansion classes Article Swipe

MAKE IMPACT

Felix Reidl , Blair D. Sullivan · YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2001.05236

We present an algorithm to count the number of occurrences of a pattern graph $H$ as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs in 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(4^{h^2}h (\text{wcol}_h(G)+1)^{h^3} |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(4^{h^2}h \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 [11], our algorithm provides a promising alternative to algorithms using the traditional $p$-treedepth colouring framework [13]. We describe preliminary experimental results from an initial open source implementation which highlight its potential.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2001.05236

PDF

https://arxiv.org/pdf/2001.05236

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4287904070

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4287904070

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2001.05236

Digital Object Identifier

Title

A color-avoiding approach to subgraph counting in bounded expansion classes

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2020

Year of publication

Publication date

2020-01-15

Full publication date if available

Authors

Felix Reidl, Blair D. Sullivan

List of authors in order

Landing page

https://arxiv.org/abs/2001.05236

Publisher landing page

PDF URL

https://arxiv.org/pdf/2001.05236

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2001.05236

Direct OA link when available

Concepts

Combinatorics, Bounded function, Graph, Order (exchange), Mathematics, Induced subgraph, Running time, Time complexity, Discrete mathematics, Algorithm, Economics, Vertex (graph theory), Mathematical analysis, Finance

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload