Abstract
In 1965 Motzkin and Straus established a remarkable connection between the local/global maximizers of the Lagrangian of a graph G over the standard simplex Δ and the maximal/maximum cliques of G. In this work we generalize the Motzkin-Straus theorem to k-uniform hypergraphs, establishing an isomorphism between local/global minimizers of a particular function over Δ and the maximal/maximum cliques of a k-uniform hypergraph. This theoretical result opens the door to a wide range of further both practical and theoretical applications, concerning continuous-based heuristics for the maximum clique problem on hypergraphs, as well as the discover of new bounds on the clique number of hypergraphs. Moreover we show how the continuous optimization task related to our theorem, can be easily locally solved by mean of a dynamical system.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baum, L.E., Eagon, J.A.: An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc. 73, 360–363 (1967)
Baum, L.E., Petrie, T., Soules, G., Weiss, N.: A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Statist. 41, 164–171 (1970)
Baum, L.E., Sell, G.R.: Growth transformations for functions on manifolds. Pacific J. Math. 27, 211–227 (1968)
Berge, C.: Hypergraphs. Combinatorics of Finite Sets. Ed. North-Holland, Amsterdam (1989)
Blakley, G.R.: Homogeneous nonnegative symmetric quadratic transformations. Bull. Amer. Math. Soc. 70, 712–715 (1964)
Bomze, I.M., Pelillo, M., Giacomini, R.: Evolutionary approach to the maximum clique problem: empirical evidence on a larger scale. Developments in Global Optimization, 95–108 (1997)
Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization (Supplement Volume A), pp. 1–74 (1999)
Bomze, I.M., Budinich, M., Pelillo, M., Rossi, C.: Annealed replication: a new heuristic for the maximum clique problem. Discr. Appl. Math. 121(1-3), 27–49 (2002)
Budinich, M.: Exact bounds on the order of the maximum clique of a graph. Discr. Appl. Math. 127, 535–543 (2003)
Bunke, H., Dickinson, P.J., Kraetzl, M.: Theoretical and Algorithmic Framework for Hypergraph Matching. In: ICIAP, pp. 463–470 (2005)
Faugeras, O.D., Berthod, M.: Improving consistency and reducing ambiguity in stochastic labeling: an optimization approach. IEEE Trans. Pattern Anal. Machine Intell. 3, 412–424 (1981)
Frankl, P., Rödl, V.: Hypergraphs do not jump. J. Combinatorica 4, 149–159 (1984)
Gibbons, L.E., Hearn, D.W., Pardalos, P.M.: A continuous based heuristic for the maximum clique problem. In: Cliques, Coloring and Satisfiability: 2nd DIMACS Impl. Chall., vol. 26, pp. 103–124 (1996)
Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22, 754–768 (1997)
Khot, S.: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In: Proc. of 42nd Ann. IEEE Symp. on Found. of Comp. Sc., pp. 600–609 (2001)
Mohammed, J.L., Hummel, R.A., Zucker, S.W.: A gradient projection algorithm for relaxation labeling methods. IEEE Trans. Pattern Anal. Machine Intell. 5, 330–332 (1983)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math. 17, 533–540 (1965)
Mubay, D.: A hypergraph extension of Turán’s theorem. J. Combin. Theory B 96, 122–134 (2006)
Papa, D.A., Markov, I.: Hypergraph Partitioning and Clustering. In: Approximation Algorithms and Metaheuristics, pp. 61.1– 61.19 (2007)
Pardalos, P.M.: Continuous approaches to discrete optimization problems. In: Nonlinear Optimization and Applications, pp. 313–328 (1996)
Pardalos, P.M., Phillips, A.T.: A global optimization approach for solving the maximum clique problem. Int. J. Comput. Math. 33, 209–216 (1990)
Pavan, M., Pelillo, M.: Generalizing the Motzkin-Straus theorem to edge-weighted graphs, with applications to image segmentation. In: Rangarajan, A., Figueiredo, M.A.T., Zerubia, J. (eds.) EMMCVPR 2003. LNCS, vol. 2683, pp. 485–500. Springer, Heidelberg (2003)
Pelillo, M.: Relaxation labeling networks for the maximum clique problem. J. Artif. Neural Networks 2, 313–328 (1995)
Pelillo, M., Jagota, A.: Feasible and infeasible maxima in a quadratic program for maximum clique. J. Artif. Neural Networks 2, 411–420 (1995)
Rota Bulò, S., Pelillo, M.: A Continuous Characterization of Maximal Cliques in k-uniform Hypergraphs Tech. Report CS-2007-4, “Ca’ Foscari” University of Venice (2007)
Sos, V.T., Straus, E.G.: Extremal of functions on graphs with applications to graphs and hypergraphs. J. Combin. Theory B 63, 189–207 (1982)
Turán, P.: On an extremal problem in graph theory (in Hungarian). Mat. ès Fiz. Lapok 48, 436–452 (1941)
Wilf, H.S.: The eigenvalues of a graph and its chromatic number. J. London Math. Soc. 42, 330–332 (1967)
Wilf, H.S.: Spectral bounds for the clique and independence numbers of graphs. J. Combin. Theory Ser. B 40, 113–117 (1986)
Zhou, D., Huang, J., Schölkopf, B.: Learning with hypergraphs: clustering, classification, embedding. Neural Inform. Proc. Systems 19 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rota Bulò, S., Pelillo, M. (2008). A Continuous Characterization of Maximal Cliques in k-Uniform Hypergraphs. In: Maniezzo, V., Battiti, R., Watson, JP. (eds) Learning and Intelligent Optimization. LION 2007. Lecture Notes in Computer Science, vol 5313. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92695-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-92695-5_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92694-8
Online ISBN: 978-3-540-92695-5
eBook Packages: Computer ScienceComputer Science (R0)