Minimum sum set cover : structures and algorithm

Abstract

A set cover of a hypergraph H is a set of vertices intersecting every hyperedge. In the minimum sum set cover problem, vertices are selected one by one; each edge pays the position of the first vertex that hits it, and the objective is to minimize the total cost. When H is a graph, this is the minimum sum vertex cover problem. A solution is specified by a set cover S together with an ordering of its vertices. While the classical set cover problem seeks to minimize |S|, the minimum sum variant favors covering many edges early and may prefer larger covers. This motivates a natural question: how large can the gap between τ⟶ and τ be? We prove an upper bound τ⟶ ≤ τ log₂ |E(H)|, and show that for any n > 0, there exists a hypergraph H on n + 3 vertices with τ = 3 and τ⟶ = n. For graphs, we obtain stronger bounds: we prove τ⟶ ≤ 2τ log₂ τ, improving the bound of Liu et al. [Theor. Comput. Sci., 2025], and we construct graphs with τ⟶ = Ω( (τ log τ) / (log log τ) ), nearly matching this upper bound. On the algorithmic side, we show that minimum sum set cover is fixed-parameter tractable on bounded-rank hypergraphs, parameterized by τ⟶, extending the algorithm of Liu et al. for graphs.