Counting Patterns in Degenerate Graphs in Constant Space
For researchers in subgraph counting, this work provides constant-space algorithms and improved time bounds for small patterns, though many results are incremental extensions of prior work.
The paper introduces DAG treedepth, a new graph parameter enabling constant-space algorithms for counting homomorphisms and induced subgraphs in d-degenerate graphs, and shows that all patterns on ≤9 vertices can be counted in O(n³) time with constant space, while patterns on ≤11 vertices can be counted in O(n²) time with polynomial space.
For a fixed pattern graph, we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms into an $n$-vertex, $d$-degenerate host graph. Bressan (Algorithmica, 2021) introduced the notion of DAG treewidth and showed that counting homomorphisms and induced subgraphs can be performed efficiently using dynamic programming that requires polynomial space. In this work, we introduce a new graph parameter, called DAG treedepth, which enables efficient divide-and-conquer algorithms for counting homomorphisms in $d$-degenerate host graphs using only constant space. Bera, Gishboliner, Levanzov, Seshadhri, and Shapira (SODA, 2021) showed that a pattern graph has DAG treewidth one if and only if it contains no induced cycle of length at least six. This induced minor characterization leads to linear-time and linear-space algorithms. Building on this line of work, we derive an induced-minor characterization of graphs with DAG treedepth at most two that uses only constant space. Recently, Paul-Pena and Seshadhri (ICALP, 2025) proved that all pattern graphs on at most nine vertices can be counted in subquadratic time using polynomial space. We show that every pattern graph on at most nine vertices can be counted as an induced subgraph in $O(n^3)$ time using only constant space. Moreover, we show that patterns on at most eleven vertices can be counted in $O(n^2)$ time using polynomial space. Finally, we present a constant-space algorithm for counting induced subgraphs that matches the running time of Bressan algorithm. We further show that, when polynomial space is allowed, homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms can be counted faster than Bressan algorithm. In addition, we establish several other results related to DAG treewidth and DAG treedepth that may be of independent interest.