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

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Lund University
  • University of Warsaw

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.

Details

Original languageEnglish
Article number48
Pages (from-to)1-26
JournalACM Transactions on Algorithms
Volume13
Issue number4
Publication statusPublished - 1 Sep 2017
MoE publication typeA1 Journal article-refereed

    Research areas

  • Counting low pathwidth graphs, Counting matchings, Counting packings, Counting paths, FPT algorithms, Matrix multiplication, Meet in the middle

ID: 15782919