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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.