Conversion of coloring algorithms into maximum weight independent set algorithms

摘要

A general technique for converting approximation algorithms for the vertex coloring problem in a class of graphs into approximation algorithms for the maximum weight independent set problem (MWIS) in the same class of graphs is presented. The technique consists of solving an LP-relaxation of the MWIS problem with certain clique inequalities, constructing an instance of the vertex coloring problem from the LP solution, applying the coloring algorithm to this instance, and selecting the best resulting color class as the MWIS solution. The approximation ratio obtained is the product of the approximation ratio with which the LP formulation can be solved (usually equal to one) and the approximation ratio of the coloring algorithm with respect to the size of the largest relevant clique. Applying this technique, the best known approximation algorithms are obtained for the maximum Weight edge-disjoint paths problem in bidirected trees and in bidirected two-dimensional meshes with row-column routing, and for time-constrained scheduling of weighted packets in the same topologies. These problems are also proved to be MAX SNP-hard. (c) 2005 Elsevier B.V. All rights reserved.