Due 4/27/99

In circuit board layout and VLSI design problems it is often the case that we are interested in partitioning the components into two sets so that there is a minimum number of wires running between the two sets of components.  We can abstract this problem as the following optimal graph partitioning problem:

Input: An undirected graph G = (V,E) with an even number of vertices.
Output: Sets X and Y such that X and Y are disjoint, X union Y = V, X and Y have the same number of vertices, and the number of edges from X to Y is minimal.

Example 1:  a  -  b  - c  - d
            \     /    \    /
               e         f

If X = {a, b, c} and Y = {d, e, f } then there are 4 edges between X and Y, namely {a,e}, {b,e}, {c,d}, {c,f}.  This is not so good because there is a better partition X = {a, b, e} and Y = {c, d, f} which has only one edge {b,c} between them.  This is an optimal partition.

I know that finding the optimal partition is NP-hard so I want to consider local search algorithms, perhaps simulated annealing to solve this problem.  The first step in setting this problem up as a local search problem is to define the solution space and the neighborhood of a solution.

1. Define the solution space for this problem.
2. Define the move relation that takes a solution to one of its neighbors.
3. Show that any solution is reachable from any other by a sequence of moves.
4. Using the local search structure you have defined design a steepest descent greedy search algorithm.  For your algorithm it is not necessary to give details of the data structures, just the high level design.

Run your steepest descent algorithm on the following graph

Example 2:  a  -  b  - c  - d  -----  k         l
            \     /    \    /        /  \      /  \
               e         f         g  -  h  - i  - j
 

with starting partition X = {a, b, c, d, k, l} and Y = {e, f, g, h, i, j} to see if steepest descent reaches the global minimum.

5.   Give a brief evaluation of the greedy steepest descent algorithm. Would you recommend greedy steepest descent as the best way to find an optimal graph partition?