2026-08-06T08:11:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11467 2024-03-06T10:48:06Z ddc:004 open_access

Faster Subgraph Counting in Sparse Graphs Bressan, Marco subgraph counting tree decomposition degeneracy A fundamental graph problem asks to compute the number of induced copies of a k-node pattern graph H in an n-node graph G. The fastest algorithm to date is still the 35-years-old algorithm by Nešetřil and Poljak [Nešetřil and Poljak, 1985], with running time f(k) * O(n^{omega floor[k/3] + 2}) where omega <=2.373 is the matrix multiplication exponent. In this work we show that, if one takes into account the degeneracy d of G, then the picture becomes substantially richer and leads to faster algorithms when G is sufficiently sparse. More precisely, after introducing a novel notion of graph width, the DAG-treewidth, we prove what follows. If H has DAG-treewidth tau(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d,k) * O~(n^{tau(H)}); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d,k) * n^{o(tau(H)/ln tau(H))} for all H. This result characterises the complexity of counting subgraphs in a d-degenerate graph. Developing bounds on tau(H), then, we obtain natural generalisations of classic results and faster algorithms for sparse graphs. For example, when d=O(poly log(n)) we can count the induced copies of any H in time f(k) * O~(n^{floor[k/4] + 2}), beating the Nešetřil-Poljak algorithm by essentially a cubic factor in n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco Bressan 2019 Is Part Of LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2019.6 urn:nbn:de:0030-drops-114673 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.6 eng https://creativecommons.org/licenses/by/3.0/legalcode