Dekel Tsur

In the A-Multi3-Hitting Set problem (A-M3HS), where A⊆{1,2,3}, the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that |S∩e|∈A for every hyperedge e. In this paper we give O∗(2.027k)-time algorithms for {1}-M3HS and {1,3}-M3HS, and an O∗(1.381k)-time algorithm for {2}-M3HS.