Towards optimal and expressive kernelization for d-hitting set

DOI10.1007/S00453-013-9774-3zbMATH Open1314.68167arXiv1112.2310OpenAlexW3106541239MaRDI QIDQ486984FDOQ486984

Authors: René van Bevern 

Publication date: 19 January 2015

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

fault diagnosisalgorithm engineeringlinear-time data reductionparameterized algorithmicssunflower lemmavertex cover in hypergraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65)

Cites Work

• Applying modular decomposition to parameterized cluster editing problems
• Fixed-parameter algorithms for cluster vertex deletion
• A kernelization algorithm for \(d\)-hitting set
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• Title not available (Why is that?)
• Diagnosing multiple faults
• A theory of diagnosis from first principles
• Intersection Theorems for Systems of Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized approximation algorithms for hitting set
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernelization: new upper and lower bound techniques
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• An efficient fixed-parameter algorithm for 3-hitting set
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• Exploiting a Hypergraph Model for Finding Golomb Rulers
• Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Simpler linear-time kernelization for planar dominating set
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Kernels for edge dominating set: simpler or smaller
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
• Parameterized and Exact Computation

Cited In (15)

• Dynamic kernels for hitting sets and set packing
• Title not available (Why is that?)
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• A shortcut to (sun)flowers: kernels in logarithmic space or linear time
• Parameterizing edge modification problems above lower bounds
• Title not available (Why is that?)
• Constrained hitting set problem with intervals
• Computing Hitting Set Kernels By AC^0-Circuits
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Exploiting hidden structure in selecting dimensions that distinguish vectors
• Fixed-parameter algorithms for DAG partitioning
• Finding Points in General Position
• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits

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)