# Hardness of Minimizing Submodular Functions with Cardinality Constraints

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?

• 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 Mar 11 '15 at 13:27
• @YuvalFilmus Hence the be f a cut function or not, the size-constrained minimizing submodular function is NP-hard. – Jerry Song Mar 12 '15 at 3:48