4 ms·

I have just answered one of those problems here. http://cstheory.stackexchange.com/questions/20245/subset-of-a-bipartite-graph-with-maximal-number-of-minimal-u

• a3_nm 11y ago
  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-a-bipartite-graph-with-maximal-number-of-minimal-unmatched-vertices#comment77255_33603 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-assignment-problem-with-subsets http://a3nm.net/work/research/questions/#complexity-of-an-as...). Thanks again for making me remove the first problem from this list!
  • chaoxu 11y ago
    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.