To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
Introduction to the Second DIMACS Challenge: Cliques, Coloring, and
Satisfiability
DAVID S. JOHNSON AND MICHAEL A. TRICK
1. The Second DIMACS Challenge
The purpose of a DIMACS Challenge is to encourage and coordinate research in the experimental analysis of algorithm. The First DIMACS Challenge [14] specifically encouraged experimetal work in the area of network flow and matchings. This Second DIMACS Challenge, which took place in conjunction with the DIMACS Special Year on Combinatorial Optimization, addressed three difficult combinatorial optimization problems: finding cliques in a graph, coloring the vertices of a graph, and solving instances of the satisfiability problem. These problems were chosen both for their practical interest and because of their theoretical intractability.
The Challenge began in September 1992, and culminated in a three-day workshop held at the DIMACS Center at Rutgers University in October, 1993. The electronic mailing list for the Challenge consisted of more than 250 people from all around the world, and the workshop itself had more than 100 participants. This volume contains revised and refereed versions of 28 of the papers presented at the workshop. Preliminary drafts were circulated at the workshop. These were then revised in response to feedback from workshop participants and subjected to a rigorous refereeing process that in many cases caused further revision and additional experimentation before yielding the versions you see here.
The papers were only part of outcome of the Challenge. Over the course of the year, DIMACS acted as a repository for data, sample codes, bibliographies, draft papers, and analysis tools, and these are all still available via the World Wide Web, as explained later in this introduction. Included in this material are benchmark codes and test problems. In the papers of this volume there are two aspects to the computational tests. First, authors have designed experiments that they feel best illustrate their work. Second, they present results for a standard set of benchmark test instances in their problem domain. These benchmark results, along with the running times they report for two benchmark codes on the machines they used, should make it easier for readers to compare the results of different authors.
2. The Problems
For this Challenge, we wanted to choose a small number of difficult combinatorial optimization problems that had both practical and theoretical interest. We chose to concentrate on finding cliques in graphs, coloring graphs, and solving satisfiability problems. The following defines these problems.
2.1. Cliques and Colorings. Given an undirected graph G = (V, E), a clique of the graph is a set of mutually adjacent vertices. A maximum clique is, naturally, a clique whose number of vertices is at least as large as that for any other clique in the graph. If the vertices have weights then a maximum weighted clique is a clique with the largest possible sum of vertex weights.
A (vertex) coloring of an undirected graph is an assignment of a label to each vertex. It is required that the labels on the pair of vertices incident to any edge be different. A minimum coloring of a graph is a coloring that uses as few different labels as possible. Clique and coloring problems are very closely related. It is straightforward to see that the size of the maximum clique is a lower bound on the minimum number of labels needed to color a graph.
Both of these problems are formally NP-hard for general graphs [13]. It therefore seems unlikely that it will be possible to find a fast (i.e. polynomial-time) algorithm to solve these problems exactly. In fact, based on the results of [10, 2, 1, 16, 3] it seems unlikely that it is even possible to find an approximate solution to these problems quickly: Bellare, Goldreich and Sudan [3] show that, assuming $P \new NP$ , for any $\epsilon \geq 1/4$ (for clique, $1/7$ for coloring) no polynomial time approximation algorithm can find a solution that is guaranteed to be within a ratio of $| V | ^{\epsilon}$ of optimal.
Many problems of practical interest can be modeled as clique and coloring problems. The general form of these applications involves forming a graph with vertices representing items of interest. An edge connects two "incompatible" items. The maximum clique problem is then to find as large a set of pairwise incompatible items as possible. The minimum coloring problem is to group the items into as few groups as possible, subject to the constraint that no incompatible items end up in the same group. Examples of applications include time tabling and scheduling (Leighton [15], Opsut and Roberts [181, and de Werra [9]), radio frequency assignment (Gamst [11]), computer register allocation (Chaitin [5], Chaitin et. al [6], Chow and Hennessy [7, 81, and Briggs, Cooper, Kennedy, and Torczon [4]), printed circuit board testing (Garey, Johnson, and So [12], Yu,Goldschmidt and Chen [19] and Yu. Kouvelis, and Luo [20]), and pattern matching (Ogawa [17]).
2.2. Satisfiability. The Satisfiability Problem (SAT) and its close relative, the Maximum Satisfiability Problem (MAX-SAT) are central problems in artificial intelligence, logic, and computational complexity. These problems can be defined as follows:
A boolean variable x is a variable that can assume only the values true or false (sometimes denoted 1 or 0 respectively). A boolean formula is a combination of boolean variables using the logical connectives not $\overline{x}$, or ($\bigvee$), and and ($\bigwedge$). A variable or a negation of a variable is called a literal. A disjunction of literals is called a clause.
Given a set of clauses $C_l, C_2,... , C_n$ on the variables $x_1, x_2, ..., x_n$, the satisfiability problem is to determine if the formula
is satisfiable. That is, is there an assignment of values to the variables so that the above formula evaluates to true. Clearly, this requires that each $C_j$ evaluate to true. The maximum satisfiability problem is to find an assignment of values to the variables so that the largest number of clauses evaluate to true.
3. The Papers
While there are some relationships between the problems (clique size and coloring numbers provide bounds for each other, both clique and coloring problems can be formulated as satisfiability problem), most of the participants of the Challenge chose to concentrate on one of the problems. The papers in this volume are divided by problem type.
3.1. Cliques. The papers on finding cliques in a graph are a mixture of exact and heuristic methods.
A variety of heuristic techniques were examined for finding cliques. Balas and Niehaus note that finding the maximum clique in the union of two cliques is solvable by matching techniques, and provide a heuristic based on this. Gibbons, Hearn, and Pardalos look at a continuous-variable formulation of the problem and provide a heuristic based on rounding. Both Grossman and Jagota, Sanchis and Ganesan look at neural network approaches. Soriano and Gendreau look at a different type of general heuristic technique: tabu search. Goldberg and Rivenburgh use a restricted backtracking method to provide a tradeoff between quality of clique and completeness of search. Homer and Peinado develop a plynomial time heuristic based on subgraph exclusion and apply it to very large instances.
There were three groups who used different relaxations of the problem in order to create improved exact algorithms. Balas, Ceria, Cornuejols, and Pataki use a "Lift and Project" method to find good bounds. Mannino and Sassano use an edge projection method to create both a heuristic and an improved branch and bound exact algorithm. Bourjolly, Gill, Laporte and Mecure look at strengthening relaxations of a quadratic 0-1 formulation.
Brockington and Culberson are concerned not with solving clique problems but with generating them. They show how to "hide" large cliques in graphs thatlook like random graphs.
3.2. Graph Coloring. This topic attracted the fewest participants, perhaps due to its difficulty. While clique algorithms were developed that could routinely solve graphs with hundreds of vertices, the graph coloring algorithms tended to be ineffective on random graphs with as few as seventy vertices.
Sewell provides an exact graph coloring algorithm, based on improved upper and lower bounding methods, as was as a new branching rule. Culberson and Luo look at a new greedy heuristic involving an iterated greedy method with a clever reordering between iterations. Glover, Parker, and Ryan have a tabu search technique that can be used to find either heuristic or optimal colorings. Morgenstern uses a distributed computing enviroment to explore some neighborhood search methods. Lewandowski and Condon use parallel computing for some similar heuristics.
3.3. Satisfiability. The satisfiability problem attracted a great deal of interest, perhaps because of the broadness of its application.
There were a number of exact algorithms developed. Dubois, Andre, Boufkhad, and Carlier look at a specialization of an exact method for finding satisfying assignments when it is suspected that no such assignment exists. Van Gelder and Tsuji suggest an exact algorithm that attempts to deduce the effects of setting variables and looks for equialent literals to simplify the problem. Jaumard, Stan, and Desrosiers develop a general algorithm based on tabu search heuristics and fast algorithms for the polynomial time solvable subproblem of determining satisfiability when there are just two literals per clause. Pretolani uses improed heuristics, branching, and relaxations based on a hypergraph interpretation of the satisfiability problem.
A number of researchers were concerned with local search techniques for finding solutions. Selman, Kautz, and Cohen look at a mixed random walk technique for escaping from local minima. Resende and Feo develop a "Greedy Randomized Adaptive Search Procedure (GRASP)" to construct starting solutions. Hampson and Kibler address the problem of how to determine when it would be best to create a new starting solution rather than continue to local search. Spears uses simulated annealing for avoiding local minima.
Asahiro, lwama, and Miyano suggest a new type of random instance generator with know solutions. This generator has a known number of satisfying assignments.
There are two papers on the maimum satisfiability problem. Cheriyan, Cunningham, Tuncel, and Wang look at problems with at most two literals per clause and determine aspects of its polyhedral structure. They also explore a rounding procedure to get a heuristic solution. Wallace and Freuder use a constraint satisfaction procedure and compare their method with a David-Putnam procedure.
3.4. Combination. Techniques such as tabu search and genetic algorithms are applicable to all three of the Challenge problems. Fleurent and Ferland explore the possibility of creating a general purpose system that can solve all three Challenge problems.
4. Who Won?
The Second DIMACS Challenge was meant as a challenge, not a competition or race. For hard combinatorial optimization problems even a definition of a "winner" is difficult. How should heuristic and exact methods be compared? How should heuristics with differing time requirements and solution qualities be compared? Should an exact method that works quickly on small instances be preferred to one that works slowly on small instances by quicker on larger ones? How should parallel implementations be compared to serial ones? Many algorithms are sensitive to instance structure: how should this be corrected for? F'urthermore, the primary impetus behind many papers in the Challenge is to explicate some broader idea, and the speed of the particular implementation is almost irrelevant.
The choice of approach depends very much on the particulars of the situation. How much time is available? How critical is the solution quality? How robust must the algorithm be?
It is for these reasons that we have decided to present the raw data with very little editorial comment from us: each reader is ivited to come to his or her own conclusion.
In order to proivde some standardization among the papers, a number of instances for each Challenge problem were chosen. All participants were asked to solve these problems and report their results in a standard report. Participants were also given a standard graph coloring program and asked to compile the program, solve a small number of instances, and report the resulting times. In this way, the machines and compilers used by different groups can be compared. Details of the instances are given in the appendix to this olume.
5. Electronically Available Materials
During the Challenge, all of the Challenge material was available by anonymous ftp from DIMACS. Coinciding with the publication of the volume, a World Wide Web site for this Challenge has been created, reachable from http://dimacs.rutgers.edu/archive/Challenges/index.html
This site contains a wealth of material on the Challenge and its problems. Some of the materials include:
Challenge Documentation. These include all the documentation of the Challenge, an archive of the electronic mail messages, the schedule of the Workshop and other material.
Sample Codes. A number of Challenge participants have proided sample computer programs for algorithms for the Challenge problems. These provide a useful benchmark for continuing research. For instance, the programs dfmax and dmclique are exact and heuristic methods respectiely for solving clique problems.
Problem Instances. Perhaps the most useful continuing aspect of the Challenge is the continuing collection of instances of the Challenge problems. At this writing, we have more than 70 clique instances, 40 coloring instances, and 200 satisfiability istances. These are all in a standard format. Tools for converting instances from one format to another are also included.
Continuing Efforts. While the publication of this volume represents the formal finish of the Challenge, some aspects will continue. The repository for instances will remain and expand. Further analysis of the Challenge results will be available.
6. Acknowledgments
A DIMACS Challenge is a large undertaking that requires the efforts of a number of people. We would like to acknowledge the efforts all who help make the Challenge a success. The Challenge Steering committee consisted of Vasek Chvatal, Rutgers University, William Cook, Bell Communications Research, David Johnson, AT&T Bell Laboratories, Cathy McGeoch, Amherst College, Bob Tarjan, Princeton University, and Michael Trick, DIMACS Visiting Fellow/Carnegie Mellon University, who was the Challenge Coordinator. The committee was responsible for not only setting the agenda for the Challenge, but also was the selection committee for the Workshop and helped in many other ways. Cathy McGeoch was also instrumental in the selection and review of papers for this volume. The staff at DIMACS were wonderful in making the Challenge go smoothly. In particular, Jennifer Katinsky handled much of the computer set up and put out many fires for us. Pat Toci and Ida Castellano made certain that the Workshop went smoothly and were a great help throughout the Challenge. Last, and certainly not least, it is the participants that make a Challenge a success and we would like to thank them for their enthusiasm and interest in the Second DIMACS Challenge.
The second editor would like to acknowledge the generous support of DIMACS, the Graduate School of Industrial Administration at Carnegie Mellon University, and the Office of Naval Research. (Grant N0014-92-J-1387).
REFERENCES
1. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szedgedy. Proof verification and hardness of approximation problems. In Proceedings 33rd IEEE Symposium on the Foundations of Computer Science, Pages 14-23, Los Angeles, CA, 1992. IEEE Computer Society.
2. S. Arora, and S. Safra. Probablilistic checking of proofs; a new characterization of np. In Proceedings 33rd IEEE Symposium on Foundations of Computer Science, pages 2-13, Los Angeles, CA, 1992. IEEE Computer Society.
3. M. Bellare, O. Goldreich, and M Sudan. Free bits, PCP and non-approximability- Towards tight results. In Proceedings 36th IEEE Symposium on Foundations of Computer Science, pages 422-431, Los Alamitos, CA, 1995. IEEE Computer Society.
4. P. Briggs, K. Cooper, K. KEnnedy, and L. Torczon. Coloring heuistics for register allocation. In ASCM Conference on Program Language Design and Implementation, pages 275-284, 1989.
5. G.J. Chaitin. Register allocaton and spilling via graph coloring. In Proceedings of hte ACM SIGPLAN 82 Symplsium on Compiler Construction, pages 98-105, New York, NY, 1982. ACM.
6. G.J. Chaitin, M. Auslander, A.K. Chandra, J. Cocke, M.E. Hopkins, and P . Markstein. Register allocation via coloring. Coputer Languages, 6:47-57, 1981.
7. Fred C. Chow and John L. Hennessy. Register allocation by priority-based coloring. In Proceedings of the ACM SIGPLAN 84 Symposium on Compiler Constructin, pages 222-232, New York, NY, 1984. ACM.
8. Fred C. Chow and John L. Hennessy. The priority-based coloring approach to register allocation. ACM Tranasactions on Programming Languages and Systems, 12(4): 501-536, 1990.
9. D, De Werra. An introductino to timetabling. European Jouranl of Oprations Research, 19:151-162, 1985.
10. U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M.Szegedy. Approximating clique is almost NP-complete. In Proceedings 32nd IEEE Symposium on Foundations of Computer Science, pages 2-12, Los Angeles, CA, 1991. IEEE Computer Society.
11. Andreas Gamst. Some lower bounds or a class of frequency assignment problems. IEEE Transactions of Vehicular Echnology, 35(1):8-14, 1986.
12. M.R. Garey, D,S, Johnson, and H.C., So. An application of graph coloring to printed circuit testing. IEEE Trans. On Circuits and Systems, CAS-23:591-599, 1976.
13. Michael R. Garey and David S. Johnson. Computer and Instractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, SanFrancisco, CA, 1979.
14. David S. Johnson and Cathrine C. McGeoch. Network Flows and Matching: First DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 12, American Mathematical Society, 1993.
15. F.T. Leighton. A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, 84:489-506, 1979.
16. C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proceedings 25th ACM Symposium on Theory of Computing, New York, NY, 1993. ACM.
17. Hideo Ogawa. Labeled point pattern matching by delaunay trangulation and maximal cliques. Pattern Recognition, 19(1):35-40, 1986.
18. R.J. Opsut and Fred S. Roberts On the fleet maintenance, movile radio frequency, task assignment and traffic phasing problems, In G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak-Foster, and D.R. Lick, editors, The Theory and Applications of Graphs, pages 479-492, New York, NY, 1981. John Wiley & Sons.
19. G. Yu, O. Goldschmidt, and H. Chen. Clique, independent set and vertex cover in geometric graphs. ORSA/TIMS Presentation, San Francesco, CA, 1992.
20. G. Yu, P. Kouvelis, and Luo. A weighted vertex packing problem for specially structured geometric graphs arising in the design of electronic testing fixtures. ORSA/TIMS Presentation, San Francisco, CA, 1992.
AT&T BELL LABORATORIES, MURRAY HILL, NJ 07974
E-mail address: dsj@research.att.com
GRADUATE SCHOOL OF INDUSTIRAL ADMINISTRATION, CARNEGIE MELLON UNIVERSITY,
PITTSBURGH, PA 15213
E-mail address: trick@cmu.edu
Foreword xi
Introduction to the Second DIMACS Challenge: Cliques, coloring, and
satisfiability
DAVID S. JOHNSON AND MICHAEL A. TRICK 1
Clique
Polyhedral methods for the maximum clique problem
EGON BALAS, SABASTIAN CERIA, GERARD CORNUEJOLS, AND
GABOR PATAKI 11
Finding large cliques in arbitrary graphs by bipartite matching
EGON BALAS AND WILLIAM NIEHAUS 29
An exact quadratic 0-1 algorithm for the stable set problem
JEAN-MARIE BOURJOLLY, PAUL GILL, GILBERT LAPORTE, AND
HELENE MERCURE 53
Camouflaging independent sets in quasi-random graphs
MARK BROCKINGTON AND JOSEPH C. CULBERSON 75
Constructing cliques using restricted backtracking
MARK K. GOLDBERG AND REID D. RIVENBURGH 89
A continuous based hueristic for the maximum clique problem
L. E. GIBBONS, D. W. HEARN, AND P. M. PARDALOS 103
Applying the INN model to the Maximum Clique problem
TAL GROSSMAN 125
Experiments with polynomial-time CLIQUE approximation algorithms
on very large graphs
STEVEN HOMER AND MARCUS PEINADO 147
Approximately solving Maximum Clique using neural network and
related heuristics
ARUN JAGOTA, LAURA SANCHIS, AND RAVIKANTH GANESAN 169
Edge projection and the maximum cardinality stable set problem
CARLO MANNINO AND ANTONIO SASSANO 205
Tabu search algorithms for the maximum clique problem
PATRICK SORIANO AND MICHEL GENDREAU 221
Coloring
Exploring the k-coloable landscape with Iterated Greedy
JOSEPH C. CULBERSON AND FENG LUO 245
Coloring by tabu branch and bound
FRED GLOVER, MARK PARKER, AND JENNIFER RYAN 285
Experiments with parallel graph coloring heuristics and
applications of graph coloring
GARY LEWANDOWSKI AND ANNE CONDON 309
Distributed coloration neighborhood search
CRAIG MORGENSTERN 335
A. improved algorithm for exact graph coloring
E. C. SEWELL 359
Satisfiability
Random generation of test instances ith controlled attributes
YUICHI ASAHIRO, KAZUO IWAMA, AND EIJI MIYANO 377
A linear programming and rounding approach to max 2-sat
J. CHERIYAN, W. H. CUNNINGHAM, L. TUNCEL, AND Y. WANG 395
SAT versus UNSAT
0. DUBOIS, P. ANDRE, Y. BOUFKHAD. AND J. CARLIER 415
Large plateaus and plateau search in Boolean Satisfiability
problems: When to give up searching and start again
STEVEN HAMPSON AND DENNIS KIBLER 437
Tabu search and a quadratic relaxation for the Satisfiability
problem
BRIGITTE JAUMARD, MIHNEA STAN, AND JACQUES DESROSIERS 457
Efficiency, and stability of hypergraph SAT algorithms
DANIELE PRETOLANI 479
A GRASP for satisfiability
MAURICIO G. C. RESENDE AND THOMAS A. FEO 499
Local search strategies for satisfiabilitv testing
BART SELMAN, HENRY KAUTZ, AND BRAM COHEN 521
Simulated annealing for hard satisfiability problems
WILLIAM M. SPEARS 533
Satisfiability testing with more reasoning and less guessing
ALLEN VAN GELDER AND YUMI K. TSUJI 559
Comparative studies of constraint satisfaction and Davis-Putnam,
algorithms for maximum satisfiabilitv problems
RICHARD J. WALLACE AND EUGENE C. FREUDER 587
Combination
Object-oriented implementation of heuristic search methods for
Graph Coloring, Maximum Clique, and Satisfiability
CHARLES FLEURENT AND JACQUES A. FERLAND 619
Appendix: Second DIMACS Challenge test problems
MICHAEL A. TRICK 653
Index of Volumes
DIMACS Homepage