Computing Hitting Set Kernels By AC^0-Circuits

DOI10.4230/LIPICS.STACS.2018.9MaRDI QIDQ3304103zbMATH OpenOpenAlexFDO

Authors Max Bannach, Till Tantau

Publication date 5 August 2020

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

zbMATH Keywords

parallel computationfixed-parameter tractabilitykernelization

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Hypergraphs (05C65) Parallel algorithms in computer science (68W10) Networks and circuits as models of computation; circuit complexity (68Q06) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: Given a hypergraph $H=(V,E)$, what is the smallest subset $XsubseteqV$ such that $ecapXeqemptyset$ holds for all $einE$? This problem, known as the hitting set problem, is a basic problem in parameterized complexity theory. There are well-known kernelization algorithms for it, which get a hypergraph $H$ and a number $k$ as input and output a hypergraph $H^{\prime }$ such that (1) $H$ has a hitting set of size $k$ if, and only if, $H^{\prime }$ has such a hitting set and (2) the size of $H^{\prime }$ depends only on $k$ and on the maximum cardinality $d$ of edges in $H$. The algorithms run in polynomial time, but are highly sequential. Recently, it has been shown that one of them can be parallelized to a certain degree: one can compute hitting set kernels in parallel time $O(d)$ -- but it was conjectured that this is the best parallel algorithm possible. We refute this conjecture and show how hitting set kernels can be computed in constant parallel time. For our proof, we introduce a new, generalized notion of hypergraph sunflowers and show how iterated applications of the color coding technique can sometimes be collapsed into a single application.

Recommendations

• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
• Kernelization Algorithms for d-Hitting Set Problems
• A kernelization algorithm for \(d\)-hitting set
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Near-optimal bootstrapping of hitting sets for algebraic circuits
• scientific article; zbMATH DE number 7759277
• scientific article; zbMATH DE number 7009617
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Parameterized and Exact Computation

Cites work

• scientific article; zbMATH DE number 2086399 (Why is no real title available?)
• Advice classes of parametrized tractability
• An efficient fixed-parameter algorithm for 3-hitting set
• Color-coding
• Fast parallel fixed-parameter algorithms via color coding
• Intersection Theorems for Systems of Sets
• On the space and circuit complexity of parameterized problems: classes and completeness
• Parallel Multivariate Meta-Theorems
• Parametrized complexity theory.
• Scalable parallel algorithms for FPT problems
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• Towards optimal and expressive kernelization for \(d\)-hitting set

Cited in

(10)

• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
• Dynamic kernels for hitting sets and set packing
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• The parameterized space complexity of model-checking bounded variable first-order logic
• Towards optimal and expressive kernelization for \(d\)-hitting set
• On the descriptive complexity of color coding
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Dynamic kernels for hitting sets and set packing
• Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits

This page was built for publication: Computing Hitting Set Kernels By AC^0-Circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304103)