Towards optimal and expressive kernelization for d-hitting set
From MaRDI portal
(Redirected from Publication:486984)
Towards optimal and expressive kernelization for \(d\)-hitting set
Towards optimal and expressive kernelization for \(d\)-hitting set
Abstract: d-Hitting Set is the NP-hard problem of selecting at most k vertices of a hypergraph so that each hyperedge, all of which have cardinality at most d, contains at least one selected vertex. The applications of d-Hitting Set are, for example, fault diagnosis, automatic program verification, and the noise-minimizing assignment of frequencies to radio transmitters. We show a linear-time algorithm that transforms an instance of d-Hitting Set into an equivalent instance comprising at most O(k^d) hyperedges and vertices. In terms of parameterized complexity, this is a problem kernel. Our kernelization algorithm is based on speeding up the well-known approach of finding and shrinking sunflowers in hypergraphs, which yields problem kernels with structural properties that we condense into the concept of expressive kernelization. We conduct experiments to show that our kernelization algorithm can kernelize instances with more than 10^7 hyperedges in less than five minutes. Finally, we show that the number of vertices in the problem kernel can be further reduced to O(k^{d-1}) with additional O(k^{1.5 d}) processing time by nontrivially combining the sunflower technique with d-Hitting Set problem kernels due to Abu-Khzam and Moser.
Recommendations
- Towards optimal and expressive kernelization for \(d\)-hitting set
- A kernelization algorithm for \(d\)-hitting set
- Kernelization Algorithms for d-Hitting Set Problems
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- scientific article; zbMATH DE number 7759277
- Dynamic kernels for hitting sets and set packing
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Parameterized and Exact Computation
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Computing Hitting Set Kernels By AC^0-Circuits
Cites work
- scientific article; zbMATH DE number 3767009 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A kernelization algorithm for \(d\)-hitting set
- A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
- A theory of diagnosis from first principles
- An efficient fixed-parameter algorithm for 3-hitting set
- Applying modular decomposition to parameterized cluster editing problems
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Diagnosing multiple faults
- Exploiting a Hypergraph Model for Finding Golomb Rulers
- Fixed-parameter algorithms for cluster vertex deletion
- Intersection Theorems for Systems of Sets
- Kernelization: new upper and lower bound techniques
- Kernels for edge dominating set: simpler or smaller
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Parameterized algorithms for \(d\)-hitting set: the weighted case
- Parameterized and Exact Computation
- Parameterized approximation algorithms for hitting set
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Parametrized complexity theory.
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Simpler linear-time kernelization for planar dominating set
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
Cited in
(14)- Towards optimal and expressive kernelization for \(d\)-hitting set
- Kernelization of the subset general position problem in geometry
- Constrained hitting set problem with intervals
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- scientific article; zbMATH DE number 7559382 (Why is no real title available?)
- Exploiting hidden structure in selecting dimensions that distinguish vectors
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Finding points in general position
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- Dynamic kernels for hitting sets and set packing
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Computing Hitting Set Kernels By AC^0-Circuits
- Fixed-parameter algorithms for DAG partitioning
This page was built for publication: Towards optimal and expressive kernelization for \(d\)-hitting set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q486984)
