Narrow sieves for parameterized paths and packings

2010/07/07 by Andreas Björklund, Thore Husfeldt, Björklund, Andreas +5 · 4 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1007.1161

arxiv created 2010/07/07 · arxiv updated 2010/07/08

Abstract

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).

Cited by

• Weighted k-Path and Other Problems in Almost O^*(2^k) Deterministic Time via Dynamic Representative Sets
• Constructing Long Paths in Graph Streams
• (Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs
• Kronecker scaling of tensors with applications to arithmetic circuits and algorithms

Related

• On r-Simple k-Path and Related Problems Parameterized by k/r
• Designing Deterministic Polynomial-Space Algorithms by Color-Coding Multivariate Polynomials
• Parameterized Complexity of Path Set Packing
• Deterministic Parameterized Algorithms for Matching and Packing Problems
• Faster deterministic parameterized algorithm for k-Path