Counting Connected Subgraphs with Maximum-Degree-Aware Sieving

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

15 Downloads (Pure)

Abstract

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].
Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation (ISAAC 2018)
EditorsWen-Lian Hsu, Der-Tsai Lee, Chung-Shou Liao
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Pages1-12
ISBN (Print)978-3-95977-094-1
DOIs
Publication statusPublished - 2018
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Algorithms and Computation - Jiaoxi, Taiwan, Republic of China
Duration: 16 Dec 201819 Dec 2018
Conference number: 29

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume123
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Algorithms and Computation
Abbreviated titleISAAC
CountryTaiwan, Republic of China
CityJiaoxi
Period16/12/201819/12/2018

Keywords

  • graph embedding
  • k-path
  • subgraph counting
  • maximum degree

Fingerprint Dive into the research topics of 'Counting Connected Subgraphs with Maximum-Degree-Aware Sieving'. Together they form a unique fingerprint.

Cite this