Advanced

Counting thin subgraphs via packings faster than meet-in-the-middle time

Björklund, Andreas LU ; Kaski, Petteri and Kowalik, Lukasz (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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
publisher
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
2018-01-07 12:22:38
@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>},
  articleno    = {48},
  author       = {Björklund, Andreas and Kaski, Petteri and Kowalik, Lukasz},
  issn         = {1549-6325},
  keyword      = {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    = {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},
  volume       = {13},
  year         = {2017},
}