Complexity of transforming a balanced bipartite graph into regular graph?
Transform G into a weighted flow network N: connect the source s to all nodes in A by arcs of capacity n/2 and cost 0, connect all nodes in B to the sink t by arcs of capacity n/2 and cost 0, and connect each A-node u to each B-node v by an arc of capacity 1, with cost -1 if (u,v) is in G and 1 otherwise.

The maximum flow in N is n^2/2. Its cost can be written as -|E|+d, for some d >= 0. This d is the minimum edit cost of transforming G into a balanced n/2-regular bipartite graph with partition A,B.