Narrow sieves for parameterized paths and packings

• DOI: 10.1016/j.jcss.2017.03.003
• Publication Date: 2017-03-18T20:15:21Z
• Authors: Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto
• Keywords: FOS: Computer and information sciences; Set packing; Sieve; Determinant; 0102 computer and information sciences; 01 natural sciences; NP-COMPLETENESS; Determinant Edge coloring; Computer Science - Data Structures and Algorithms; COLOR; Data Structures and Algorithms (cs.DS); Edge coloring; ta113; Polynomial identity testing; Randomized algorithm; COMPLEXITY; Computer and information sciences; ALGORITHMS; Graph algorithm; Multidimensional matching; DISJOINT TRIANGLES; TIME; SET PACKING; GRAPH; k-Path

We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space; the constant bases of the exponentials are significantly smaller than in previous works. For example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with $d$ colors in time within a polynomial factor of O(2^{(d-1)n/2}). Our techniques build upon and generalize some recently published ideas by I. Koutis (ICALP 2009), R. Williams (IPL 2009), and A. Bj��rklund (STACS 2010, FOCS 2010).