# Approaches to the size constrained weighted set cover problem

I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended up quite confused with only one, also rather recent paper by Golab et al. [1].

Am I missing something here?

[1] Golab, Korn, Li, Saha and Srivastava, Size-constrained weighted set cover. In _Proceedings of 31st International Conference on Data Engineering (ICDE), pp. 879–890. IEEE, 2015. IEEE Digital Library; author PDF.

• Welcome to CS.SE! 1. Can you edit the question to provide a reference that will be as robust over time as possible? We have collected some advice here. I suggest including the title, authors, and where it was published. 2. What exactly do you want to know about the problem? 3. If you can find one paper on a topic, it's often useful to check what other papers cite that one and what other papers it cites, to see if any of them have anything relevant. – D.W. Jan 28 '17 at 12:28

The problem is in P and can be solved in $O(m^k)$ time, where $m$ is the number of sets to select from. For this reason, it is fundamentally different from standard set cover (which is NP-hard) and might not have been studied as much in the complexity theory literature.
• @martin, in that paper, $k$ is part of the input, rather than a constant. When $k$ is part of the input (i.e., unbounded), the problem is NP-complete. When $k$ is fixed (e.g., 5), it is in P. – D.W. Jan 30 '17 at 4:08