Narrow sieves for parameterized paths and packings
From MaRDI portal
Publication:2396725
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 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).
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
Cites work
- scientific article; zbMATH DE number 3974318 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- A Remark on Stirling's Formula
- A faster parameterized algorithm for set packing
- A parameterized perspective on packing paths of length two
- A probabilistic remark on algebraic program testing
- An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
- An efficient parameterized algorithm for m-set packing
- Color-coding
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Constrained multilinear detection and generalized graph motifs
- Determinant sums for undirected Hamiltonicity
- Divide-and-Color
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Exact covers via determinants
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Faster Algebraic Algorithms for Path and Packing Problems
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Graph-Theoretic Concepts in Computer Science
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Limits and Applications of Group Algebras for Parameterized Problems
- Looking at the stars
- Mixing Color Coding-Related Techniques
- NP completeness of finding the chromatic index of regular graphs
- Narrow sieves for parameterized paths and packings
- On Linear Time Minor Tests with Depth-First Search
- On limited nondeterminism and the complexity of the V-C dimension
- On the completeness of a generalized matching problem
- Parameterized and Exact Computation
- Parametrized complexity theory.
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Set partitioning via inclusion-exclusion
- Spotting trees with few leaves
- Systems of distinct representatives and linear algebra
- The Factorization of Linear Graphs
- The NP-Completeness of Edge-Coloring
- Which problems have strongly exponential complexity?
Cited in
(76)- Engineering motif search for large motifs
- Toward randomized testing of \(q\)-monomials in multivariate polynomials
- Parameterized Algorithms and Kernels for Rainbow Matching
- On \(r\)-simple \(k\)-path and related problems parameterized by \(k/r\)
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Decomposition of Map Graphs with Applications.
- Spotting trees with few leaves
- Finding detours is fixed-parameter tractable
- Randomized parameterized algorithms for co-path set problem
- Fixed-parameter tractability of maximum colored path and beyond
- scientific article; zbMATH DE number 7559154 (Why is no real title available?)
- Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
- Going far from degeneracy
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Approximate Counting of k-Paths: Deterministic and in Polynomial Space
- Computing paths of large rank in planar frameworks deterministically
- Clearing directed subgraphs by mobile agents. Variations on covering with paths
- Gerrymandering on graphs: computational complexity and parameterized algorithms
- Detours in directed graphs
- A Parameterized Perspective on Packing Paths of Length Two
- Partial information network queries
- Algorithms for topology-free and alignment network queries
- Deterministic subgraph detection in broadcast CONGEST
- Counting Paths and Packings in Halves
- Enumerating the edge-colourings and total colourings of a regular graph
- Kernel bounds for path and cycle problems
- Algorithms – ESA 2004
- Parameterized algorithms for the module motif problem
- scientific article; zbMATH DE number 7053391 (Why is no real title available?)
- A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families
- Revisiting the parameterized complexity of maximum-duo preservation string mapping
- The maximum binary tree problem
- Kernel bounds for path and cycle problems
- Mixing Color Coding-Related Techniques
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Parameterized approximation algorithms for packing problems
- Kernels for packing and covering problems
- Limits and Applications of Group Algebras for Parameterized Problems
- Improved algorithms for path, matching, and packing problems
- Randomised enumeration of small witnesses using a decision oracle
- The Maximum Binary Tree Problem.
- Faster deterministic parameterized algorithm for \(k\)-path
- Exponential approximation schemata for some network design problems
- Dealing with several parameterized problems by random methods
- Spotting trees with few leaves
- A parameterized perspective on packing paths of length two
- Fast algorithms for parameterized problems with relaxed disjointness constraints
- Parameterized pre-coloring extension and list coloring problems
- Parameterized algorithms for list \(K\)-cycle
- Improved Algorithms for Several Parameterized Problems Based on Random Methods
- Packing paths: recycling saves time
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Improved parameterized algorithms for network query problems
- An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
- Randomized parameterized algorithms for the kidney exchange problem
- Parameterized analysis and crossing minimization problems
- Faster Algebraic Algorithms for Path and Packing Problems
- A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
- Deterministic parameterized algorithms for the graph motif problem
- Parameterized Counting and Cayley Graph Expanders
- The \(k\)-distinct language: parameterized automata constructions
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
- The \(k\)-distinct language: parameterized automata constructions
- Long directed \((s,t)\)-path: FPT algorithm
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs
- Parameterized algorithms and kernels for rainbow matching
- Constrained multilinear detection and generalized graph motifs
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Deterministic algorithms for matching and packing problems based on representative sets
- Narrow sieves for parameterized paths and packings
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- An improved kernel for planar vertex-disjoint triangle packing
- Faster algorithms for finding and counting subgraphs
- Tight lower bounds for list edge coloring
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)
