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. :)
np.
There might be ways to speed up the running time for this special case. Naive algorithm using submodular minization + maximum matching as an oracle would take around O(n^c) where c is probably more than 10.
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!