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

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Standard

Counting thin subgraphs via packings faster than meet-in-the-middle time. / Björklund, Andreas; Kaski, Petteri; Kowalik, Lukasz.

julkaisussa: ACM Transactions on Algorithms, Vuosikerta 13, Nro 4, 48, 01.09.2017, s. 1-26.

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Harvard

APA

Vancouver

Author

Björklund, Andreas ; Kaski, Petteri ; Kowalik, Lukasz. / Counting thin subgraphs via packings faster than meet-in-the-middle time. Julkaisussa: ACM Transactions on Algorithms. 2017 ; Vuosikerta 13, Nro 4. Sivut 1-26.

Bibtex - Lataa

@article{6e5ee15cf3a14b5eb95d1c572994a659,
title = "Counting thin subgraphs via packings faster than meet-in-the-middle time",
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 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.",
keywords = "Counting low pathwidth graphs, Counting matchings, Counting packings, Counting paths, FPT algorithms, Matrix multiplication, Meet in the middle",
author = "Andreas Bj{\"o}rklund and Petteri Kaski and Lukasz Kowalik",
year = "2017",
month = "9",
day = "1",
doi = "10.1145/3125500",
language = "English",
volume = "13",
pages = "1--26",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
number = "4",

}

RIS - Lataa

TY - JOUR

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

AU - Björklund, Andreas

AU - Kaski, Petteri

AU - Kowalik, Lukasz

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

KW - Counting low pathwidth graphs

KW - Counting matchings

KW - Counting packings

KW - Counting paths

KW - FPT algorithms

KW - Matrix multiplication

KW - Meet in the middle

UR - http://www.scopus.com/inward/record.url?scp=85030330604&partnerID=8YFLogxK

U2 - 10.1145/3125500

DO - 10.1145/3125500

M3 - Article

VL - 13

SP - 1

EP - 26

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 4

M1 - 48

ER -

ID: 15782919