Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To solve a programming problem, I need to solve a graph problem, but I am weak at graph theory.

Given an undirected graph $G$ with edges $E$, I need to find $n=2$ subgraphs $G_1$ and $G_2$, so that $G_1 \cap G_2 = \emptyset $ and $G_1 \cup G_2 = G$, and the number of edges, where edge $u - v$ where $u \in G_1 $ and $v \in G_2 $ are minimal. For extra points I'm interested in alternative partiotions, other cases, where $n>2$, or solution for weighted graphs, but they are not important.

For the curious, the programming problem is to divide a big class into smaller classes.

share|improve this question
1  
Select a point with minimal degree. This will be $G_1$, the rest is $G_2$. Maybe you state something about the number of vertices inside $G_k$! –  draks ... Feb 9 '12 at 11:46
1  
@draks: That need not be minimal, e.g. two triangles joined by an edge. –  Chris Eagle Feb 9 '12 at 12:32
    
Sorry, timed out, and cannot format well, so as a new comment: Suppose I have $G = \{a,b,c,d,e,f\}$ and $E=\{\{a,b\},\{b,c\},\{c,a\},\{d,e\},\{e,f\},\{f,d\}\}$. Your solution will cut 2 edges, but I can have $G_1=\{a,b,c\}$ and $G_2 = \{d,e,f\}$ with 0 cuts. Even if I make this graph connected with an edge $ \{c,d\} $, your solution will still miss the optimal solution. –  pihentagy Feb 9 '12 at 12:40
    
Ok, aelguindy answered the question, but I still has some concerns. Given the following graph (that would be the case with many graphs), it is easy to cut one node from the graph with minimal cut. So cut e--h in { a--b b--c c--a d--e e--f f--d a--d a--d e--h } However, it is a bad refactor to split a 100 node graph to 99:1 –  pihentagy May 4 '12 at 13:32
add comment

1 Answer 1

What you are looking for is called a graph cut, usually one means a partition of the graph into 2 parts. Computing the minimum cut for a graph can be solved using $n - 1$ max-flow computations, or even faster (see this).

Splitting the graph into $k$ parts with the minimum number of removed edges is NP-complete (see this). If however $k$ is constant, you can compute it in $O(|V|^{k^2})$ (see the same link).

By the way, I am assuming that your "segments" form a partition of the graph (that is, their union is the entire graph), if not, then choose your segments to be empty sets.

share|improve this answer
    
Thanks, you are right, I've fixed the question. –  pihentagy Feb 9 '12 at 12:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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