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 ta

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.