Advanced

Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time

Björklund, Andreas LU ; Kaski, Petteri and Kowalik, Lukasz (2014) 25th Annual ACM-SIAM Symposium on Discrete Algorithms In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms p.594-603
Abstract
Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-vertex 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 t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element 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 “meet-in-the-middle” 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 n-vertex 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 t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element 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 “meet-in-the-middle” 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 n-vertex graph in n^{0.4547k+2p+O(1)} time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
editor
Chekuri, Chandra
pages
594 - 603
publisher
SIAM
conference name
25th Annual ACM-SIAM Symposium on Discrete Algorithms
external identifiers
  • Scopus:84902105509
ISBN
978-1-61197-338-9
DOI
10.1137/1.9781611973402.45
project
Exact algorithms
language
English
LU publication?
yes
id
df577f11-a305-4916-bfca-aaec4bbd98c8 (old id 4247771)
date added to LUP
2014-01-13 14:40:24
date last changed
2016-10-13 04:42:39
@misc{df577f11-a305-4916-bfca-aaec4bbd98c8,
  abstract     = {Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-vertex 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 t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element 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 “meet-in-the-middle” 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 n-vertex graph in n^{0.4547k+2p+O(1)} time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.},
  author       = {Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz},
  editor       = {Chekuri, Chandra},
  isbn         = {978-1-61197-338-9},
  language     = {eng},
  pages        = {594--603},
  publisher    = {ARRAY(0xa42fe38)},
  series       = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms},
  title        = {Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time},
  url          = {http://dx.doi.org/10.1137/1.9781611973402.45},
  year         = {2014},
}