Author here, thanks for the comments! I added two problems to http://a3nm.net/work/research/questions/#well-known-conjectu... following ideas here.
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!