Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time
(2014) 25th 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:
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 Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
- editor
- Chekuri, Chandra
- pages
- 594 - 603
- publisher
- Society for Industrial and Applied Mathematics
- conference name
- 25th Annual ACM-SIAM Symposium on Discrete Algorithms
- conference dates
- 2014-01-05
- 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
- 2016-04-04 10:53:23
- date last changed
- 2022-02-06 06:27:07
@inproceedings{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}},
booktitle = {{Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms}},
editor = {{Chekuri, Chandra}},
isbn = {{978-1-61197-338-9}},
language = {{eng}},
pages = {{594--603}},
publisher = {{Society for Industrial and Applied Mathematics}},
title = {{Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time}},
url = {{http://dx.doi.org/10.1137/1.9781611973402.45}},
doi = {{10.1137/1.9781611973402.45}},
year = {{2014}},
}