Mikhailyuk V.A.
Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions

Using gap-introducing and gap-preserving reductions, it is shown that there is no polynomial-time approximation scheme (PTAS) for the multiple reoptimization of the problem of calculating the chromatic number of a graph with a given exponentially growing set of optimal solutions when inserting an arbitrary vertex with no more than two edges incident to it and also when eliminating an arbitrary vertex together with all the edges incident to it. The same result holds for ordinary reoptimization. © 2016, Springer Science+Business Media New York.

Keywords: APX-hardness, gap-introducing reduction, gap-preserving reduction, multiple reoptimization, polynomial-time approximation scheme (PTAS), Approximation theory, Hardness, Optimal systems, Polynomials, APX-Hardness, Arbitrary vertices, Chromatic number of a graphs, Optimal solutions, Polynomial time approximation schemes, Reoptimization, Polynomial approximation

Cite:
Mikhailyuk V.A. (2016). Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions. Cybernetics and Systems Analysis, 52 (3), 39-48. doi: https://doi.org/10.1007/s10559-016-9837-y http://jnas.nbuv.gov.ua/article/UJRN-0000502502 [In Russian].