Minimum Sum Set Cover: Structures and Algorithm
For researchers in combinatorial optimization and parameterized complexity, the paper provides tight structural bounds and an algorithmic extension for a natural variant of set cover.
The paper studies the minimum sum set cover problem, proving that the optimal cost can be much larger than the minimum set cover size, with a gap up to n for hypergraphs and nearly matching upper and lower bounds for graphs. It also gives an FPT algorithm for bounded-rank hypergraphs parameterized by solution cost.
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~$\overrightarrowτ$ and $τ$ be? We prove an upper bound $\overrightarrowτ \le τ\log_{2} \lvert E(H)\rvert$, and show that for any positive~$n$, there exists a hypergraph $H$ on $n + 3$ vertices with $τ=3$ and $\overrightarrowτ=n$. For graphs, we obtain stronger bounds: we prove~$\overrightarrowτ \le 2τ\log_{2} τ$, improving the bound of Liu et al.\ [Theor. Comput. Sci., 2025], and we construct graphs with~$\overrightarrowτ = Ω\left( \frac{τ\log τ}{\log\log τ}\right)$, 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~$\overrightarrowτ$, extending the algorithm of Liu et al.\ for graphs (i.e., rank-two hypergraphs).