Counting thin subgraphs via packings faster than meet-in-the-middle time
(2017) In ACM Transactions on Algorithms 13(4).- Abstract
Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time nk/2+O(1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), 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'10) showed that these problems have O(n st/2) and O(nk/2) lower bounds when counting by color coding. Here, we show that one can do better-we show that the "meet-in-the-middle" exponent st/2 can be beaten and give an algorithm that counts in time... (More)
Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time nk/2+O(1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), 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'10) showed that these problems have O(n st/2) and O(nk/2) lower bounds when counting by color coding. Here, we show that one can do better-we show that the "meet-in-the-middle" exponent st/2 can be beaten and give an algorithm that counts in time n0.45470382st+O(1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth pk in an n-vertex graph in n0.45470382k+2p+O(1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting t-tuples of disjoint s-sets for s = 2, 3, 4. Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.
(Less)
- author
- Björklund, Andreas LU ; Kaski, Petteri and Kowalik, Lukasz
- organization
- publishing date
- 2017-09-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Counting low pathwidth graphs, Counting matchings, Counting packings, Counting paths, FPT algorithms, Matrix multiplication, Meet in the middle
- in
- ACM Transactions on Algorithms
- volume
- 13
- issue
- 4
- article number
- 48
- publisher
- Association for Computing Machinery (ACM)
- external identifiers
-
- scopus:85030330604
- ISSN
- 1549-6325
- DOI
- 10.1145/3125500
- language
- English
- LU publication?
- yes
- id
- 8b7e597d-4762-493d-82a1-d47792a53120
- date added to LUP
- 2017-10-16 14:06:37
- date last changed
- 2022-02-22 06:06:26
@article{8b7e597d-4762-493d-82a1-d47792a53120,
abstract = {{<p>Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time nk/2+O(1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), 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'10) showed that these problems have O(n st/2) and O(nk/2) lower bounds when counting by color coding. Here, we show that one can do better-we show that the "meet-in-the-middle" exponent st/2 can be beaten and give an algorithm that counts in time n0.45470382st+O(1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth pk in an n-vertex graph in n0.45470382k+2p+O(1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting t-tuples of disjoint s-sets for s = 2, 3, 4. Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.</p>}},
author = {{Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}},
issn = {{1549-6325}},
keywords = {{Counting low pathwidth graphs; Counting matchings; Counting packings; Counting paths; FPT algorithms; Matrix multiplication; Meet in the middle}},
language = {{eng}},
month = {{09}},
number = {{4}},
publisher = {{Association for Computing Machinery (ACM)}},
series = {{ACM Transactions on Algorithms}},
title = {{Counting thin subgraphs via packings faster than meet-in-the-middle time}},
url = {{http://dx.doi.org/10.1145/3125500}},
doi = {{10.1145/3125500}},
volume = {{13}},
year = {{2017}},
}