In this study, we explore the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms in an $n$-vertex, $d$-degenerate host graph for a fixed pattern graph. Bressan (Algorithmica, 2021) introduced the concept of DAG treewidth and demonstrated 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 allows efficient divide-and-conquer algorithms for counting homomorphisms in $d$-degenerate host graphs using only constant space. Bera et al. (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 demonstrate 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. Furthermore, 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's algorithm. When polynomial space is permitted, we also show that homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms can be counted faster than Bressan's algorithm. Additionally, we establish several other results related to DAG treewidth and DAG treedepth that may be of independent interest.
Blogger's Review: This paper significantly advances the study of counting algorithms for degenerate graphs in constant space by introducing the new parameter DAG treedepth. The efficiency of these algorithms holds great importance for large-scale graph processing applications, making it a valuable contribution to both theoretical frameworks and practical optimizations in graph algorithms.