Abstract
The linear programming relaxation of the minimum vertex coloring problem, called the fractional coloring problem, is NP-hard. We describe efficient approximation procedures for both the weighted and unweighted versions of the problem. These fractional coloring procedures are then used for generating upper bounds for the (weighted or unweighted) maximum clique problem in the framework of a branch-and-bound procedure. Extensive computational testing shows that replacing the standard upper bounding procedures based on various integer coloring heuristics with the somewhat more expensive fractional coloring procedure results in improvements of the bound by up to one-fourth in the unweighted and up to one-fifth in the weighted case, accompanied by a decrease in the size of the search tree by a factor of almost two.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
L. Babel, Finding maximum cliques in arbitrary and special graphs,Computing, 46:321–341, 1991.
L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem,ZOR-Methods and Models of Operations Research, 34:207–217, 1990.
E. Balas, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring,Discrete Applied Mathematics, 15:123–134, 1986.
E. Balas and J. Xue, Fast Maximum Clique Algorithms, TB 17.4, TIMS/ORSA, Las Vegas, May 7–9, 1990.
E. Balas and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs,SIAM Journal of Computing, 20:209–221, 1991. Addendum,SIAM Journal on Computing, 21:1000, 1992.
E. Balas and C. S. Yu, Finding a maximum clique in an arbitrary graph,SIAM Journal on Computing, 14:1054–1068, 1986.
B. Bollobás,Random Graphs, Academic Press, New York, 1985.
D. Brelaz, New methods to color the vertices of a graph,Communications of the ACM, 22:251–256, 1979.
R. Carraghan and P. M. Pardalos, A Parallel Algorithm for the Maximum Weight Clique Problem, Technical Report CS-90-40, Department of Computer Science, Pennsylvania State University, 1990.
F. D. J. Dunstan, Sequential Colorings of Graphs,Proceedings of the 5th British Combinatorial Conference, Vol. 19, 1975, pp. 456–463.
M. Grötschel, L. Lovász, and A. Schrijver, Polynomial algorithms for perfect graphs,Annals of Discrete Mathematics, 21:325–356, 1989.
F. T. Leighton, A graph coloring algorithm for large scheduling problems,Journal of Research of the National Bureau of Standards, 84:489–506, 1979.
C. Mannino and A. Sassano, An Exact Algorithm for the Stable Set Problem, IASI-CNR Report No. 334, Rome, 1992.
D. W. Matula, G. Marble, and J. D. Isaacson, Graph coloring algorithms, in R. C. Read (ed.),Graph Theory and Computing, Academic Press, London, 1972, pp. 109–122.
D. J. A. Welsh and M. B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems,The Computer Journal, 10:85–86, 1967.
J. Xue, Fractional Coloring Heuristic with Application to the Maximum Clique Problem, ARIDAM V, Abstracts, RUTCOR Report No.2-90, May–June 1990, p. 67.
J. Xue, Fast algorithms for vertex packing and related problems, Ph.D. thesis, GSIA, Carnegie Mellon University, Pittsburgh, PA, 1991.
J. Xue, Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem,Networks, to appear.
Author information
Authors and Affiliations
Additional information
Communicated by N. Megiddo.
This research was supported by the National Science Foundation under Grant No. DDM-9201340 and the Office of Naval Research through Contract N00014-85-K-0198.
Rights and permissions
About this article
Cite this article
Balas, E., Xue, J. Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring. Algorithmica 15, 397–412 (1996). https://doi.org/10.1007/BF01955041
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01955041