A kernelization algorithm for \(d\)-hitting set

DOI10.1016/j.jcss.2009.09.002zbMath1197.68083MaRDI QIDQ988567

Publication date: 18 August 2010

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.09.002

zbMATH Keywords

hypergraphs; vertex cover; fixed-parameter algorithms; kernelization; hitting set; crown decomposition

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

Kernelization of Two Path Searching Problems on Split Graphs, Unnamed Item, On the Complexity of Singly Connected Vertex Deletion, The Parameterized Complexity of Finding Point Sets with Hereditary Properties, 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size, Quadratic vertex kernel for split vertex deletion, On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT, Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems, On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT, Subset feedback vertex set in chordal and split graphs, Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU, Sequential model-based diagnosis by systematic search, A survey of parameterized algorithms and the complexity of edge modification, A Polynomial Kernel for Funnel Arc Deletion Set., A fast branching algorithm for cluster vertex deletion, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Parameterized complexity of vertex deletion into perfect graph classes, Kernelization for cycle transversal problems, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Exploiting a hypergraph model for finding Golomb rulers, Towards optimal and expressive kernelization for \(d\)-hitting set, An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem, Kernels for feedback arc set in tournaments, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Rank reduction of oriented graphs by vertex and edge deletions, Approximability of clique transversal in perfect graphs, Parameterized complexity of \(d\)-hitting set with quotas, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition, Kernels for deletion to classes of acyclic digraphs, Parameterized approximation via fidelity preserving transformations, Backdoors for linear temporal logic, Polynomial kernels for deletion to classes of acyclic digraphs, A polynomial kernel for trivially perfect editing, A polynomial kernel for diamond-free editing, On the complexity of singly connected vertex deletion, Dynamic kernels for hitting sets and set packing, A polynomial kernel for funnel arc deletion set, Color spanning objects: algorithms and hardness results, Parameterized aspects of strong subgraph closure, Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space, Fixed-parameter tractable algorithms for tracking shortest paths, A quadratic vertex kernel for feedback arc set in bipartite tournaments, Kernels for packing and covering problems, On the parameterized complexity of graph modification to first-order logic properties, Parameterised algorithms for deletion to classes of DAGs, Polynomial kernels for vertex cover parameterized by small degree modulators, On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments, Faster parameterized algorithms for deletion to split graphs, Meta-kernelization using well-structured modulators, Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, On the kernelization of split graph problems, Kernel for \(K_t\)\textsc{-free Edge Deletion}, Constrained hitting set problem with intervals, Color Spanning Objects: Algorithms and Hardness Results, Kernelization – Preprocessing with a Guarantee, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes

Cites Work