ON THE COMPLEXITY OF APPROXIMATING COLORED-GRAPH PROBLEMS

In this paper we prove explicit lower bounds on the approximability of some graph problems restricted to instances which are already colored with a constant number of colors. As far as we know, this is the first time these problems are explicitily defined and analyzed. This allows us to drastically improve the previously known inapproximability results which were mainly a consequence of the analysis of bounded-degree graph problems. Moreover, we apply one of these results to obtain new lower bounds on the approximabiluty of the minimum delay schedule problem on store-and-forward networks of bounded diameter. Finally, we propose a generalization of our analysis of the complexity of approximating colored-graph problems to the complexity of approximating approximated optimization problems.