Average-case complexity of a branch-and-bound algorithm for max independent set under the G(n,p) random model

Thumbnail
View/Open
Date
2015
Collection title
Cahier de recherche CEREMADE
Dewey
Probabilités et mathématiques appliquées
Sujet
Computational Complexity
URI
https://basepub.dauphine.fr/handle/123456789/17931
Collections
Metadata
Show full item record
Author
Bourgeois, Nicolas
92163 Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) [SAMM]
Catellier, Rémi
75 Institut de Recherche Mathématique de Rennes [IRMAR]
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Denat, Tom
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Document de travail / Working paper
Abstract (EN)
We study average-case complexity of branch-and-bound for maximum independent set in random graphs under the $\mathcal{G}(n,p)$ distribution. In this model every pair $(u,v)$ of vertices belongs to $E$ with probability $p$ independently on the existence of any other edge. We make a precise case analysis, providing phase transitions between subexponential and exponential complexities depending on the probability $p$ of the random model.