<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-08T08:39:15.063Z
Do all balanced bipartite $n/2$-regular graphs have flow cost $-|E|$? (since d=0)
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T08:50:26.933Z
I guess that both topology and $n/2$-regularity of the bipartite graph determine the minimum cost maximum flow.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-08T15:33:56.403Z
n=2, A={a1,a2}, B={b1,b2}, E={(a1,b1},(a1,b2),(a2,b2)}. |E|=4, MAX_FLOW=2 and the (minimum) cost of max flow is -2. Then -4 + d = -2 , d = 2 ??? But the number of operations required to make the graph n/2-regular (i.e. 1-regular) is 1 (delete edge (a1,b2)). Perhaps I still don't understand the original problem ... :-(
Marzio De Biasi
CC BY-SA 2.5
2011-02-10T05:51:34.573Z
@Vor, in your example |E| = 3, not 4.
Marek Chrobak
CC BY-SA 2.5
2011-02-08T06:42:57.327Z
2011-02-08T06:42:57.327Z
Marek Chrobak
<p>For each node $N \in A$ and $M \in B$, set 
$\textrm{diff}(N) = \deg(N) - n/2$ and $\textrm{diff}(M) = \deg(M) - n/2$.
Note that</p>

<p>$$\sum_{N \in A} \textrm{diff}(N) = \sum_{M \in B} \textrm{diff}(M)$$ 
(the graph is bipartite.)</p>

<p>The problem can be reformulated as: </p>

<blockquote>
  <p>What is the minimum number of operations required to make $\textrm{diff}(N) = 0$ for all nodes?</p>
</blockquote>

<p><strong>Algorithm</strong></p>

<p>STEP 1. Delete every edge $(N,M)$ such that $N \in A$, $M \in B$, $\textrm{diff}(N) &gt; 0$ and $\textrm{diff}(M) &gt; 0$.</p>

<p>STEP 2. For every node $N \in A$ with $\textrm{diff}(N) &lt; 0$, if there exists $M \in B$ having $\textrm{diff}(M) &lt; 0$, add an edge $(N,M)$.</p>

<p>After the two steps, you'll have a balanced bipartite graph in which:</p>

<p>CASE 1. $\textrm{diff}(N) = 0$ for each node $N$. (OK, stop.)</p>

<p>CASE 2. One of the two partitions has some nodes with $\textrm{diff} &gt; 0$ and some nodes  with $\textrm{diff} &lt; 0$.</p>

<ul>
<li>In this case you can "transfer" degrees between those nodes using 2 operations (delete + add). For example if $(N_1,M_1),(N_2,M_2) \in E$ and $\textrm{diff}(M_1) = 1$, $\textrm{diff}(M_2) = -1$ then delete edge $(N_1,M_1)$ and add $(N_1,M_2)$ (the operation will preserve $\textrm{diff}(N_1) = 0$. </li>
</ul>

<p>You will end with </p>

<p>CASE 3. Both partitions have some nodes with $\textrm{diff} &gt; 0$ (or both have some nodes with $\textrm{diff} &lt; 0$). In this case you can transfer degree following this procedure (suppose $p$ nodes of $A$ and $q$ nodes of $B$ have $\textrm{diff} &gt; 0$):</p>

<ul>
<li><p>For every node $N \in A$ with $\textrm{diff}(N) &gt; 0$, delete edge $(N,X)$ where $X$ is the node in $B$ (linked to $N$) having the lowest degree.</p></li>
<li><p>After this loop all nodes in $A$ will have $\textrm{diff} = 0$, and some nodes in $B$ will have $\textrm{diff} &gt; 0$ and some $\textrm{diff} &lt; 0$. Then transfer degrees using method showed in CASE 2 until every node $M$ has $\textrm{diff}(M) = 0$.</p></li>
</ul>

<p>If at CASE 3, $p$ nodes of $A$ and $q$ nodes of B have $\textrm{diff} &lt; 0$ the method is similar (add edge $(N,X)$ where $X$ is the node in $B$ having the highest degree).</p>

<p>Count the number of operations $r$ made and compare it to $k$.</p>

<p><strong>Example (how the algorithm SHOULD work)</strong></p>

<p><img src="https://i.sstatic.net/bwDoR.jpg" alt="Example"></p>

<p>Input graph; graph after STEP 1+2; graph after "degree transfer" on $A$; graph after "degree transfer" on $B$</p>

<ul>
<li>input graph</li>
<li>graph after STEP 1+2</li>
<li>graph after "degree transfer" on $B$ (from $b_1$ to $b_6$).</li>
<li>graph after "degree transfer" on $A$ (from $a_1$ to $a_6$)</li>
</ul>

<p>Red means "delete edge", blue means "add edge").</p>

