Narrow sieves for parameterized paths and packings

DOI10.1016/j.jcss.2017.03.003zbMath1370.68321arXiv1007.1161OpenAlexW2596605817MaRDI QIDQ2396725

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

Publication date: 24 May 2017

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

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

zbMATH Keywords

graph algorithmedge coloringrandomized algorithmdeterminantset packing\(k\)-pathsievepolynomial identity testingmultidimensional matching

Mathematics Subject Classification ID

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

Related Items (61)

Spotting Trees with Few Leaves ⋮ Kernel Bounds for Path and Cycle Problems ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Spotting Trees with Few Leaves ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Mixing Color Coding-Related Techniques ⋮ Randomized parameterized algorithms for the kidney exchange problem ⋮ Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized approximation algorithms for packing problems ⋮ Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for the module motif problem ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Narrow sieves for parameterized paths and packings ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Gerrymandering on graphs: computational complexity and parameterized algorithms ⋮ Kernel bounds for path and cycle problems ⋮ Improved parameterized algorithms for network query problems ⋮ An improved kernel for planar vertex-disjoint triangle packing ⋮ Exponential approximation schemata for some network design problems ⋮ Detours in directed graphs ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Faster algorithms for finding and counting subgraphs ⋮ Revisiting the parameterized complexity of maximum-duo preservation string mapping ⋮ Enumerating the edge-colourings and total colourings of a regular graph ⋮ Going Far from Degeneracy ⋮ Randomised enumeration of small witnesses using a decision oracle ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ The Maximum Binary Tree Problem. ⋮ Parameterized algorithms and kernels for rainbow matching ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for topology-free and alignment network queries ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ A \(2^{O(k)}n\) algorithm for \(k\)-cycle in minor-closed graph families ⋮ Partial information network queries ⋮ Faster deterministic parameterized algorithm for \(k\)-path ⋮ Kernels for packing and covering problems ⋮ Unnamed Item ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Long directed \((s,t)\)-path: FPT algorithm ⋮ The maximum binary tree problem ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space ⋮ Decomposition of Map Graphs with Applications. ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Unnamed Item ⋮ Parameterized Algorithms and Kernels for Rainbow Matching ⋮ Tight Lower Bounds for List Edge Coloring ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Unnamed Item ⋮ TOWARD RANDOMIZED TESTING OF q-MONOMIALS IN MULTIVARIATE POLYNOMIALS ⋮ Constrained multilinear detection and generalized graph motifs

Cites Work

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

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