1
$\begingroup$

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.

  • 0
    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:12012-05-04

1 Answers 1

4

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.

  • 0
    Thanks, you are right, I've fixed the question.2012-02-09