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.

• qwhdec.order18.holes120.1.col GOM1
• qwhdec.order30.holes316.1.col GOM1
• qwhdec.order30.holes320.1.col GOM1
• qwhdec.order33.holes381al.1.col GOM1
• qwhdec.order35.holes405.1.col GOM1
• qwhdec.order40.holes528.1.col GOM1
• qwhdec.order5.holes10.1.col GOM1
• qwhdec.order50.holes750al.1.col GOM1
• qwhdec.order50.holes825al.1.col GOM1
• qwhdec.order60.holes1080al.1.col GOM1
• qwhdec.order60.holes1152al.1.col GOM1
• qwhdec.order60.holes1440.1.col GOM1
• qwhdec.order60.holes1620.1.col GOM1
• qwhdec.order70.holes2450.1.col GOM1
• qwhdec.order70.holes2940.1.col GOM1
• qwhopt.order18.holes120.1.col GOM1
• qwhopt.order30.holes316.1.col GOM1
• qwhopt.order30.holes320.1.col GOM1
• qwhopt.order33.holes381al.1.col GOM1
• qwhopt.order35.holes405.1.col GOM1
• qwhopt.order40.holes528.1.col GOM1
• qwhopt.order5.holes10.1.col GOM1
• qwhopt.order50.holes750al.1.col GOM1
• qwhopt.order50.holes825al.1.col GOM1
• qwhopt.order60.holes1080al.1.col GOM1
• qwhopt.order60.holes1152al.1.col GOM1
• qwhopt.order60.holes1440.1.col GOM1
• qwhopt.order60.holes1620.1.col GOM1
• qwhopt.order70.holes2450.1.col GOM1
• qwhopt.order70.holes2940.1.col GOM1

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:

• Michael Trick's Coloring Page. Out of date, but complete with regards to the DIMACS Challenge and other work.
• Joe Culberson's Page Great page with lot's of interesting links.
• Andrew Appel's Sample Graph Coloring Problems based on actual code segments for register-interference.
• SUNY Stoney Brook Archive page on vertex coloring has pointers to some implementations.
• Peter Ross's graph-coloring generators, by William Spears.
• Geometry Junkyard page on colorings.