# Minimizing SubModular Function: Cardinality

Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and such that f(S) is minimized.

When the size constraint is |S| >=k, the problem is NP-hard. What is known about when the constraint is |S| <= k?

• The complement of a submodular function is submodular, so there exists a direct reduction from the hard $|S| \geq k$ case to your $|S| \leq |V| - k$ problem. – Yonatan N Mar 21 '18 at 2:30

It is NP-hard. Svitkina and Fleischer showed that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries.