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.

  • 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$!2012-02-09
  • 1
    @draks: That need not be minimal, e.g. two triangles joined by an edge.2012-02-09
  • 0
    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.2012-02-09
  • 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