Towards a general formal framework for polynomial approximation (concepts and examples)

Marc Demange, CERMSEM
Vangelis Th. Paschos*, LAMSADE

Résumé. Nous commençons par généraliser le cadre formel de l'approximation polynomiale afin d'envisager de nouveaux types de résultats. Dans un second temps, nous exploitons ce cadre pour établir des résultats d'approximation pour plusieurs problèmes combinatoires NP-difficiles. Nous nous intéressons d'abord à la classe des problèmes de maximisation d'un sous graphe induit vérifiant une propriété héréditaire et de leurs versions pondérées. Des exemples notoires de tels problèmes sont le stable maximum, la clique maximum, le sous-graphe induit l-colorable maximum, etc. Nous proposons des réductions en approximation qui permettent d'établir des améliorations significatives pour l'approximation de problèmes de cette classe, notamment pour le problème de stable de valeur maximum. Nous proposons également le premier résultat d'approximation non trivial fonction du degré du graphe pour le problème de clique de valeur maximum. Nous quittons alors cette classe de problèmes pour nous intéresser aux problèmes de somme chromatique minimum et de coloration minimum. Pour le premier, nous proposons une réduction permettant de transférer les résultats sur le stable de valeur maximum à une version pondérée des sommes chromatiques. Enfin, pour le problème de coloration minimum, nous proposons des résultats d'approximation qui améliorent les résultats connus.
Mots clés : Classes de complexité, cha”nes d'approximation polynomiale, niveau d'approximation, réductions en approximation, stable, coloration de graphes.

Abstract. In a first time we draw a rough shape of a general formal framework for polynomial approximation theory which encompasses the existing one by allowing the expression of new types of results. We show how this framework incorporates all the existing approximation results and, moreover, how new types of results can be expressed within it. Next, we use the framework introduced to obatin approximation results for a number of NP-hard problems. In this second part of the paper, we first deal with a class of problems called weighted hereditary induced-subgraph maximization problems, notable representatives of which are maximum independent set, maximum clique, maximum l-colorable induced subgraph, etc. We devise approximation preserving reductions allowing to perform subsequent improvements of the approximation ratios for problems of this class, in particular for the weighted independent set problem (max_WIS). We also devise the first non-trivial approximation results with respect to the maximum degree of the instance graph for the weighted maximum clique problem. We then leave the class of hereditary induced-subgraph maximization problems and deal with the minimum chromatic sum and the minimum coloring. For the former, we devise a reduction which allows to transfer of the results obtained for max_WIS to minimum weight chromatic sum. Finally, for minimum coloring, we produce approximation ratios improving all the known ones.
Keywords : Complexity classes, polynomial approximation chain, approximation level, approximation preserving reduction, independent set, graph coloring.

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

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