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

Andreas Björklund, Petteri Kaski, Lukasz Kowalik

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

11 Citations (SciVal)

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
EditorsChandra Chekuri
PublisherSociety for Industrial and Applied Mathematics
Pages594-603
ISBN (Print)978-1-61197-338-9
DOIs
Publication statusPublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms - Portland, Oregon
Duration: 2014 Jan 5 → …

Conference

Conference25th Annual ACM-SIAM Symposium on Discrete Algorithms
Period2014/01/05 → …

Subject classification (UKÄ)

  • Computer Science

Fingerprint

Dive into the research topics of 'Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time'. Together they form a unique fingerprint.

Cite this