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?