Faster parameterized algorithm for 3-Hitting Set

2025/01/11 by Tsur, Dekel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2501.06452

Abstract

In the 3-Hitting Set problem, the input is a hypergraph G such that the size of every hyperedge of G is at most 3, and an integers k, and the goal is to decide whether there is a set S of at most k vertices such that every hyperedge of G contains at least one vertex from S. In this paper we give an O^*(2.0409^k)-time algorithm for 3-Hitting Set.

Related

• A Refined Kernel for d-Hitting Set
• Enumerating all minimal hitting sets in polynomial total time
• On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs\n Using 2-SAT
• Linear Kernelizations for Restricted 3-Hitting Set Problems
• Computing Hitting Set Kernels By AC⁰-Circuits