О смежности вершин многогранника связных k-факторов

Комбинаторные характеристики многогранников, ассоциированных с комбинаторными задачами оптимизации, в определенной степени могут считаться характеристиками их труднорешаемости. Например, $NP$-полнота проверки несмежности вершин многогранника задачи очень часто сопутствует $NP$-трудности самой задачи. Еще одной важной характеристикой графа многогранника задачи является кликовое число. В некотором довольно широком классе алгоритмов кликовое число является нижней оценкой временной трудоемкости задачи. Кроме того, для большого количества труднорешаемых задач известны экспоненциальные нижние оценки кликового числа графов многогранников, в то время как для полиномиально разрешимых задач для него установлены полиномиальные нижние и верхние оценки. В данной работе рассматривается многогранник задачи о взвешенном связном остовном $k$-однородном подграфе (связном $k$-факторе) полного $n$-вершинного графа, который при $k=2$ является многогранником симметричной задачи коммивояжера. Показано, что при $k$, удовлетворяющих условиям $k\geq 3$ и ${\displaystyle{\Big\lceil \frac{k}{2} \Big\rceil \leq \frac{n}{8} - 1}}$, проверка несмежности вершин этого многогранника является $NP$-полной задачей и кликовое число экспоненциально по $n$. Доказательства основаны на сведении к случаю $k=2$.