2026-07-26T01:39:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12256 2024-03-06T10:49:27Z ddc:004 open_access

Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time Bannach, Max Skambath, Malte Tantau, Till Kernelization Approximation Hitting Set Constant-Depth Circuits We analyze a reduction rule for computing kernels for the hitting set problem: In a hypergraph, the link of a set c of vertices consists of all edges that are supersets of c. We call such a set critical if its link has certain easy-to-check size properties. The rule states that the link of a critical c can be replaced by c. It is known that a simple linear-time algorithm for computing hitting set kernels (number of edges) at most k^d (k is the hitting set size, d is the maximum edge size) can be derived from this rule. We parallelize this algorithm and obtain the first AC⁰ kernel algorithm that outputs polynomial-size kernels. Previously, such algorithms were not even known for artificial problems. An interesting application of our methods lies in traditional, non-parameterized approximation theory: Our results imply that uniform AC⁰-circuits can compute a hitting set whose size is polynomial in the size of an optimal hitting set. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Bannach and Malte Skambath and Till Tantau 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.9 urn:nbn:de:0030-drops-122566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode