2026-07-23T00:23:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9965 2024-03-06T10:45:13Z ddc:004 open_access

Counting Connected Subgraphs with Maximum-Degree-Aware Sieving Björklund, Andreas Husfeldt, Thore Kaski, Petteri Koivisto, Mikko graph embedding k-path subgraph counting maximum degree We study the problem of counting the isomorphic occurrences of a k-vertex pattern graph P as a subgraph in an n-vertex host graph G. Our specific interest is on algorithms for subgraph counting that are sensitive to the maximum degree Delta of the host graph. Assuming that the pattern graph P is connected and admits a vertex balancer of size b, we present an algorithm that counts the occurrences of P in G in O ((2 Delta-2)^{(k+b)/2} 2^{-b} n/(Delta) k^2 log n) time. We define a balancer as a vertex separator of P that can be represented as an intersection of two equal-size vertex subsets, the union of which is the vertex set of P, and both of which induce connected subgraphs of P. A corollary of our main result is that we can count the number of k-vertex paths in an n-vertex graph in O((2 Delta-2)^{floor[k/2]} n k^2 log n) time, which for all moderately dense graphs with Delta <= n^{1/3} improves on the recent breakthrough work of Curticapean, Dell, and Marx [STOC 2017], who show how to count the isomorphic occurrences of a q-edge pattern graph as a subgraph in an n-vertex host graph in time O(q^q n^{0.17q}) for all large enough q. Another recent result of Brand, Dell, and Husfeldt [STOC 2018] shows that k-vertex paths in a bounded-degree graph can be approximately counted in O(4^kn) time. Our result shows that the exact count can be recovered at least as fast for Delta<10. Our algorithm is based on the principle of inclusion and exclusion, and can be viewed as a sparsity-sensitive version of the "counting in halves"-approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Björklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.17 urn:nbn:de:0030-drops-99655 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.17 eng https://creativecommons.org/licenses/by/3.0/legalcode