On-line maximum-order induced hereditary subgraph problems

Marc Demange, CERMSEM
Xavier Paradon*, LAMSADE
Vangelis Th. Paschos*, LAMSADE

Résumé. Nous étudions d'abord le rapport de compétitivité de la version on-line du problème consistant à déterminer un sous graphe de taille maximum vérifiant une propriété héréditaire dans le cas où les sommets sont révélés par parquets. Nous nous intéressons alors à deux cas particuliers très importants de ce problème : le problème de stable maximum et celui de clique maximum. Enfin, nous étudions une version pondérée du problème de stable on-line.
Mots clés : Algorithmes on-line, propriété héréditaire, ensemble stable, clique, réduction.

Abstract. We first study the competitivity ratio for the on-line version of the problem of finding a maximum-order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Next, we focus ourselves on two of the most known instantiations of this problem, the maximum independent set and the maximum clique. Finally, we study a variant of the on-line maximum-weight induced hereditary subgraph problem.
Keywords : On-line algorithm, hereditary property, independent set, clique, reduction.

AMS Classification : 03D15, 68Q25, 68R10.

*LAMSADE, Université Paris Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.