Counting Patterns in Degenerate Graphs in Constant Space
Balagopal Komarath Department of Computer Science IIT Gandhinagar, India [email protected] Anant Kumar Department of Computer Science IIT Gandhinagar, India [email protected] Akash Pareek Department of Computer Science Université Libre de Bruxelles, Belgium [email protected] · 2025
Read Counting Patterns in Degenerate Graphs in Constant Space by Balagopal Komarath Department of Computer Science IIT Gandhinagar, India [email protected] Anant Kumar Department of Computer Science IIT Gandhinagar, India [email protected] Akash Pareek Department of Computer Science Université Libre de Bruxelles, Belgium [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04258.txt.
Introduction
Balagopal Komarath, Anant Kumar, and Akash Pareek study the space cost of counting graph patterns inside degenerate host graphs, where pattern counting by dynamic programming over decomposition trees traditionally needs polynomial space. Their new parameter, DAG treedepth, unlocks divide-and-conquer algorithms that run in constant space.
Building on the induced-minor characterization that separates treewidth one patterns by forbidden long induced cycles, the team characterize patterns of DAG treedepth at most two through induced minors. Every pattern graph on at most nine vertices can be counted within their constant-space framework as well, extending a recent subquadratic-time result. Memory, not just time, becomes a design axis for pattern counting.
Catalog record
| CREATOR | Balagopal Komarath Department of Computer Science IIT Gandhinagar, India [email protected] Anant Kumar Department of Computer Science IIT Gandhinagar, India [email protected] Akash Pareek Department of Computer Science Université Libre de Bruxelles, Belgium [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04258
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counting Patterns in Degenerate Graphs in Constant Space Balagopal Komarath Department of Computer Science IIT Gandhinagar, India [email protected] Anant Kumar Department of Computer Science IIT Gandhinagar, India [email protected] Akash Pareek Department of Computer Science Université Libre de Bruxelles, Belgium [email protected] Abstract For an arbitrary, fixed graph (pattern graph), we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms from the pattern graph to n n -vertex, d d -degenerate graphs as input. Recent work by Bressan (Algorithmica, 2021) has shown that this problem has efficient dynamic programming algorithms using a graph parameter called DAG treewidth. Bressan used DAG treewidth to design a fast algorithm for counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms that use polynomial space. Bera, Gishboliner, Levanzov, Seshadhri, and Shapira (SODA, 2021) provided a characterization of graphs with DAG treewidth one. In this paper, we introduce a new graph parameter called DAG treedepth and show that it yields efficient divide and conquer algorithms that use only constant space (in the unit-cost RAM model). Specifically, we show: • An algorithm for counting subgraphs isomorphic to sparse pattern graphs using only constant space. • We derive an induced minor-based characterization for graphs of DAG treedepth up to two. • For pattern graphs upto nine vertices, the induced subgraphs can be counted in O ( n 3 ) O(n^{3}) time using constant space. • An algorithm for counting induced subgraphs that matches the running time given by Bressan but only uses constant space. Apart from the DAG treedepth result, we also focus on DAG treewidth. For DAG treewidth, we show that we can count homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms faster than Bressan’s algorithm (2021). We further show that for all pattern graphs up to 11 vertices, we can count induced subgraphs in quadratic time. Beyond these algorithmic results, we also analyze DAG treedepth structurally and compare it with treedepth. We also show that DAG treedepth and DAG treewidth are upper- and lower-bounded by treedepth and treewidth of graphs from an associated family of graphs. 1 Introduction For simple, undirected graphs G (host) and H (pattern), we consider the problem of counting the number of occurrences of H in G under the following three fundamental notions of containment. 1. The number of subgraphs of G isomorphic to H . That is, the cardinality of \{(V^{\prime},E^{\prime})\mid(V^{\prime},E^{\prime})\cong G,V^{\prime}\subseteq V(G),E^{\prime}\subseteq E(G)\} . 2. The number of induced subgraphs of G isomorphic to H . That is, the cardinality of \{G[S]\mid S\subseteq V(G)\} , where G[S]=(S,\{\{u,v\}\in E(G)\mid u,v\in S\}) is the subgraph of G induced by vertices in S . 3. The number of homomorphisms from H to G . That is, the cardinality of \{\phi:V(H)\mapsto V(G)\mid\{u,v\}\in E(H)\text{ if and only if }\{\phi(u),\phi(v)\}\in E(G)\text{ for all }u,v\} . Counting subgraphs and homomorphisms is at the heart of many problems in combinatorics, database theory, and network analysis [ FG04 , Lov12 , ANRD15 , CDM17b , DK25 , KNOZ25 ] . These problems capture fundamental questions such as detecting specific patterns in large networks, evaluating conjunctive queries. When the host graph G is unrestricted, the complexity of such counting tasks is well understood, as it is closely tied to the structural measures of the pattern graph H . In particular, the running time for counting subgraphs is governed by the treewidth of H in the setting of unrestricted space, and by the treedepth of H when constant space is imposed [ DST02 , KKMS23 ] . However, in many real-world settings, host graphs are not arbitrary but exhibit additional structure such as sparsity or bounded degeneracy [ PS20 , JSP15 ] . The class of d -degenerate graphs provides a natural way to model such sparse networks. A graph is said to be d -degenerate if every subgraph contains a vertex of degree at most d . This family includes many important graph classes, such as planar graphs, graphs excluding a fixed minor and, preferential attachment graphs [ Ses23 ] . Studying counting problems on degenerate graphs can therefore lead to more refined algorithmic bounds that better reflect the structure of real data. In this direction, Bressan [ B21 ] introduced a new structural parameter of the pattern graph, called the DAG treewidth , and demonstrated that when the host graph G is d -degenerate, counting homomorphisms can be performed significantly faster for patterns of small DAG treewidth. More precisely: Theorem 1 If the DAG treewidth of a k -vertex graph H is w , then we can count the number of homomorphisms from H to any n -vertex, d -degenerate G in time O(f(k,d)n^{w}) . Bressan’s algorithm for counting homomorphisms is based on a dynamic programming (DP) approach, which is similar to treewidth-based DP algorithms. By analyzing DAG treewidth structurally, Bressan [ B21 ] further showed that, for any k -vertex pattern, we can count the number of induced subgraphs in time O(f(k,d)n^{k/4}) . Bera, Pashanasangi, and Seshadhri [ BPS21 ] used DAG-treewidth to characterized the set of patterns countable in linear-time by deriving induced minor obstructions for graphs of DAG treewidth 1 . They showed that if the largest induced cycle in H has length at most 5, then there is a near-linear time algorithm for counting H -homomorphisms in bounded degeneracy graphs. More works on studying (near) linear-time algorithms for bounded degeneracy graphs includes [ BR22 , BGLS22 , PPS22 , PPS25 ] . Despite this progress, the study of quadratic-time algorithms for bounded-degeneracy graphs remains relatively unexplored. One reason could be that the structural understanding of DAG treewidth quickly becomes intractable. As we show later in the paper, even deciding whether a DAG H has dtw(H)\leq 2 is NP-complete. Formally, Theorem 2 Let H be a DAG, then deciding whether \operatorname{dtw}(H)\leq 2 is NP -complete. This hardness result suggests that DAG treewidth may not be the right parameter for capturing tractable classes beyond linear time in bounded-degeneracy graphs. Thereofore, a natural question is whether or not there is an analogue to treedepth for counting homomorphisms in d -degenerate graphs. To this end, we aim to design a divide-and-conquer algorithm that operates in constant space. We consider the pattern graph and degeneracy of host graph as fixed. Therefore, if the space only depends on the pattern graph and degeneracy, we regard it as constant-space. To achieve this, we define a new parameter called DAG treedepth (dtd), analogous to treedepth. Unlike the DAG treewidth parameter, deciding whether a DAG H has dtd(H)\leq k for some constant k is in XP. Informally, we show the following. Theorem 3 Let k be a constant. Given a DAG H , it can be verified in O(n^{f(k)}) time whether dtd(H)\leq k or not, where f(k) is some computable function. 1.1 Our Results We begin by introducing a new structural parameter, called the DAG treedepth (see Definition 15 ), which serves as a natural analogue of treedepth. The DAG treedepth parameter enables the design of efficient, constant-space, divide-and-conquer algorithms for counting homomorphisms into d -degenerate host graphs. In particular, we establish the following result: Theorem 4 Let d be some constant. If DAG treedepth of a k -vertex graph H is t , then there is an O(n^{t}) -time, constant space algorithm