Transform a graph into a bipratite one

[StTwister]

Hi,

How can i transform a weighted graph into a bipartite one so that the sum of the edges between nodes from different sets is minimum?

[Zachm]

Which operations are allowed in the graph transformation ?
- Is adding or deleting edges allowed ?
- Is graph connectivity needs to be preserved ?

A bipartite graph has exactly 2 sets of vertices where ALL edges have one vertex in set A and one vertex in set B, therfore I assume that you want to achieve this transformation by deleting edges, until a bipartite graph remains.
You can continue to delete edges (thus loosing connectivity) and reduce the weight-sum of the edges between A and B even more, the graph will still be bipartite by definition.

So, if the problem is to find a connected bipartite graph of minimum weight-sum which is a sub-graph of the original graph, you might wanna try to find a minimum spanning tree of the graph.

A tree is by definition bipartite, and a minimum spanning tree is the lightest (in edge weights) structure that preserves graph connectivity.

The most common algorithms for finding a minimum spanning tree in a graph are Prim's or Kruskal's algorithms. You can find information and links on both at:
http://en.wikipedia.org/wiki/Minimum_spanning_tree#Algorithms

I think that this is an optimal solution, although I didn't prove it formally.
I would be happy to receive any comments / corrections.

Best of luck !

[StTwister]

Ok, let me reformulate the problem.

I got a weighted graph (not necesrilly connected) and i must split the nodes into 2 sets in such way that the sum of edges between nodes from the SAME set is maximum.

I think that all I need to do is to split them in 2 sets in such way that the sum of edges between nodes from different sets is minimum, so I'd need to do that WIHTOUT deleting any edges.

So I guess i was wrong as it is not a bipratita graph (since i wont be deleting any edges).

Thanks for your help and sorry for my faulty explanation, I'd like to hear from you again :)

[Zachm]

One last question:
Are there any edges with negative weight in the graph ?

[StTwister]

No, all edges have positive weight

[Zachm]

There might be a really simple solution, but I don't see it right now.
I thought of a rather complex algorithm which I'll try to describe.

Problem formulation: Given a non-directed weighted graph G=(V,E),
The objective is to divide all nodes in V into two sets, A and B, such that the weight-sum of all edges from A to B is minimum.

Let's divide into 2 cases -

Case A: Graph has n unconnected components (n>1).

In this case, let's arbitrarily give each of the components a number, 1..n.
Now, let's assign all nodes of component 1 to set A and all other nodes to set B. Clearly there are no edges from A to B since component 1 is not connected to any of the other components. The objective is complete.

Case B: Graph is connected (No independet non-connected components).

The objective is to find a set of edges E' which is a subset of E which is the lightest Min-Cut in the graph.

A Min-Cut in a graph is a term used in Flow Networks which is connected to the maximum flow possible in a network, given a source node S and a sink node T (See the Max-Flow/Min-Cut theorem (http://en.wikipedia.org/wiki/Max_flow_min_cut_theorem)).
The Min-Cut can be derived from the Ford-Fulkerson algorithm (http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm) for finding max-flow in a flow-network.

Arbitrarily selecting a pair of nodes to be S and T might not be enough since the Min-Cut is dependent on the source and the sink.
In order to find the lightest Min-Cut in G, I think one should find the "All-Pairs" Min-Cut - I'll try to describe the algorithm in psuedo-code:

1. Initialize a |V|x|V| matrix M with zero's
(M[i][j] == 1 if and only if a Min-Cut was found when S==i and T==j).

2. Initialize MinFlow <-- Infinity

3. Initialize a set of edges, MinCut <-- Empty

4. For i <-- 1 to |V| do
For j <-- 1 to |V| do
If M[i][j] == 0 Then
a. (MaxFlow, E') <-- Ford-Fulkerson(i,j)
b. If MaxFlow < MinFlow Then
b.1 MinFlow <-- MaxFlow
b.2 MinCut <-- E'
End If
c. M[i][j] <-- 1; M[j][i] <-- 1
End If
Next j
Next i


Notations:
* Ford-Fulkerson(i,j) means: "Run the Ford-Fulkerson algorithm on G where i is source node and j is sink node". The output of such action is a value of the max-flow in the network (equals to the weight-sum of the Min-Cut), and a set of edges, E' which is the edges part of the Min-Cut found (can be derived from the algorithm with minor changes).

* MaxFlow is a value - result of the Ford-Fulkerson algorithm.

* MinFlow by the end of the run will be the minimum MaxFlow found of all the Ford-Fulkerson runs.

* MinCut is a set of edges that by the end of the run will be the lightest Min-Cut of all the source-sink pairs in G.

Complexity: O(|V|^2) runs of the Ford-Fulkerson algorithm, each done (with Edmonds-Karp method) with complexity of O(|V|^2 x |E|), this gives a total complexity of O(|V|^4 * |E|). Doesn't seem very fast, but still polynomial. Other methods of reducing the number of Ford-Fulkerson runs may be applicable (like excluding nodes after deducting they don't have a chance of improving the Min-Cut). More thought can be given to this matter.

Any comments / suggestions / corrections are more than welcome.

Best of luck !

[StTwister]

Thanks for your really nice solution. Unfortunately, the complexity is a bit big indeed, but that's fine so far, since I don't have any other solution yet.

I'll start implementing this solution right away and tell you the results.