Maximum-weight independent set is as "well-approximated" as the unweighted one

Marc Demange, CERMSEM
Vangelis Th. Paschos*, LAMSADE

Résumé. Nous présentons une réduction d'expansion O(log n) (où n est l'ordre du graphe) préservant le rapport d'approximation entre les versions pondérée et non pondérée d'une classe de problèmes de maximisation consistant à trouver un sous-graphe induit de poids maximum vérifiant une propriété héréditaire. Nous en déduisons une première amélioration du meilleur rapport connu pour le problème du stable maximum pondéré. Cette réduction nous permet aussi de concevoir, pour tout k, un algorithme approché polynomial de rapport O(min[log^kn/n) ; log m/(k² m(log log m)²]) où m désigne le degré moyen du graphe. Dans cette expression, le membre fonction de n dépasse le meilleur rapport connu pour le cas non pondéré IS (O(log² n/n)) tandis que le second membre est de la forme W(1/D) pour WIS (où D est le degré maximum du graphe) sachant que le meilleur rapport connu en fonction de D valait jusqu'ici 3/(D+2). A partir du problème de coloration, nous proposons alors un algorithme approché polynomial pour WIS ayant pour rapport O(min[n^-4/5 ; log log D/D]). Précisons qu'approcher le problème de stable (pondéré ou non) par un rapport W(1/D est un problème ouvert important et que, pour tout e appartenant à ]0,1[, ces deux problèmes sont également connus pour être non-approximables à rapport n^e-1. Enfin, nous proposons les premiers rapports non triviaux en W(1/D) pour les problèmes de la clique maximum pondérée et non pondérée, du sous-graphe induit l-colorable de poids maximum et de la somme chromatique.
Mots clés : Problèmes combinatoires, complexité algorithmique, algorithmes approchées polynomiaux, problème héréditaire, stable, clique, sous-graphe induit l-colorable, somme chromatique.

Abstract. We devise an approximation-preserving reduction of expansion O(log n) (where n is the order of the input-graph) between weighted and unweighted versions of a class of problems called weighted hereditary induced-subgraph maximization problems. This allows us to perform a first improvement of the best approximation ratio for the weighted independent set problem (WIS). Then, using this reduction, we propose, for every k, a polynomial time approximation algorithm for WIS achieving a ratio O(min[log^kn/n) ; log m/(k² m(log log m)²]) where m denotes the average graph-degree of the input-graph. In any of the two cases, this is an important improvement since in the former one, the ratio for WIS outerperforms O(log² n/n), the best-known ratio for (unveighted) independent set problem (IS), while in the latter case, we obtain W(1/D) ratio for WIS (where D is the maximum graph-degree) given that, until now, the best-known ratio in terms of D was 3/(D+2). Next, based upon graph-coloring, we devise a polynomial time approximation algorithm for WIS achieving ratio O(min[n^-4/5 ; log log D/D]). Let us note that approximation of both independent set versions within ratios W(1/D is a very well-known open problem and that, for every e, both problems are known to be inapproximable within ratio n^e-1. Finally, we propose the first non-trivial W(1/D) ratios for maximum-size and maximum-weight clique, for maximum-weight l-colorable induced subgraph and for chromatic sum.
Keywords : Combinatorial problems, computational complexity, polynomial-time approximation algorithm, NP-completeness, hereditary problem, independent set, clique, l-colorable induced subgraph, chromatic sum.

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

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