2020/01/15 by Felix Reidl, Reidl, Felix, Blair D. Sullivan +1
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2001.05236
openalex publication_date 2020/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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(‖ C‖ ⋅ h wcolh(\mathbb G)h-1 |G|), where wcolh(\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(4h2h (wcolh(G)+1)h3 |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(‖ C‖ ⋅ h colh(\mathbb G)h-1 |G|), resulting in an overall complexity of O(4h2h colh(G)h2 |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.