Narrow sieves for parameterized paths and packings

DOI10.1016/J.JCSS.2017.03.003zbMATH Open1370.68321arXiv1007.1161OpenAlexW2596605817MaRDI QIDQ2396725FDOQ2396725

Authors: Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto 

Publication date: 24 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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"orklund (STACS 2010, FOCS 2010).

Full work available at URL: https://arxiv.org/abs/1007.1161

Recommendations

• Algorithms – ESA 2004
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Improved algorithms for path, matching, and packing problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

zbMATH Keywords

randomized algorithmdeterminantgraph algorithm\(k\)-pathsieveedge coloringpolynomial identity testingset packingmultidimensional matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Cites Work

• The Factorization of Linear Graphs
• A faster parameterized algorithm for set packing
• A probabilistic remark on algebraic program testing
• Which problems have strongly exponential complexity?
• Narrow sieves for parameterized paths and packings
• Parametrized complexity theory.
• Constrained multilinear detection and generalized graph motifs
• A Remark on Stirling's Formula
• Mixing Color Coding-Related Techniques
• Faster Algebraic Algorithms for Path and Packing Problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• The NP-Completeness of Edge-Coloring
• Color-coding
• An efficient parameterized algorithm for m-set packing
• On the completeness of a generalized matching problem
• Graph-Theoretic Concepts in Computer Science
• Looking at the stars
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Title not available (Why is that?)
• On Linear Time Minor Tests with Depth-First Search
• Set partitioning via inclusion-exclusion
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• On limited nondeterminism and the complexity of the V-C dimension
• NP completeness of finding the chromatic index of regular graphs
• A parameterized perspective on packing paths of length two
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Divide-and-Color
• Systems of distinct representatives and linear algebra
• Parameterized and Exact Computation
• Title not available (Why is that?)
• Spotting trees with few leaves
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Determinant sums for undirected Hamiltonicity
• Exact covers via determinants
• Colorings with few colors: counting, enumeration and combinatorial bounds

Cited In (73)

• Title not available (Why is that?)
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Parameterized Algorithms and Kernels for Rainbow Matching
• Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
• Spotting trees with few leaves
• Finding Detours is Fixed-Parameter Tractable
• Going Far from Degeneracy
• Title not available (Why is that?)
• Randomized parameterized algorithms for co-path set problem
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Toward randomized testing of \(q\)-monomials in multivariate polynomials
• Computing paths of large rank in planar frameworks deterministically
• Decomposition of Map Graphs with Applications.
• Counting Paths and Packings in Halves
• Kernel bounds for path and cycle problems
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• The \(k\)-distinct language: parameterized automata constructions
• The \(k\)-distinct language: parameterized automata constructions
• Parameterized Pre-Coloring Extension and List Coloring Problems
• Randomised enumeration of small witnesses using a decision oracle
• Exponential approximation schemata for some network design problems
• Constrained multilinear detection and generalized graph motifs
• Parameterized approximation algorithms for packing problems
• The maximum binary tree problem
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Packing paths: recycling saves time
• Parameterized algorithms and kernels for rainbow matching
• A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Faster deterministic parameterized algorithm for \(k\)-path
• Spotting trees with few leaves
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• Randomized parameterized algorithms for the kidney exchange problem
• Faster algorithms for finding and counting subgraphs
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• Detours in directed graphs
• Improved algorithms for path, matching, and packing problems
• Enumerating the edge-colourings and total colourings of a regular graph
• Deterministic parameterized algorithms for the graph motif problem
• Tight Lower Bounds for List Edge Coloring
• A parameterized perspective on packing paths of length two
• Narrow sieves for parameterized paths and packings
• Algorithms – ESA 2004
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• An improved kernel for planar vertex-disjoint triangle packing
• Gerrymandering on graphs: computational complexity and parameterized algorithms
• A Parameterized Perspective on Packing Paths of Length Two
• Parameterized algorithms for the module motif problem
• Kernel bounds for path and cycle problems
• Parameterized analysis and crossing minimization problems
• Long directed \((s,t)\)-path: FPT algorithm
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• Mixing Color Coding-Related Techniques
• Faster Algebraic Algorithms for Path and Packing Problems
• Parameterized Counting and Cayley Graph Expanders
• Deterministic algorithms for matching and packing problems based on representative sets
• Limits and Applications of Group Algebras for Parameterized Problems
• Dealing with several parameterized problems by random methods
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Partial information network queries
• Title not available (Why is that?)
• The Maximum Binary Tree Problem.
• Improved parameterized algorithms for network query problems
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Algorithms for topology-free and alignment network queries
• Kernels for packing and covering problems
• Parameterized algorithms for list \(K\)-cycle
• Improved Algorithms for Several Parameterized Problems Based on Random Methods
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs

This page was built for publication: Narrow sieves for parameterized paths and packings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396725)