Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера

В работе рассматриваются новые варианты задачи аппроксимации графа, в которых имеются ограничения на размер компонент связности аппроксимирующих графов. Доказано, что если мощность каждой компоненты аппроксимирующего графа не больше заданного целого числа $p\geq3$, то задача аппроксимации графа является $NP$-трудной, а в случае $p=2$ она полиномиально разрешима.