<p><strong>Correctness</strong></p>

<p>Still working on it.</p>

<p>P.S. I'm a CS newbie so perhaps I completely misunderstood the problem :-)</p>

<p>P.P.S. the graph keeps "balanced bipartite" because the algorithm doesn't add/delete nodes or edges between the elements of each set.</p>

CC BY-SA 2.5
2011-02-07T01:49:52.683Z
Note that even if there exists nodes a∈A and b∈B such that diff(a)>0 and diff(b)>0, they may not be adjacent.  Therefore, I do not think that your answer fully specifies an algorithm.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T04:07:21.307Z
@Tsuyoshi, that's not quite right. In the case you describe, the first part of the algorithms concludes, and it moves to the second phase. In general, the first phase ends when the neighborhood of all "excess" (diff > 0) nodes on the left consists of "deficient" (diff < 0) nodes on the right, and vice versa. I'm not entirely sure it's correct, but it's not because of your issue.
Suresh Venkat
CC BY-SA 2.5
2011-02-07T04:43:24.533Z
@Vor: What about $G=(\{a_1,\ldots,a_4\}\cup\{b_1,\ldots,b_4\}$,$\{\{a_1,b_2\},\{a_1,b_3\},\{a_1,b_4\},\{b_1,a_2\}$,$\{b_1,a_3\},\{b_1,a_4\},\{a_2,b_2\},\{a_3,b_3\},\{a_4,b_4\}\})$? You got $diff(a_1)=diff(b_1)=1$ and diff 0 for the rest.
Marcus Ritt
CC BY-SA 2.5
2011-02-07T05:23:28.777Z
@Suresh: I do not think that this answer takes into account the case which I pointed out, but Marcus gave a much cleaner counterexample to the claim stated in the answer, which supersedes my comment.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T08:00:40.543Z
@Marcus great example, but the algorithm can still work: delete {a1,b2} then transfer degree from b1 to b2. Now I modify it.
Marzio De Biasi
CC BY-SA 2.5
2011-02-07T08:57:35.207Z
@Tsuyoshi why do you say "they may not be adjacent"? If diff(N)=0 for all nodes then the graph is regular (every node have the same degree)? Are there constraints in the order in which an edge can be removed or added?
Marzio De Biasi
CC BY-SA 2.5
2011-02-07T13:29:34.220Z
I am afraid that the current (revision 8) case analysis makes no sense to me, but the most important point is: How do you prove that your method takes the minimum number of edits?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T14:09:10.843Z
@Tsuyoshi Excuse me for my bad English. If you want, give me some complex examples and I'll show on them how the algorithm works.
Marzio De Biasi
CC BY-SA 2.5
2011-02-07T14:41:52.330Z
(1) No, it is not about English.  In the current version (revision 10), I do not think that cases 1, 2 and 3 are exhaustive.  But I do not have time to construct a counterexample for a moving target.  Also, you have to make diff(v)=0 for all vertices v, not just ∑_{a∈A}diff(a)=∑_{b∈B}diff(b)=0.  (2) Again, where is your proof of correctness?  To prove that the problem is in P, you have to not only give some polynomial-time algorithm which may work, but also prove that the algorithm is correct.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T15:06:12.730Z
@Tsuyoshi "I do not have time to construct a counterexample for a moving target" You're right, sorry :-))) ... however, at the end of the algorithm all diff(v) = 0 ... I'll try to demonstrate (first of all to myself) that it is correct.
Marzio De Biasi
CC BY-SA 2.5
2011-02-06T23:40:39.463Z
2011-02-08T07:04:38.133Z
2011-02-08T07:04:38.133Z
Marzio De Biasi
<p>I'm studying certain graph editing problems and I'd like to determine the complexity of this problem:</p>

