I'm looking for an optimal and heuristic algorithms to solve the following
two graph coloring problems:

Given a graph and a fixed number of colors:

 find a subset of the nodes, and an assignment of colors to the nodes in
 that subset, such that adjacent nodes are assigned different colors and
 such that one of the two following objective functions is maximized:

 1) the number of nodes in the subset, or
 2) the sum of the degrees of the nodes in the subset.

Any suggestions or pointers relating to these problems would be appreciated.

Thanks,

Waleed Meleis
mel...@ece.neu.edu

In article <5o6l69$...@chaos.dac.neu.edu>,
  mel...@vlsi47.ece.neu.edu (Waleed Meleis) wrote:

these are indeed interesting problems because in practice,
e.g. in class scheduling problems, the graph is usually not exactly fixed.
Often some local changes in the graph are allowed
so it is of great value to find a small set of vertices
apart from which the remainder of the graph can be legally k-colored.
One might then try and change the graph locally at these nodes.

I assume that in case of problem (2) you mean to maximize
the number of edges in a k-colorable induced subgraph H of G.
Problem (1) is not only NP-complete but even hard to approximate
to a factor of n^{\epsilon}, see

  Lund, C., Yannakakis, M.,
  The Approximation of Maximum Subgraph Problems,
  in: Proc. ICALP'91, Eds. Lingas, A., Karlsson, R., Carlsson, S.,
  Springer LNCS 700, 1993, 40-51.

For O(n(\log\log n/\log n)^2))-approximative algorithms see

  Halldorsson, M.M.: Approximations via partitioning,
  JAIST Technical Report IS-RR-95-0013F, Hokuriku, March 1995;
  available at URL: http://www.rhi.hi.is/~mmh/index_e.html

The (dual) node-deletion problem, i.e. finding the minimum number
of nodes such that the remainder of the graph is k-colorable
is still MAX-SNP-hard though it seems easier to approximate.
It would be interesting to know whether something similar holds
for problem (2).

An exact algorithm for the problems should in some way or another
enumerate all (k+1)-partitions of the graph at hand with the understanding
that the (k+1)-th partition class need not form an independent set (i.e.
a color class) in G. The classical backtracking algorithm of Brown [1972]
with the saturation-largest-first amendments
(via dynamic reordering of the vertices), see

  Kubale, M., Jackowski, B.:
  A generalized implicit enumeration algorithm for graph coloring,
  Comm. ACM 28, 1985, 412-418.

  Korman, S.M.:
  The graph-colouring problem,
  in: Combinatorial optimization,
  Eds. Christofides, N., Mingozzi, A., Toth, P., Sandi, C.,
  Wiley, New York, 1979, 211-235.

can then easily be adapted to operate on a fixed number of colors
and incorporate a bounding strategy for the new objection function
(number of nodes [resp. edges] in the first k partition classes).

As to heuristics a wide range of ideas seem applicable.
For problem (2) I should think the Recursive-Largest-First heuristic:

  Leighton, F.T.:
  A graph coloring algorithm for large scheduling problems,
  J. Res. Nat. Bur. Stand. 84, 1979, 489-506.

would yield reasonable results. In any case
I would try and compare Simulated Annealing

  Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.:
  Optimization by simulated annealing: an experimental evaluation;
  Part II: graph coloring and number partitioning,
  Oper. Res. 39, 1991, 378-406.

and Tabu-Search

  Hertz, A., Taillard, E., De Werra, D.: Tabu search,
  in: Local search in combinatorial optimization,
  Eds. Aarts, E., Lenstra, K.,
  Wiley, Chichester, 1997, 121-136.

In general, the standard reference for graph coloring theory is

  Jensen, T.R., Toft, B.:
  Graph coloring problems,
  Wiley-Interscience, New York, 1995.

As to state-of-the-art algorithms for graph coloring see

  Cliques, coloring, and satisfiability,
  Eds. Johnson, D.S., Trick, M.,
  DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
  Vol. 26, AMS, 1996.

For information about graph (coloring) software, benchmarks and other
resources available over the net you might like to visit the WWW-page

  Graphs: Theory - Algorithms - Complexity
  http://www.informatik.hu-berlin.de/~weinert/graphs.html

Best regards,
Thomas Emden-Weinert
                                                ,,,,
                                               [o o]
+-----------------------------------------oOOo-`(_)'-oOOo---------+
| Thomas Emden-Weinert                                            |
|                                                                 |
| Tel. +49-30-20181-297           Humboldt-Universit"at zu Berlin |
| Fax  +49-30-20181-296                  Institut f"ur Informatik |
| wein...@informatik.hu-berlin.de                  D-10099 Berlin |
| http://www.informatik.hu-berlin.de/~weinert             Germany |
+-----------------------------------------------------------------+

-------------------==== Posted via Deja News ====-----------------------
      http://www.dejanews.com/     Search, Read, Post to Usenet