Counting Thin Subgraphs via Packings Faster Than MeetintheMiddle Time
(2014) 25th Annual ACMSIAM Symposium on Discrete Algorithms p.594603 Abstract
 Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an nvertex graph in time n^{k/2+O(1)}. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via nst/2+O(1)time algorithms for counting ttuples of pairwise disjoint sets drawn from a given family of ssized subsets of an nelement universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω(n^{⌊st/2⌋}) and Ω(n^{⌊k/2⌋}) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meetinthemiddle” exponent st/2 can be beaten and give an algorithm that counts... (More)
 Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an nvertex graph in time n^{k/2+O(1)}. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via nst/2+O(1)time algorithms for counting ttuples of pairwise disjoint sets drawn from a given family of ssized subsets of an nelement universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω(n^{⌊st/2⌋}) and Ω(n^{⌊k/2⌋}) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meetinthemiddle” exponent st/2 can be beaten and give an algorithm that counts in time n^{0.4547st+O(1)} for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an nvertex graph in n^{0.4547k+2p+O(1)} time, improving on the three mentioned algorithms for paths and matchings, and circumventing the colorcoding lower bound. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4247771
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri and Kowalik, Lukasz
 organization
 publishing date
 2014
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms
 editor
 Chekuri, Chandra
 pages
 594  603
 publisher
 Society for Industrial and Applied Mathematics
 conference name
 25th Annual ACMSIAM Symposium on Discrete Algorithms
 conference dates
 20140105
 external identifiers

 scopus:84902105509
 ISBN
 9781611973389
 DOI
 10.1137/1.9781611973402.45
 project
 Exact algorithms
 language
 English
 LU publication?
 yes
 id
 df577f11a3054916bfcaaaec4bbd98c8 (old id 4247771)
 date added to LUP
 20160404 10:53:23
 date last changed
 20211006 03:47:50
@inproceedings{df577f11a3054916bfcaaaec4bbd98c8, abstract = {Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an nvertex graph in time n^{k/2+O(1)}. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via nst/2+O(1)time algorithms for counting ttuples of pairwise disjoint sets drawn from a given family of ssized subsets of an nelement universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω(n^{⌊st/2⌋}) and Ω(n^{⌊k/2⌋}) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meetinthemiddle” exponent st/2 can be beaten and give an algorithm that counts in time n^{0.4547st+O(1)} for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an nvertex graph in n^{0.4547k+2p+O(1)} time, improving on the three mentioned algorithms for paths and matchings, and circumventing the colorcoding lower bound.}, author = {Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}, booktitle = {Proceedings of the TwentyFifth Annual ACMSIAM Symposium on Discrete Algorithms}, editor = {Chekuri, Chandra}, isbn = {9781611973389}, language = {eng}, pages = {594603}, publisher = {Society for Industrial and Applied Mathematics}, title = {Counting Thin Subgraphs via Packings Faster Than MeetintheMiddle Time}, url = {http://dx.doi.org/10.1137/1.9781611973402.45}, doi = {10.1137/1.9781611973402.45}, year = {2014}, }