Counting Connected Subgraphs with MaximumDegreeAware Sieving
(2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018p.117
 Abstract
 We study the problem of counting the isomorphic occurrences of a kvertex pattern graph P as a subgraph in an nvertex 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 Delta2)^{(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 equalsize 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... (More)
 We study the problem of counting the isomorphic occurrences of a kvertex pattern graph P as a subgraph in an nvertex 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 Delta2)^{(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 equalsize 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 kvertex paths in an nvertex graph in O((2 Delta2)^{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 qedge pattern graph as a subgraph in an nvertex 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 kvertex paths in a boundeddegree 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 sparsitysensitive version of the "counting in halves"approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009]. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/188143b54842494db15b39ffd6961a90
 author
 Björklund, Andreas ^{LU} ; Husfeldt, Thore ^{LU} ; Kaski, Petteri and Koivisto, Mikko
 organization
 publishing date
 2018
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 graph embedding, kpath, subgraph counting, maximum degree
 host publication
 29th International Symposium on Algorithms and Computation (ISAAC 2018)
 pages
 1  17
 publisher
 Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 conference name
 29th International Symposium on Algorithms and Computation, ISAAC 2018<br/><br/>
 conference location
 Jiaoxi, Yilan, Taiwan, Province of China
 conference dates
 20181216  20181219
 external identifiers

 scopus:85063676476
 ISBN
 9783959770941
 DOI
 10.4230/LIPIcs.ISAAC.2018.17
 language
 English
 LU publication?
 yes
 id
 188143b54842494db15b39ffd6961a90
 date added to LUP
 20190201 08:35:06
 date last changed
 20190414 04:08:31
@inproceedings{188143b54842494db15b39ffd6961a90, abstract = {We study the problem of counting the isomorphic occurrences of a kvertex pattern graph P as a subgraph in an nvertex 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 Delta2)^{(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 equalsize 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 kvertex paths in an nvertex graph in O((2 Delta2)^{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 qedge pattern graph as a subgraph in an nvertex 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 kvertex paths in a boundeddegree 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 sparsitysensitive version of the "counting in halves"approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009].}, author = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko}, isbn = {9783959770941}, keyword = {graph embedding,kpath,subgraph counting,maximum degree}, language = {eng}, location = {Jiaoxi, Yilan, Taiwan, Province of China}, pages = {117}, publisher = {Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {Counting Connected Subgraphs with MaximumDegreeAware Sieving}, url = {http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.17}, year = {2018}, }