Abstract
The classical problem of finding a clique of largest cardinality in an arbitrary graph is NP-complete. For that reason earlier work diverges into two directions. The first concerns algorithms solving the problem for arbitrary graphs in reasonable (but exponential) time, the other restricts to special classes of graphs where polynomial methods can be found. Here, the two directions are combined in a way. A branch and bound algorithm is developed treating the general case. Computational experiments on random graphs show that this algorithm compares favorable to the fastest known method. Furthermore, it consumes only polynomial time for quite a few graph classes. For some of them no polynomial solution method is given so far.
Zusammenfassung
Das klassische Problem der Ermittlung einer Clique größter Mächtigkeit in einem beliebigen Graph ist NP-vollständig. Deshalb teilen sich bisherige Untersuchungen in zwei Richtungen. Die erste beschäftigt sich mit Algorithmen, die das Problem für beliebige Graphen in vernünftiger (aber exponentieller) Zeit lösen, die andere beschränkt sich auf spezielle Graphenklassen, für die polynomiale Methoden möglich sind. Hier werden diese beiden Richtungen kombiniert. Es wird ein Branch and Bound-Algorithmus für den allgemeinen Fall entwickelt. Praktische Rechenexperimente an Zufallsgraphen zeigen, daß dieser Algorithmus dem schnellsten bisher bekannten Verfahren überlegen ist. Darüberhinaus benötigt er nur polynomiale Rechenzeit für eine Vielzahl von Graphenklassen, darunter einige, für die noch keine polynomiale Lösungsmethode bekannt ist.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Babel, L.: Ein Branch and Bound-Verfahren zur Lösung des Maximum Clique Problems. Dissertation, TU München (1990).
Babel, L., Tinhofer, G.: A branch and bound algorithm for the maximum clique problem. ZOR—Methods and Models of Operations Research34, 207–217 (1990).
Berge, C.: Graphs and hypergraphs, Amsterdam: North Holland (1973).
Brelaz, D.: New methods to color the vertices of a graph. Comm. of the ACM22, 251–256 (1979).
Deo, N.: Graph theory with applications to engineering and computer science. New York: Prentice Hall (1974).
Fulkerson, D. R., Gross, O. A.: Incidence matrices and interval graphs. Pacific J. Math.15, 835–855 (1965).
Garey, M. R., Johnson, D. S.: Computers and intractability. Freeman, N. Y. (1979).
Golumbic, M. C.: Algorithmic graph theory and perfect graphs. New York: Academic Press (1980).
Johnson, D. S.: The NP-completeness column: an ongoing guide. J Algorithms6, 434–451 (1985).
Johnson, D. S.: The NP-completeness column: an ongoing guide. J Algorithms8, 438–448 (1987).
Wald, J. A., Colbourn, C. J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks13, 159–167 (1983).
de Werra, D.: Heuristics for graph colorings. In: Tinhofer, G., (ed.), Computational graph theory. Computing Suppl7, 191–208. Wien New York: Springer (1990).
Augustson, J. G., Minker, J.: An analysis of some graph theoretical cluster techniques. J. of the ACM17, 571–588 (1970).
Balas, E., Samuelsson, H.: A node covering algorithm. Naval Res. Log. Quart.24, 213–233 (1977).
Balas, E., Yu, C. S.: Finding a maximum clique in an arbitrary graph. SIAM J. Computing15, 1054–1068 (1986).
Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph. Comm. of the ACM16, 575–577 (1973).
Friden, C., Hertz, A., de Werra, D.: TABARIS: an exact algorithm based on tabu search for finding a maximum independent set in a graph. Preprint, ORWP 3 (1989).
Gerhards, L., Lindenberg, W.: Clique detection for nondirected graphs: Two new algorithms. Computing21, 295–322 (1979).
Loukakis, E.: A new backtracking algorithm for generating the family of maximal independent sets of a graph. Comp. Math. Appl.9, 583–589 (1983).
Loukakis, E., Tsouros, C.: Determining the number of internal stability of a graph. Intern. J. Comp. Math.11, 207–220 (1982).
Nemhauser, G. L., Trotter, L. E.: Vertex packings: structural properties and algorithms. Math. Programming8, 232–248 (1975).
Tarjan, R. E., Trojanowski, A. E.: Finding a maximum independent set. SIAM J. Computing6, 537–546 (1977).
Corneil, D. G., Perl, Y., Stewart, L. K.: A linear recognition algorithm for cographs. SIAM J. Computing,14, 929–934 (1985).
Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Computing1, 180–187 (1972).
Gavril, F.: Algorithms for a maximum clique and maximum independent set of a circle graph. Networks3, 261–273 (1973).
Gavril, F.: Algorithms on circular-arc-graphs. Networks4, 357–369 (1974).
Golumbic, M. C., Hammer, P. L.: Stability in circular-arc-graphs. J Algorithms9, 314–320 (1988).
Gupta, U., Lee, D., Leung, J.: Efficient algorithms for interval graphs and circular-graphs. Networks12, 459–467 (1982).
Hsu, W.-L., Ikura, Y., Nemhauser, G. L.: A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles. Mathematical Programming20, 225–232 (1981).
Hsu, W.-L., Nemhauser, G. L.: Algorithms for maximum weight cliques, minimum weighted clique covers and minimum colorings of claw-free perfect graphs. Ann Discrete Math.21, 357–369 (1984).
Masuda, S., Nakajima, K.: An optimal algorithm for finding a maximum independent set of a circular-arc-graph. SIAM J. Computing17, 41–52 (1988).
Masuda, S., Nakajima, K., Kashiwabara, T., Fujisawa, T.: Efficient algorithms for finding maximum cliques of an overlap graph. Networks20, 157–171 (1990).
Minty, G. J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory B28, 284–304 (1980).
Papadimitriou, C. H., Yannakakis, M.: The clique problem for planar graphs. Inform. Proc. Letters13, 131–133 (1981).
Rose, D. J., Tarjan, R. E., Lueker, G. S.: Algorithmic aspects of vertex elimination on graphs. SIAM J: Computing5, 266–283 (1976).
Rotem, D., Urrutia, J.: Finding maximum cliques in circle graphs. Networks11, 269–278 (1981).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Babel, L. Finding maximum cliques in arbitrary and in special graphs. Computing 46, 321–341 (1991). https://doi.org/10.1007/BF02257777
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02257777