Re: need an algo for graph-coloring...

[EMAIL PROTECTED] (Paltis) wrote in message news:<[EMAIL PROTECTED]>...

> I have a non-oriented connected graph 
> (the only thing I know about it) and
> I have to color each vertex with either
> black or white color (only two possible colors).
> 
> I'm looking for any reference or algorithm
> (on-line if possible)
> allowing to color the vertices so that 
> the number of edges connecting two vertices 
> with the same color is minimized.
> 
> I would prefer "exact" methods, or
> "approached" methods with proved convergence
> to a stable locally minimal color configuration.

If all you need is a local optimum, that isn't too hard.
Start with any solution.
Improve the solution by reversing the color of a vertex until it can't
be done anymore.
The number of edges is an obvious upper bound on the number of
reverses.

If you want an optimal solution, I suspect you're in NP-completeness
territory.

You'll probably want a solver that can deal with quadratic terms in
the objective.
The all gray solution will be in the convex hull of any linearization
and it will be optimal.
That problem can be alleviated somewhat by forcing a decision on one
vertex.

You might want to look at the strategy employed by QUALEX.
It won't guarantee you an optimal solution, but it's likely to
give you good feasible solutions and it will give you lower bounds.

If you go the ILP route, I think that you will need a huge number of
cutting planes.
The following are theoretically sufficient, but feeding them to a B&B
solver would result in a long wait.

min  sum cost[a,b]
   {a,b} in Edges
s.t.
cost[a,b] >= 1 - white[a] - white[b]   for {a,b} in Edges
cost[a,b] >= white[a] + white[b] - 1   for {a,b} in Edges

white binary


One can add more constraints, e.g.:
  sum cost[a,b] >= (|S|-1)**2/4   for S the vertices of a clique
  a<b                                 |S| odd
{a,b} in S

There is a similar formula for even sized cliques.
One can also define constraints that bound the cost of a clique by a
linear function of the number of white vertices.

One won't need them all, but deciding which ones are needed is a
non-trivial task.


It's also fairly easy to find a solution that cannot be improved by
changing two  vertices.
When changing a single vertex can no longer improve the solution, look
at vertices that you can flip without harming the solution.
Iff two of them are adjacent and of opposite color, then reversing
both of them will improve the solution.