Computational complexity of the graph approximation problem
Alexander A. Ageev, Victor P. Il’ev, Alexander V. Kononov, А. С. Талевнин · Journal of Applied and Industrial Mathematics · 2007
The computational complexity of the graph approximation problem is investigated. It is shown that the different variants of this problem are NP-hard both for undirected and directed graphs. A polynomial-time approximation scheme (PTAS) for one of the variants is presented.