Thanks a lot! I think you understood the problem correctly, I checked your argument and it seems correct to me, see https://cstheory.stackexchange.com/questions/20245/subset-of...

We have no specific plans for this result but it's always comforting to have an answer after all and know that it's in P. Plus this way I learnt about the existence of submodular functions. :)

List updated (http://a3nm.net/work/research/questions/#complexity-of-an-as...). Thanks again for making me remove the first problem from this list!