<p>It is NP-hard. <a href="https://arxiv.org/abs/0805.1071" rel="nofollow noreferrer">Svitkina and Fleischer showed</a> that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries. </p>

CC BY-SA 3.0
2018-03-20T11:21:33.143Z
2018-03-20T16:38:59.297Z
2018-03-20T16:38:59.297Z
Chao Xu
<p>Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| &lt;= k and  such that f(S) is minimized.</p>

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

CC BY-SA 3.0
2018-03-21T02:30:47.197Z
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
<ds.algorithms><approximation-algorithms><submodularity>
Minimizing SubModular Function: Cardinality
Pavan Aduri
# Minimizing SubModular Function: Cardinality

(Asked by: username_0 on 2018-03-19)

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?

**Tags:** ds.algorithms, approximation-algorithms, submodularity

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-03-20. Score: 3

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


---

