Narrow sieves for parameterized paths and packings

作者：

Highlights：

• We present faster algorithms for classic problems on paths and packings.

• The algorithms are randomized, fixed-parameter tractable, and take polynomial space.

• We also present a faster algorithm for the edge-coloring problem in regular graphs.

• We generalize a recently studied algebraic approach.

摘要

•We present faster algorithms for classic problems on paths and packings.•The algorithms are randomized, fixed-parameter tractable, and take polynomial space.•We also present a faster algorithm for the edge-coloring problem in regular graphs.•We generalize a recently studied algebraic approach.

论文关键词：Determinant,Edge coloring,Graph algorithm,k-Path,Multidimensional matching,Sieve,Set packing,Polynomial identity testing,Randomized algorithm

论文评审过程：Received 24 August 2016, Revised 28 February 2017, Accepted 1 March 2017, Available online 18 March 2017, Version of Record 11 April 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.03.003