6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Let me make sure I understand. Do you allow the new graph to have fewer vertices than G? $\endgroup$ – Marek Chrobak Feb 6 '11 at 23:31
  • $\begingroup$ @Marek, No, The new graph have the same vertex set $V$. I'll edit the question accordingly. $\endgroup$ – Mohammad Al-Turkistany Feb 6 '11 at 23:35
  • $\begingroup$ Such a procedure might shed light on certain expander properties of graphs. Cool. $\endgroup$ – Ross Snider Feb 6 '11 at 23:36
  • 1
    $\begingroup$ @Ross: Can you elaborate on the relation of this question to expanders? $\endgroup$ – Tsuyoshi Ito Feb 7 '11 at 2:16
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Snider Feb 7 '11 at 9:28
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do all balanced bipartite $n/2$-regular graphs have flow cost $-|E|$? (since d=0) $\endgroup$ – Mohammad Al-Turkistany Feb 8 '11 at 8:39
  • $\begingroup$ I guess that both topology and $n/2$-regularity of the bipartite graph determine the minimum cost maximum flow. $\endgroup$ – Mohammad Al-Turkistany Feb 8 '11 at 8:50
  • $\begingroup$ 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 ... :-( $\endgroup$ – Marzio De Biasi Feb 8 '11 at 15:33
  • $\begingroup$ @Vor, in your example |E| = 3, not 4. $\endgroup$ – Marek Chrobak Feb 10 '11 at 5:51
0
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 7 '11 at 1:49
  • $\begingroup$ @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. $\endgroup$ – Suresh Venkat Feb 7 '11 at 4:07
  • $\begingroup$ @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. $\endgroup$ – Marcus Ritt Feb 7 '11 at 4:43
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Feb 7 '11 at 5:23
  • 4
    $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito Feb 7 '11 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.