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?

  • $\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$ – Yuval Filmus Mar 11 '15 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 '15 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.