<p>Input: Balanced bipartite graph <span class="math-container">$G(A \bigcup B, E)$</span>, <span class="math-container">$|A|=|B|=n$</span>, integer <span class="math-container">$k$</span></p>

<p>Problem: Is there <span class="math-container">$r$</span> edit operations that transform the input graph into balanced bipartite <span class="math-container">$n/2$</span>-regular graph (<span class="math-container">$r \leq k$</span>).</p>

<p>An edit operation can be an addition of one edge or a removal of one edge (between sets <span class="math-container">$A$</span> and <span class="math-container">$B$</span>). </p>

<blockquote>
  <p>Has anyone seen this problem in the literature? Is there a polynomial time algorithm or is it <span class="math-container">$NP$</span>-complete?</p>
</blockquote>

<p>My main interest is in the case where <span class="math-container">$k \leq cn$</span> for some constant <span class="math-container">$c \gt 0$</span>.</p>

<p>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 <span class="math-container">$G(A \bigcup B, E)$</span> into balanced bipartite <span class="math-container">$n/2$</span>-regular graph <span class="math-container">$G(A \bigcup B, E^{'})$</span>. Notice that <span class="math-container">$n$</span> must be even integer.</p>

CC BY-SA 2.5
2011-02-06T23:31:04.197Z
Let me make sure I understand. Do you allow the new graph to have fewer vertices than G?
Marek Chrobak
CC BY-SA 2.5
2011-02-06T23:35:51.053Z
@Marek, No, The new graph have the same vertex set $V$. I'll edit the question accordingly.
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-02-06T23:36:49.380Z
Such a procedure might shed light on certain expander properties of graphs. Cool.
Ross Snider
CC BY-SA 2.5
2011-02-07T02:16:01.277Z
@Ross: Can you elaborate on the relation of this question to expanders?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T09:28:15.913Z
@Tsuyoshi I think my comment was a bit hasty. Here is what I was thinking: it is known that directed graphs can be described as balanced bipartite graphs and if this decision problem gives us a constructive way to convert such a graph to a d-regular graph (the first reading I missed that it is a n/2-regular _balanced bipartite_ graph) then this might shed light on the expanding properties of various directed graphs. This in turn might allow one to study the expansion properties of graphs created by non-abelian groups (which are easily described as directed rather than undirected graphs). Cont.
Ross Snider
CC BY-SA 2.5
2011-02-07T09:29:40.827Z
Cont... but upon reading the question again and questioning my poor-man's intuition I would retract my comment if I could.
Ross Snider
CC BY-SA 2.5
2011-02-07T15:00:06.653Z
@Ross: Thanks for the explanation.  I have to think more about it, but my intuition is that being “n/2-regular” is pretty far from “expanding,” because the expanding property is meaningful only when the graph is sparse.
Tsuyoshi Ito
CC BY-SA 4.0
2019-12-19T11:02:20.887Z
I've a "crazy" idea, but I cannot find a quick counterexample to it. Take a maximum matching, and remove it from the graph. Do it $n/2$ times. Let the size of the $i$th matching be $m_i$. The solution is $\sum_{i=1}^{n/2} (n - m_i)$ and the number of remaining edges.
Yixin Cao
<ds.algorithms><reference-request><graph-algorithms>
Complexity of transforming a balanced bipartite graph into regular graph?
Mohammad Al-Turkistany
# Complexity of transforming a balanced bipartite graph into regular graph?

(Asked by: username_0 on 2011-02-06)

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.

**Tags:** ds.algorithms, reference-request, graph-algorithms

> **Comments:**
> **username_1**: Let me make sure I understand. Do you allow the new graph to have fewer vertices than G?  
> **username_0**: @Marek, No, The new graph have the same vertex set $V$. I'll edit the question accordingly.  
> **username_2**: Such a procedure might shed light on certain expander properties of graphs. Cool.  
> **username_3**: @Ross: Can you elaborate on the relation of this question to expanders?  
> **username_2**: @Tsuyoshi I think my comment was a bit hasty. Here is what I was thinking: it is known that directed graphs can be described as balanced bipartite graphs and if this decision problem gives us a constructive way to convert such a graph to a d-regular graph (the first reading I missed that it is a n/2-regular _balanced bipartite_ graph) then this might shed light on the expanding properties of various directed graphs. This in turn might allow one to study the expansion properties of graphs created by non-abelian groups (which are easily described as directed rather than undirected graphs). Cont.  
> **username_2**: Cont... but upon reading the question again and questioning my poor-man's intuition I would retract my comment if I could.  
> **username_3**: @Ross: Thanks for the explanation.  I have to think more about it, but my intuition is that being “n/2-regular” is pretty far from “expanding,” because the expanding property is meaningful only when the graph is sparse.  
> **username_4**: I've a "crazy" idea, but I cannot find a quick counterexample to it. Take a maximum matching, and remove it from the graph. Do it $n/2$ times. Let the size of the $i$th matching be $m_i$. The solution is $\sum_{i=1}^{n/2} (n - m_i)$ and the number of remaining edges.  

---

## 2 answers

### Answer by username_1 on 2011-02-08. Score: 3

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.

> **Comments:**
> **username_0**: Do all balanced bipartite $n/2$-regular graphs have flow cost $-|E|$? (since d=0)  
> **username_0**: I guess that both topology and $n/2$-regularity of the bipartite graph determine the minimum cost maximum flow.  
> **username_5**: n=2, A={a1,a2}, B={b1,b2}, E={(a1,b1},(a1,b2),(a2,b2)}. |E|=4, MAX_FLOW=2 and the (minimum) cost of max flow is -2. Then -4 + d = -2 , d = 2 ??? But the number of operations required to make the graph n/2-regular (i.e. 1-regular) is 1 (delete edge (a1,b2)). Perhaps I still don't understand the original problem ... :-(  
> **username_1**: @Vor, in your example |E| = 3, not 4.  

---

### Answer by username_5 on 2011-02-06. Score: 0

For each node $N \in A$ and $M \in B$, set
$\textrm{diff}(N) = \deg(N) - n/2$ and $\textrm{diff}(M) = \deg(M) - n/2$.
Note that

$$\sum\_{N \in A} \textrm{diff}(N) = \sum\_{M \in B} \textrm{diff}(M)$$
(the graph is bipartite.)

The problem can be reformulated as:

> What is the minimum number of operations required to make $\textrm{diff}(N) = 0$ for all nodes?

**Algorithm**

STEP 1. Delete every edge $(N,M)$ such that $N \in A$, $M \in B$, $\textrm{diff}(N) > 0$ and $\textrm{diff}(M) > 0$.

STEP 2. For every node $N \in A$ with $\textrm{diff}(N) < 0$, if there exists $M \in B$ having $\textrm{diff}(M) < 0$, add an edge $(N,M)$.

After the two steps, you'll have a balanced bipartite graph in which:

CASE 1. $\textrm{diff}(N) = 0$ for each node $N$. (OK, stop.)

CASE 2. One of the two partitions has some nodes with $\textrm{diff} > 0$ and some nodes with $\textrm{diff} < 0$.

* In this case you can "transfer" degrees between those nodes using 2 operations (delete + add). For example if $(N\_1,M\_1),(N\_2,M\_2) \in E$ and $\textrm{diff}(M\_1) = 1$, $\textrm{diff}(M\_2) = -1$ then delete edge $(N\_1,M\_1)$ and add $(N\_1,M\_2)$ (the operation will preserve $\textrm{diff}(N\_1) = 0$.

You will end with

CASE 3. Both partitions have some nodes with $\textrm{diff} > 0$ (or both have some nodes with $\textrm{diff} < 0$). In this case you can transfer degree following this procedure (suppose $p$ nodes of $A$ and $q$ nodes of $B$ have $\textrm{diff} > 0$):

* For every node $N \in A$ with $\textrm{diff}(N) > 0$, delete edge $(N,X)$ where $X$ is the node in $B$ (linked to $N$) having the lowest degree.
* After this loop all nodes in $A$ will have $\textrm{diff} = 0$, and some nodes in $B$ will have $\textrm{diff} > 0$ and some $\textrm{diff} < 0$. Then transfer degrees using method showed in CASE 2 until every node $M$ has $\textrm{diff}(M) = 0$.

If at CASE 3, $p$ nodes of $A$ and $q$ nodes of B have $\textrm{diff} < 0$ the method is similar (add edge $(N,X)$ where $X$ is the node in $B$ having the highest degree).

Count the number of operations $r$ made and compare it to $k$.

**Example (how the algorithm SHOULD work)**

![Example](https://i.sstatic.net/bwDoR.jpg)

Input graph; graph after STEP 1+2; graph after "degree transfer" on $A$; graph after "degree transfer" on $B$

* input graph
* graph after STEP 1+2
* graph after "degree transfer" on $B$ (from $b\_1$ to $b\_6$).
* graph after "degree transfer" on $A$ (from $a\_1$ to $a\_6$)

Red means "delete edge", blue means "add edge").

**Correctness**

Still working on it.

P.S. I'm a CS newbie so perhaps I completely misunderstood the problem :-)

P.P.S. the graph keeps "balanced bipartite" because the algorithm doesn't add/delete nodes or edges between the elements of each set.

> **Comments:**
> **username_3**: Note that even if there exists nodes a∈A and b∈B such that diff(a)>0 and diff(b)>0, they may not be adjacent.  Therefore, I do not think that your answer fully specifies an algorithm.  
> **username_6**: @Tsuyoshi, that's not quite right. In the case you describe, the first part of the algorithms concludes, and it moves to the second phase. In general, the first phase ends when the neighborhood of all "excess" (diff > 0) nodes on the left consists of "deficient" (diff < 0) nodes on the right, and vice versa. I'm not entirely sure it's correct, but it's not because of your issue.  
> **username_7**: @Vor: What about $G=(\{a_1,\ldots,a_4\}\cup\{b_1,\ldots,b_4\}$,$\{\{a_1,b_2\},\{a_1,b_3\},\{a_1,b_4\},\{b_1,a_2\}$,$\{b_1,a_3\},\{b_1,a_4\},\{a_2,b_2\},\{a_3,b_3\},\{a_4,b_4\}\})$? You got $diff(a_1)=diff(b_1)=1$ and diff 0 for the rest.  
> **username_3**: @Suresh: I do not think that this answer takes into account the case which I pointed out, but Marcus gave a much cleaner counterexample to the claim stated in the answer, which supersedes my comment.  
> **username_5**: @Marcus great example, but the algorithm can still work: delete {a1,b2} then transfer degree from b1 to b2. Now I modify it.  
> **username_5**: @Tsuyoshi why do you say "they may not be adjacent"? If diff(N)=0 for all nodes then the graph is regular (every node have the same degree)? Are there constraints in the order in which an edge can be removed or added?  
> **username_3**: I am afraid that the current (revision 8) case analysis makes no sense to me, but the most important point is: How do you prove that your method takes the minimum number of edits?  
> **username_5**: @Tsuyoshi Excuse me for my bad English. If you want, give me some complex examples and I'll show on them how the algorithm works.  
> **username_3**: (1) No, it is not about English.  In the current version (revision 10), I do not think that cases 1, 2 and 3 are exhaustive.  But I do not have time to construct a counterexample for a moving target.  Also, you have to make diff(v)=0 for all vertices v, not just ∑_{a∈A}diff(a)=∑_{b∈B}diff(b)=0.  (2) Again, where is your proof of correctness?  To prove that the problem is in P, you have to not only give some polynomial-time algorithm which may work, but also prove that the algorithm is correct.  
> **username_5**: @Tsuyoshi "I do not have time to construct a counterexample for a moving target" You're right, sorry :-))) ... however, at the end of the algorithm all diff(v) = 0 ... I'll try to demonstrate (first of all to myself) that it is correct.  

---

