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

DOI10.1016/j.jcss.2009.09.002zbMath1197.68083OpenAlexW2014363582MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

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

Cites Work