Graph partitioning problem

Question 1

Describe the graph partitioning problem

Answer 1

The graph partitioning problem is a problem in which we have a graph G(V,E), and two sets A and B.

We want to pot the nodes v in V into either A or B such that the edges crossing from A to B is minimized.

Question 2

With v in V, what is E(v) = external(v) and I(v) = interal(v)?

Answer 2

With some node v, E(v) are the edges crossing from v’s set to the other set.

I(v) are v’s edges connected to other nodes in v’s set.

Question 3

With some v in V, what is diff(v)?

Answer 3

diff(v) = external(v) - internal(v).

Question 4

How do you interpret diff(v)?

Answer 4

diff(v) is the difference between internal and external edges for some node. It tells us something about how much of an improvement we can expect when moving v to the other set.

Moving v to the other set might improve diff(v). Does it decrease diff(w) for w in V, v =/= w?

Question 5

How do you improve this problem?

Answer 5

You can exchange pairwise nodes a and b.

Question 6

How do you calculate the gain of swapping two nodes?

Answer 6

gain(a,b) = diff(a) + diff(b) - 2.