Complexity of transforming a balanced bipartite graph into regular graph? I'm studying certain graph editing problems and I'd like to determine the complexity of this problem:

Input: Balanced bipartite graph $G(A \bigcup B, E)$, $|A|=|B|=n$, integer $k$

Problem: Is there $r$ edit operations that transform the input graph into balanced bipartite $n/2$-regular graph ($r \leq k$).

An edit operation can be an addition of one edge or a removal of one edge (between sets $A$ and $B$). 


  Has anyone seen this problem in the literature? Is there a polynomial time algorithm or is it $NP$-complete?


My main interest is in the case where $k \leq cn$ for some constant $c \gt 0$.

EDIT: One way to look at the problem is to find the minimum number of edit operations that transform an input of balanced bipartite graph $G(A \bigcup B, E)$ into balanced bipartite $n/2$-regular graph $G(A \bigcup B, E^{'})$. Notice that $n$ must be even integer.
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.