Предположим, что для одной из двух задач в каждой из следующих пар существует альфа-приближенный алгоритм за время O(n2):
Гарантирует ли это, что для другой задачи в паре существует альфа-приближенный алгоритм за время O(n2)? Я знаю, что Clique сводится к Independent Set, который, в свою очередь, сводится к Vertex Cover.
Не обязательно по двум причинам.
Прежде всего, NP-редукции обычно не являются линейными по сложности. Некоторые из них да, но обычно проблема сложности n сводится к какой-то другой проблеме NP размера n^3 или что-то в этом роде. Даже если бы мы нашли алгоритм 3SAT с линейным временем, мы бы не нашли алгоритмы с линейным временем для всех NP-сложных задач — только полиномиальные алгоритмы. Так что если под «похожим» вы подразумеваете «тоже n^2», то не в общем.
Во-вторых, приближения вообще не передаются. Из-за нелинейного роста сложности (это упрощение, почему, но это сойдет), гарантии аппроксимации обычно не выдерживают процесса редукции. В результате, хотя все NP-полные задачи являются в некотором смысле товарищами по сложности точного решения, они далеки от нее по сложности аппроксимации.
В некоторых конкретных случаях приближения делают перенос (и один из ваших примеров — оставленный в качестве упражнения для читателя — определенно переносится). Но это никак не гарантировано.
