COLOR02/03/04:
Graph Coloring and its Generalizations
Announcements
COLOR02/03/04 is a series of activities to effort to encourage research on
computational methods for graph coloring problems, to
evaluate alternative approaches using a common testbed, and to
stimulate discussion on present and future directions in computational
combinatorial optimization.
The Series consists of two workshops and one volume of refereed
papers.
- A Computational Symposium was held in conjunction with Constraint
Programming 2002 at Cornell University, Ithaca, NY USA September 7-8,
2002. Fifteen papers were presented.
- A group of sessions will be held at the International Symposium on Mathematical
Programming in Copenhagen August 18-22.
- A volume of refereed papers will be published as a special issue
of Discrete Applied Mathematics. Due date for submissions:
March 15, 2004.
Mailing List
Join the mailing list for
ongoing information.
Computational Symposium (CP2002)
A Computational Symposium was held in conjuction with Constraint Programming
2002.
- Initial Announcement
- List of papers accepted for
presentation at the symposium.
- Symposium
Schedule
- Summary of Symposium (Powerpoint
presentation by Trick
- Summary of Computational Results (HTML)
- In these sheets (note the buttons labeled Heuristics, Optimality,
Bandwidth: each points to a different sheet), T stands for time
reported, MT is modified time (time if the benchmark had taken 100),
and the letters at the head of each column is the authors
initials. Heuristics: CLGA (Croitoru et al.), GHZ (Galinier et al.),
BP (Bui and Patel), PS (Phan and Skiena), CS (Chiarandini and
Stuetzle). Optimization: CD (Caramia and Dell'Olmo), AVG (van
Gelder), MZ (Mendez Diaz and Zabala). Bandwidth: PS (Phan and
Skiena), P (Prestwich).
- Summary of Computational Results (Excel spreadsheet)
Math Programming Symposium
A series of 3-4 sessions will be held at International Symposium on Mathematical
Programming, Copenhagen, Denmark, August 18-22.
Deadline for submissions: April 1.
Paper selection: April 25.
Paper submission process:
All extended abstracts should be submitted through our online submission
form. Abstracts should be 5-10 pages in length.
Note: If at all possible, please be sure to attempt to solve
all of the instances listed in the COLOR02 computational results.
Refereed Volume
A refereed volume on this topic will be published by Discrete
Applied Mathematics. Submissions for this volume are solicited
from those who presented at CP2002 and those who present at ISMP2003,
as well as relevant papers not presented at either.
Papers with a computational component must provide solution
values/computation time for the instances marked (*) below (for graph
coloring) or for all the instances given (for the generalizations).
Papers must also provide the times for the Benchmark Program given
below in order to allow cross-paper comparisons.
Full paper submission deadline: March 15, 2004
While no particular paper format is required for submission, there
are latex
style files from Elsevier that may be used.
Paper submission process: Email paper to trick@cmu.edu or send four copies to
Michael Trick
GSIA Room 341B
Carnegie Mellon University
Pittsburgh, PA 15213
USA
Topic
The Series is be on the topic "Graph Coloring and its
Generalizations". This topic was chosen due to the wide applicability
of graph coloring and the variety of solution approaches that have
been proposed. This series builds off of a DIMACS Computational
Challenge from the fall of 1993, where graph coloring was one of the
problems addressed. In addition to the basic graph coloring problem,
results are also solicited for the related problems of
"multi-coloring" (assigning multiple colors to each node) and
bandwidth allocation models (those with minimum difference
requirements on the colors on adjacent nodes).
More formally, given a graph G=(V,E), node weights k(i) and
edge weights d(i,j), we define four problems:
- The graph coloring problem: find the minimum k and
a mapping r from V to 1..k such r(i)<>r(j)
for every edge (i,j).
- The multi-coloring problem: find the minimum k and
assignment of a subset S(i) of 1..k to each i such that the
size of S(i) is k(i) and for each edge (i,j), the
intersection of S(i) and S(j) is empty.
- The bandwidth coloring problem: the graph coloring problem
together with the constraint that the absolute value of the difference
betwen r(i) and r(j) is at least d(i,j) for each
edge.
- The bandwidth multi-coloring problem: the multi-coloring
problem along with the constraint that the absolute value of the
difference between any member of S(i) and S(j) is at
least d(i,j) for each edge. For values d(i,i), this is interpreted to require
differences between distinct values in S(i).
Possible topics suitable for the Series include:
- Exact algorithms for graph coloring
- Constraint programming
- Integer programming
- Semidefinite programming
- Nonlinear approaches
- Heuristic approaches
- Metaheuristics
- Incomplete methods
- Applications and Instances
- Instance generators
- Applications and specially structured instances
- Evaluation of Methods
- Methods for algorithm comparison
- Tools for experimental algorithmics
All papers should have some computational aspect.
Organizers
The organizers of this Series are
- David Johnson, AT&T Labs
- Anuj Mehrotra, University of Miami
- Michael Trick, Carnegie Mellon
Benchmarking Machines and Testing Solutions
Since the computations will be done on different machines, please
download the benchmark tar file,
compile the program dfmax and run the program on r500.b, reporting the
resulting computation time.
Marco Chiarandini has developed a code to test solutions for validity
(updated 2002/10/24).
Chirag Patel has provided a zip file with a modified
benchmark file to work under Windows.
Allen van Gelder has provided a UNIX shell
script to eliminate any duplicate edges in a file (some benchmark
files include both edges (i,j) and (j,i)). Be sure to rename the file
elim_dup.csh to match up with the instructions.
Instances
These graphs are in a modification of the DIMACS file format. Each
line of the graph begins with a letter that defines the rest of the
line. The legal lines are
- c Comment: remainder of line ignored.
- p Problem: must be of form
p edges n m
where n is the number of nodes (to be numbered 1..n) and m the number
of edges.
- e Edge: must be of the form
e n1 n2 d
where n1 and n2 are the endpoints of the edge. The optional d value
is used to enforce a requirement and n1 and n2 have colors that differ
by at least d (if there is no d value, it is assumed d=1).
- f Fixed: of the form
f n1 c1 c2 c3 ...
states that node n1 must choose its colors from c1, c2, c3 ... (the
default is that the node can take on any color).
- n Node: of the form
n n1 c1
used in multicoloring to state that c1 colors must be assigned to node
n1. Any node without a "n" line is assumed to have value 1. These
colors must all differ by at least 1, unless there is an edge of the
form
e n1 n1 d
in which case all the colors at n1 must differ by at least d.
Graph Coloring Instances
In addition to the following instances, Joe Culberson has
generators
for Equipartite IID, Flat, and Evacuation graphs which have a
guaranteed upper bound on the chromatic number. See his notes for
exploring phase transitions. Also, for larger problems, there are
graphs from the clique part of the DIMACS
Challenge.
- (*)DSJC125.1.col (125,736), ?, DSJ
- (*)DSJC125.5.col (125,3891), ?, DSJ
- (*)DSJC125.9.col (125,6961), ?, DSJ
- (*)DSJC250.1.col (250,3218), ?, DSJ
- (*)DSJC250.5.col (250,15668), ?, DSJ
- (*)DSJC250.9.col (250,27897), ?, DSJ
- (*)DSJC500.1.col (500,12458), ?, DSJ
- (*)DSJC500.5.col (500,62624), ?, DSJ
- (*)DSJC500.9.col (500,224874), ?, DSJ
- (*)DSJR500.1.col (500,3555), ?, DSJ
- (*)DSJR500.1c.col (500,121275), ?, DSJ
- (*)DSJR500.5.col (500, 58862), ?, DSJ
- (*)DSJC1000.1.col (1000,49629), ?, DSJ
- (*)DSJC1000.5.col (1000,249826), ?, DSJ
- (*)DSJC1000.9.col (1000,449449), ?, DSJ
- fpsol2.i.1.col (496,11654), 65, REG
- fpsol2.i.2.col (451,8691), 30, REG
- fpsol2.i.3.col (425,8688), 30, REG
- inithx.i.1.col (864,18707), 54, REG
- inithx.i.2.col (645, 13979), 31, REG
- inithx.i.3.col (621,13969), 31, REG
- (*)latin_square_10.col
(900,307350), ?, LAT
- (*)le450_15a.col (450,8168), 15, LEI
- (*)le450_15b.col (450,8169), 15, LEI
- (*)le450_15c.col (450,16680), 15, LEI
- (*)le450_15d.col (450,16750), 15, LEI
- (*)le450_25a.col (450,8260), 25, LEI
- (*)le450_25b.col (450,8263), 25, LEI
- (*)le450_25c.col (450,17343), 25, LEI
- (*)le450_25d.col (450,17425), 25, LEI
- (*)le450_5a.col (450,5714), 5, LEI
- (*)le450_5b.col (450,5734), 5, LEI
- (*)le450_5c.col (450,9803), 5, LEI
- (*)le450_5d.col (450,9757), 5, LEI
- mulsol.i.1.col (197,3925), 49, REG
- mulsol.i.2.col (188,3885), 31, REG
- mulsol.i.3.col (184,3916), 31, REG
- mulsol.i.4.col (185,3946), 31, REG
- mulsol.i.5.col (186,3973), 31, REG
- school1.col (385,19095), ?, SCH
- (*)school1_nsh.col (352,14612), ?, SCH
- zeroin.i.1.col (211,4100), 49, REG
- zeroin.i.2.col (211, 3541), 30, REG
- zeroin.i.3.col (206, 3540), 30, REG
- anna.col (138,493), 11, SGB
- david.col (87,406), 11, SGB
- homer.col (561,1629), 13, SGB
- huck.col (74,301), 11, SGB
- jean.col (80,254), 10, SGB
- games120.col (120,638), 9, SGB
- miles1000.col (128,3216), 42, SGB
- miles1500.col (128,5198), 73, SGB
- miles250.col (128,387), 8, SGB
- miles500.col (128,1170), 20, SGB
- miles750.col (128,2113), 31, SGB
- queen5_5.col (25,160), 5, SGB
- queen6_6.col (36,290), 7, SGB
- queen7_7.col (49,476), 7, SGB
- (*)queen8_12.col (96,1368), 12, SGB
- (*)queen8_8.col (64, 728), 9, SGB
- (*)queen9_9.col (81, 2112), 10, SGB
- (*)queen10_10.col (100,2940), ?, SGB
- (*)queen11_11.col (121,3960), 11, SGB
- (*)queen12_12.col (144,5192), ?, SGB
- (*)queen13_13.col (169,6656), 13, SGB
- (*)queen14_14.col (196,8372), ?, SGB
- (*)queen15_15.col (225,10360), ?, SGB
- (*)queen16_16.col (256,12640), ?, SGB
- myciel3.col (11,20), 4, MYC
- myciel4.col (23,71), 5, MYC
- (*)myciel5.col (47,236), 6, MYC
- (*)myciel6.col (95,755), 7, MYC
- (*)myciel7.col (191,2360), 8,
MYC
- mugg88_1.col (88,146), 4,
MIZ
- mugg88_25.col (88,146), 4,
MIZ
- mugg100_1.col (100,166), 4,
MIZ
- (*)mugg100_25.col (100,166), 4, MIZ
- abb313GPIA.col (1557,
53356), ? HOS --> (corrected 12/29/03)
- ash331GPIA.col (662,4185), ? HOS
- ash608GPIA.col (1216,7844), ? HOS
- ash958GPIA.col (1916,12506), ? HOS
- will199GPIA.col
(701,6772), ? HOS (corrected 12/29/03)
- (*)1-Insertions_4.col (67,232), 4, CAR
- (*)1-Insertions_5.col (202,1227), ?, CAR
- (*)1-Insertions_6.col (607,6337), ?, CAR
- (*)2-Insertions_3.col (37,72), 4, CAR
- (*)2-Insertions_4.col (149,541), 4, CAR
- (*)2-Insertions_5.col (597,3936), ?, CAR
- (*)3-Insertions_3.col (56,110), 4, CAR
- (*)3-Insertions_4.col (281,1046), ?, CAR
- (*)3-Insertions_5.col (1406,9695), ?, CAR
- (*)4-Insertions_3.col (79,156), 3, CAR
- (*)4-Insertions_4.col
(475,1795), ?, CAR
- (*)1-FullIns_3.col 30,100,?CAR
- (*)1-FullIns_4.col 93,593, ?CAR
- (*)1-FullIns_5.col 282,3247,?CAR
- (*)2-FullIns_3.col 52,201, ?CAR
- (*)2-FullIns_4.col 212,1621,?CAR
- (*)2-FullIns_5.col 852,12201,?CAR
- (*)3-FullIns_3.col 80,346,?CAR
- (*)3-FullIns_4.col 405,3524,?CAR
- (*)3-FullIns_5.col 2030,33751,?CAR
- (*)4-FullIns_3.col 114,541,?CAR
- (*)4-FullIns_4.col 690,6650,?CAR
- (*)4-FullIns_5.col 4146,77305,?CAR
- (*)5-FullIns_3.col 154,792,?CAR
- (*)5-FullIns_4.col 1085,11395,?CAR
- wap01a.col (2368,110871), ?, KOS
- wap02a.col (2464,111742), ?, KOS
- wap03a.col (4730,286722), ?, KOS
- wap04a.col (5231,294902), ?, KOS
- wap05a.col (905,43081), ?, KOS
- wap06a.col (947,43571), ?, KOS
- wap07a.col (1809,103368), ?, KOS
- wap08a.col (1870,104176), ?, KOS
- qg.order30.col
(900,26100), 30, GOM
- qg.order40.col
(1600,62400), 40, GOM
- qg.order60.col
(3600,212400), 60, GOM
- qg.order100.col (10000,990000), 100, GOM
Notes:
- DSJ: (From David Johnson
(dsj@research.att.com)) Random graphs
used in his paper with Aragon, McGeoch, and Schevon, ``Optimization by
Simulated Annelaing: An Experimental Evaluation; Part II, Graph
Coloring and Number Partitioning'', Operations Research, 31, 378--406
(1991). DSJC are standard (n,p) random graphs. DSJR are geometric
graphs, with DSJR..c being complements of geometric graphs.
In some papers, the edge count is twice that given here since
both (i,j) and (j,i) are counted.
- CUL: (From Joe Culberson
(joe@cs.ualberta.ca)) Quasi-random coloring problem.
- REG: (From Gary Lewandowski
(gary@cs.wisc.edu)) Problem based on register allocation for variables
in real codes.
- LEI: (From Craig Morgenstern
(morgenst@riogrande.cs.tcu.edu)) Leighton graphs with guaranteed
coloring size. A reference is F.T. Leighton, Journal of Research of
the National Bureau of Standards, 84: 489--505 (1979).
- SCH: (From Gary Lewandowski
(lewandow@cs.wisc.edu))Class scheduling graphs, with and
without study halls.
- LAT: (From Gary Lewandowski (lewandow@cs.wisc.edu))
Latin square problem.
- SGB: (From Michael Trick (trick@cmu.edu)) Graphs from Donald Knuth's Stanford GraphBase. These can be divided into:
- Book Graphs. Given a work of literature, a graph is created where
each node represents a character. Two nodes are connected by an edge
if the corresponding characters encounter each other in the book.
Knuth creates the graphs for five classic works:
Tolstoy's Anna Karenina (anna), Dicken's David
Copperfield (david), Homer's Iliad (homer),
Twain's Huckleberry Finn (huck), and Hugo's Les
Mis\'erables (jean).
- Game Graphs. A graph representing the games played in a
college football season can be represented by a graph where the nodes
represent each college team. Two teams are connected by an edge if
they played each other during the season. Knuth gives the
graph for the 1990 college football season.
- Miles Graphs. These graphs are similar to geometric graphs
in that nodes are placed in space with two nodes connected if they are
close enough. These graphs, however, are not random. The nodes
represent a set of United States cities and the distance between them
is given by by road mileage from 1947. These graphs are also due to
Kuth.
- Queen Graphs. Given an n by n chessboard, a queen
graph is a graph on n^2 nodes, each corresponding to a square of the
board. Two nodes are connected by an edge if the corresponding
squares are in the same row, column, or diagonal. Unlike some of the
other graphs, the coloring problem on this graph has a natural
interpretation: Given such a chessboard, is it possible to place n
sets of n queens on the board so that no two queens of the same set
are in the same row, column, or diagonal? The answer is yes if and
only if the graph has coloring number n. Vasek Chvatal
has a page
on such colorings.
- MYC: (From Michael Trick (trick@cmu.edu))
Graphs based on the Mycielski transformation. These graphs are
difficult to solve because they are triangle free (clique number
2) but the coloring number increases in problem size.
- MYC: (From Kuzunori Mizuno
(mizuno@algor.is.tsukaba.ac.jp) Graphs that are almost
3-colorable, but have a hard-to-find four clique embedded.
- HOS: (From Shahadat Hossain) Graphs
obtained from a matrix partitioning problem in the segmented
columns approach to determine sparse Jacobian matrices.
- CAR: (From M. Caramia caramia@iac.rm.cnr.it
and P. Dell'Olmo paolo.dellolmo@uniroma1.it) k-Insertion graphs
and Full Insertion graphs
are a generalization of myciel graphs with inserted nodes to
increase graph size but not density.
- KOS: (From Arie Koster koster@zib.de) From
real-life optical network design problems. Each vertex
corresponds to a lightpath in the network; edges correspond to
intersecting paths. (Corrected June 28, 2002 and replaced by
wap?a.col instances: nodes now numbered from 1 to n)
- GOM: (From Carla Gomes
gomes@cs.cornell.edu) Latin squares (standard encoding).
Coloring with Fixed Sets
In the following, some or all nodes must choose from the sets given by
"f" lines.
Notes:
- GOM1 Encodings of latin square problem. See readme for more information.
Bandwidth and multicoloring instances
The following can be used in bandwidth (edge weights) multicoloring
(node weights) or both simply by ignoring unwanted information (edge
weights for multicoloring and node weights for bandwidth). They can
even be used for graph coloring by ignoring both!
- GEOM20.col (20,40) GEO
- GEOM20a.col (20,57) GEO
- GEOM30.col (30,80) GEO
- GEOM30a.col (30,111)GEO
- GEOM40.col (40,118) GEO
- GEOM40a.col (40,186) GEO
- GEOM50.col (50,177) GEO
- GEOM50a.col (50,288) GEO
- GEOM60.col (60,245) GEO
- GEOM60a.col (60,339) GEO
- GEOM70.col (70,337) GEO
- GEOM70a.col (70,529) GEO
- GEOM80.col (80,429) GEO
- GEOM80a.col (80,692) GEO
- GEOM90.col (90, 531) GEO
- GEOM90a.col (90,879) GEO
- GEOM100.col (100,647) GEO
- GEOM100a.col (100,1092) GEO
- GEOM110.col (110,748) GEO
- GEOM110a.col (110,1317) GEO
- GEOM120.col (120,893) GEO
- GEOM120a.col (120,1554) GEO
- GEOM20b.col (20,52) GEO
- GEOM30b.col (30,111)GEO
- GEOM40b.col (40,197) GEO
- GEOM50b.col (50,299) GEO
- GEOM60b.col (60,426) GEO
- GEOM70b.col (70,558) GEO
- GEOM80b.col (80,743) GEO
- GEOM90b.col (90,950) GEO
- GEOM100b.col (100,1150) GEO
- GEOM110b.col (110,1366) GEO
- GEOM120b.col (120,1611) GEO
- DSJC125.1g.col (125,736), ?, DSJ
- DSJC125.5g.col (125,3891), ?, DSJ
- DSJC125.9g.col (125,6961), ?, DSJ
- myciel5g.col (47,236), ?, MYC
- myciel6g.col (95,755), ?, MYC
- myciel7g.col (191,2360), ?,
MYC
- queen8_8g.col (64, 728), ?, SGB
- queen9_9g.col (81, 2112), ?, SGB
- queen10_10g.col (100,2940), ?, SGB
- queen11_11g.col (121,3960), ?, SGB
- queen12_12g.col (144,5192), ?, SGB
- DSJC125.1gb.col (125,736), ?, DSJ
- DSJC125.5gb.col (125,3891), ?, DSJ
- DSJC125.9gb.col (125,6961), ?, DSJ
- myciel5gb.col (47,236), ?, MYC
- myciel6gb.col (95,755), ?, MYC
- myciel7gb.col (191,2360), ?,
MYC
- queen8_8gb.col (64, 728), ?, SGB
- queen9_9gb.col (81, 2112), ?, SGB
- queen10_10gb.col (100,2940), ?, SGB
- queen11_11gb.col (121,3960), ?, SGB
- queen12_12gb.col (144,5192), ?, SGB
- R50_1g.col
- R50_5g.col
- R50_9g.col
- R75_1g.col
- R75_5g.col
- R75_9g.col
- R100_1g.col
- R100_5g.col
- R100_9g.col
- R50_1gb.col
- R50_5gb.col
- R50_9gb.col
- R75_1gb.col
- R75_5gb.col
- R75_9gb.col
- R100_1gb.col
- R100_5gb.col
- R100_9gb.col
Notes:
- GEO Geometric graphs generated by Michael
Trick. Points are generated in a 10,000 by 10,000 grid and are
connected by an edge if they are close enough together. Edge weights
are inversely proportional to the distance between nodes; Node
weights are uniformly generated. (Note, I do not know how hard this
problem is, so if the 120 is too easy, let me know so I can generate
larger instances). The GEOMn instances are sparse; GEOMa and GEOMb
instances are denser; GEOMb requires fewer colors per node.
- Other instances are for multicoloring: the "g.col" are the
corresponding coloring instances with node weights uniformly generated
between 1 and 5; the "gb.col" have node weights uniformly generated
between 1 and 20.
Further Information
The primary source of information for this Series is the web page:
http://mat.gsia.cmu.edu/COLORING03
Interested in the Series? Join the mailing list for ongoing
information.
Bibliographies
- koster.doc
- Description: Annotated Bibliography on Frequency Assignment by
Dr. Ir. Arie M. C. A. Koster (koster@zib.de) available at
http://fap.zib.de
- L(h,k) page
- Description: Survey of L(h,k) labelling results by
Dr. Tiziana Calamoneri (calamo@dsi.uniroma1.it).
- marco.ps marco.pdf
- Description: Graph coloring bibliography by Dr. Marco Chiarandini
(machud@intellektik.informatik.tu-darmstadt.de).
- Elsevier-web-of-science.doc
- Description: Abstracts found on Elsevier and on Web of Science by
a search for graph coloring and frequency assignment.
- international-abstracts-in-or.doc
- Description: Abstracts found in International Abstracts in O.R. by a
search for graph coloring and frequency assignment.
Links
Some links that may help in this Series: