Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
复制标题
通过打包计算细子图比中间相遇时间更快
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Lukasz Kowalik
中科院分区：
文献类型：
--
作者：
Andreas Björklund;P. Kaski;Lukasz Kowalik
Vassilevska和Williams(Stoc‘09)展示了如何在时间nk/2+O(1)内计算n-顶点图中k个顶点上的简单路径和k/2条边上的匹配。同年，Koutis和Williams(ICALP‘09)和Björcround等人给出了两种具有相同运行时间的不同算法。(ESA‘09)，通过nst/2+O(1)-用于计算从给定的n元宇宙的S大小的子集族中提取的成对不交集的t元组的时间算法。不久之后，Alon和Gutner(Talg‘10)证明了当用颜色编码计数时，这些问题有Ω(n⌊st/2⌋)和Ω(n⌊k/2⌋)的下界。这里，我们证明了一个人可以做得更好--我们证明了“中间相遇”指数st/2可以被击败，并给出了一个算法，该算法在时间n0.45470382st+O(1)内计算t是3的倍数。这意味着在n0.45470382k+2p+O(1)时间内计算n-顶点图中k个固定子图的出现次数和路径宽度p≪k的算法，改进了上述三种路径和匹配算法，并绕过了颜色编码的下界。我们还给出了当S=2，3，4时不相交的S集的t元组计数的改进的界。我们的算法使用快速矩阵乘法。我们提出了一个论点，即这是必要的，以低于中间相遇的障碍。
Vassilevska and Williams (STOC’09) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-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 Björklund 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 Ω(n⌊ st/2⌋) and Ω(n⌊ k/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 p ≪ k 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.
DOI：
10.1007/978-3-642-39206-1_30
发表时间：
2013-07
期刊：
--
影响因子：
--
作者：
Radu Curticapean
通讯作者：
Radu Curticapean