On kernels for \(d\)-path vertex cover

DOI10.1016/j.jcss.2024.103531MaRDI QIDQ6564612

Ondřej Suchý, Pratibha Choudhary, Radovan Červený

Publication date: 1 July 2024

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

zbMATH Keywords

parameterized complexitykernelizationexpansion lemma\(d\)-path vertex cover\(d\)-hitting set

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Improved upper bounds for vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
• A kernel of order \(2k-c\log k\) for vertex cover
• Exact algorithms for maximum independent set
• Iterative compression and exact algorithms
• Faster deterministic parameterized algorithm for \(k\)-path
• Minimum \(k\)-path vertex cover
• Partitioning a graph into small pieces with applications to path transversal
• Hitting Forbidden Minors: Approximation and Kernelization
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Fast Witness Extraction Using a Decision Oracle
• A 4 k ² kernel for feedback vertex set
• A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Parameterized algorithmics for d-H<scp>itting</scp> S<scp>et</scp>
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Mixing Color Coding-Related Techniques
• Paths, Trees, and Flowers
• Parameterized Algorithms
• Generating Faster Algorithms for d-Path Vertex Cover

This page was built for publication: On kernels for \(d\)-path vertex cover