Counting large patterns in degenerate graphs

Christine Awofeso, Patrick Greaves, Oded Lachish Felix Reidl · 2025

Read Counting large patterns in degenerate graphs by Christine Awofeso, Patrick Greaves, Oded Lachish Felix Reidl (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-20385.txt.

Introduction

Awofeso, Greaves, Lachish, and Reidl count small patterns inside sparse large networks. Their 2025 paper tackles subgraph counting, a basic problem in network analysis. Given a pattern graph and a host graph, count pattern copies. Counting is provably hard even for cliques or paths. Degenerate host graphs, where parts stay sparse, offer an opening.

Earlier results still grew exponentially with pattern size. The new algorithm improves the known bound for a broad pattern family. Those patterns, called (c,d)-locatable, admit a small vertex cover. Bicliques of any size belong to the family. Runtime depends only polynomially on the pattern's size. For the (1,d) case the dependence on host size becomes linear. A matching hardness result borders the tractable zone. Patterns barely outside that class are already hard to count. Plans include testing the algorithms on real-world networks.

Catalog record

CREATORChristine Awofeso, Patrick Greaves, Oded Lachish Felix Reidl
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE138 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-20385

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counting large patterns in degenerate graphs Christine Awofeso, Patrick Greaves, Oded Lachish Felix Reidl Abstract Subgraph counting is a fundamental algorithmic problem with many applications, including in the analysis of social and biological networks. The problem asks for the number of occurrences of a pattern graph H H as a subgraph of a host graph G G and is known to be computationally challenging: it is # ​ W ​ [ 1 ] \#W[1] -hard even when H H is restricted to simple structures such as cliques or paths. Curticapean and Marx (FOCS’14) show that if the graph H H has vertex cover number τ \tau , subgraph counting has time complexity O ⁡ ( | H | 2 O ⁡ ( τ ) ​ | G | τ + O ⁡ ( 1 ) ) O(|H|^{2^{O(\tau)}}|G|^{\tau+O(1)}) . This raises the question of whether this upper bound can be improved for input graphs G G from a restricted family of graphs. Earlier work by Eppstein (IPL’94) shows that this is indeed possible, by proving that when G G is a d d -degenerate graph and H H is a biclique of arbitrary size, subgraph counting has time complexity O ⁡ ( d ​ 3 d / 3 ​ | G | ) O(d3^{d/3}|G|) . We show that if the input is restricted to d d -degenerate graphs, the upper bound of Curticapean and Marx can be improved for a family of graphs H H that includes all bicliques and satisfies a property we call ( c , d ) (c,d) -locatable . Importantly, our algorithm’s running time only has a polynomial dependence on the size of H H . A key feature of ( c , d ) (c,d) -locatable graphs H H is that they admit a vertex cover of size at most c ​ d cd . We further characterize ( 1 , d ) (1,d) -locatable graphs, for which our algorithms achieve a linear running time dependence on | G | |G| , and we establish a lower bound showing that counting graphs which are barely not ( 1 , d ) (1,d) -locatable is already # ​ W ​ [ 1 ] \#\text{W}[1] -hard. We note that the restriction to d d -degenerate graphs has been a fruitful line of research leading to two very general results (FOCS’21, SODA’25) and this creates the impression that we largely understand the complexity of counting substructures in degenerate graphs. However, all aforementioned results have an exponential dependency on the size of the pattern graph H H . 1 Introduction Recall that a graph is d -degenerate iff its vertices can be ordered in such a way that every vertex has at most d neighbours preceding it in the order. Bressan and Roth [ 4 ] recently proved several lower and upper bounds related to counting substructures—subgraphs, induced subgraphs, homomorphisms—in degenerate graphs which, up to some minor factors, provide a characterisation of these problems: Given a graph H and a d -degenerate graph G , they show that counting how often H appears as a subgraph in G is possible in expected time f(|H|,d)|G|^{\im(H)} and counting how often it appears as an induced subgraph in time f(|H|,d)|G|^{\alpha(H)} , where \im(H) is the induced matching number and \alpha(H) the independence number of H . Assuming the exponential time hypothesis (ETH), Bressan and Roth further show almost matching lower bounds 1 1 1 f(|H|,d)|G|^{o(\im(H)/\log\im(H))} and f(|H|,d)|G|^{o(\alpha(H)/\log\alpha(H))} , respectively .Previous work had focused on hardness classifications for counting substructures without any degeneracy restrictions on G [ 7 , 6 , 8 ] , parameterising the treewidth of G [ 13 ] , and the generalised subgraph problem [ 15 ] . Regarding the linear-time countability of subgraphs in degenerate graphs, Bera et al . [ 3 ] proved that all graphs H on at most five vertices can be counted in time O(\|G\|d^{|H|-2}) . Moreover, they showed that counting cycles on six or more vertices is not possible in linear time unless the Triangle Detection Conjecture 2 2 2 The conjecture states that there exists a constant \delta such that any algorithm under the word-RAM model takes times at least |G\|^{1+\delta-o(1)} in expectation to detect whether G contains a triangle [ 1 ] . (TDC) fails. Bressan [ 5 ] designed an algorithm that counts subgraphs in time O(f(d,|H|)|G|^{\tau_{1}(H)}) , where \tau_{1}(H) is a width-measure called the DAG treewidth of H . Regarding lower bounds, Bera et al . [ 2 ] provided a complete characterisation of the graphs H that can be counted in linear time in a degenerate host graph as a subgraph/induced subgraph under the TDC 3 3 3 The exact characterisations are somewhat technical, but they revolve round the existence of C_{k} , k\geq 6 , as certain types of substructures in H . These results create the impression that we largely understand the complexity of counting substructures in degenerate graphs. The problem is, in all aforementioned upper bounds the running times have an exponential dependence on |H| . However, in the general case ( cf . Theorem 2.8 in [ 7 ] ), if H has vertex cover number \tau , subgraph counting can be solved in time O(|H|^{2^{O(\tau)}}|G|^{\tau+O(1)}) , and much earlier Eppstein [ 10 ] showed that when G is a d -degenerate graph and H is a biclique, subgraph counting can be solved in time O(d3^{d/3}|G|) . This leaves the question of whether the upper bound of Curticapean and Marx can be improved for a larger family of graphs than just bicliques. Our contribution: We show that if the input is restricted to d -degenerate graphs, the upper bound of Curticapean and Marx can be improved for a family of graphs H satisfying a property we call (c,d) -locatable , which includes all bicliques. Specifically, we show that for every such graph H subgraph counting can done in time O\big((cd)^{2}f(c,d)|H|^{f(c,d)}|G|^{c}\big) where f(c,d)=2^{d}(cd)^{d+1} (Theorem Theorem ( \star ) , Section 3.3 ) and as a semi-induced subgraph 4 4 4 A pattern H with vertex cover S and independent set T appears semi-induced in G if some supergraph \hat{H} obtained by only adding edges between T -vertices in H appears as an induced subgraph of G . in time O\big((cd)^{2cd+d}|G|^{c}\big) (Theorem 3.2 , Section 3.3 ). If the host graph G is bipartite, the time complexity holds for counting induced subgraphs. We note that our result is incomparable to Bressan’s algorithm, since our algorithm can count patterns with large independent sets which have unbounded DAG treewidth. To compare these results to those of Curticapean and Marx, note that the cd in our result bounds the vertex cover number \tau of H . Expressing our running time with this parameter, we have that O\big((cd)^{2}f(c,d)|H|^{f(c,d)}|G|^{c}\big) translates to O\big((\tau)^{2}f(\tau,d)|H|^{f(\tau,d)}{|G|^{\tau/d}}\big) where f(\tau,d)=2^{d}(\tau)^{d+1} and O\big((cd)^{2cd+d}|G|^{c}\big) translates to O\big((\tau)^{2\tau+d}{|G|^{\tau/d}}\big) , so in both cases this improves the exponent of |G| by a factor of 1/d . We are specifically interested in (1,d) -locatable patterns as these can be counted with only a linear dependence on |G| in the running time. We characterise these patterns (Section 3.4 ) and supplement our positive algorithmic results with a lower bound that shows that even counting

Read the complete text