<p>I am new to submodular functions and I am reading the introductions to submodular functions and applications ( <a href="https://www.ima.umn.edu/optimization/seminar/queyranne.pdf" rel="nofollow">https://www.ima.umn.edu/optimization/seminar/queyranne.pdf</a> ).</p>

<p>In this introduction, it says</p>

<p>" A submodular set function can be minimized in strongly polynomial time. Remark: • minimizing a submodular function f, subject to a cardinality constraint, such as |A| = b, or |A| ≥ b, or |A| ≤ b are NP-hard when f is a cut function ".</p>

<p>In the remark, it says the problem is NP-hard if 1) there is a cardinality constraint and 2) f is a cut function.</p>

<p>What if only one of the 2 constraints holds, i.e. f is not a cut function but there is a cardinality constraint? Is this problem of minimizing f(A) still an NP-hard problem?</p>

CC BY-SA 3.0
2015-03-11T13:27:44.640Z
Starting with a cut function, you can modify one value of the function (say $f$ of the entire universe) without modifying the objective value while keeping the function submodular. So asking that $f$ not be a cut function doesn't make the problem easier.
Yuval Filmus
CC BY-SA 3.0
2015-03-12T03:48:04.020Z
@YuvalFilmus Hence the be *f* a cut function or not, the size-constrained minimizing submodular function is NP-hard.
Jerry Song
<np-hardness><submodularity><minimization>
Hardness of Minimizing Submodular Functions with Cardinality Constraints
Jerry Song
# Hardness of Minimizing Submodular Functions with Cardinality Constraints

(Asked by: username_0 on 2015-03-11)

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( <https://www.ima.umn.edu/optimization/seminar/queyranne.pdf> ).

In this introduction, it says

" A submodular set function can be minimized in strongly polynomial time. Remark: • minimizing a submodular function f, subject to a cardinality constraint, such as |A| = b, or |A| ≥ b, or |A| ≤ b are NP-hard when f is a cut function ".

In the remark, it says the problem is NP-hard if 1) there is a cardinality constraint and 2) f is a cut function.

What if only one of the 2 constraints holds, i.e. f is not a cut function but there is a cardinality constraint? Is this problem of minimizing f(A) still an NP-hard problem?

**Tags:** np-hardness, submodularity, minimization

> **Comments:**
> **username_1**: Starting with a cut function, you can modify one value of the function (say $f$ of the entire universe) without modifying the objective value while keeping the function submodular. So asking that $f$ not be a cut function doesn't make the problem easier.  
> **username_0**: @YuvalFilmus Hence the be *f* a cut function or not, the size-constrained minimizing submodular function is NP-hard.  

---

## 0 answers

