УДК 519.85
MSC: 90XXX
DOI: 10.21538/0134-4889-2018-24-2-235-242
Полная версия статьи
Работа выполнена при поддержке РФФИ (проект 18-07-00599).
Комбинаторные характеристики многогранников, ассоциированных с комбинаторными задачами оптимизации, в определенной степени могут считаться характеристиками их труднорешаемости. Например, $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$.
Ключевые слова: $k$-фактор, многогранник, смежность вершин многогранника, кликовое число графа.
СПИСОК ЛИТЕРАТУРЫ
1. Padberg M. W., Rinaldi G. A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems // SIAM Review. 1991. Vol. 33, no. 1. P. 60–100. doi: 10.1137/1033004 .
2. Grotschel M., Holland O. Solution of large-scale symmetric traveling salesman problems // Math. Progr. 1991. Vol. 51, no. 1–3. P. 141–202. doi: 10.1007/BF01586932 .
3. Crowder H., Johnson E. L., Padberg M. W. Solving large-scale zero-one linear programming problems // Operations Research. 1983. Vol. 31, no. 5. P. 803–834. doi: 10.1287/opre.31.5.803 .
4. Simanchev R. Yu., Urazova I. V. Cutting planes algorithm for the connected k-factor problem using the facet inequalities [e-resource] // Proc. OPTIMA-2017 Conf. (Petrovac, Montenegro, October 2–7). 2017. P. 517–523. URL: http://ceur-ws.org/Vol-1987/paper74.pdf .
5. Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem // Math. Progr. 1989. Vol. 45, no. 1–3. P. 59–96. doi: 10.1007/BF01589097 .
6. Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.
7. Papadimitriou C. H. The adjacency relation on the traveling salesman polytope is NP-complete // Math. Progr. 1978. Vol. 14, no. 1. P. 312–324. doi: 10.1007/BF01588973 .
8. Бондаренко В. А. Неполиномиальная нижняя оценка сложности задачи коммивояжера в одном классе алгоритмов // Автоматика и телемеханика. 1983. № 9. C. 45–50.
9. Edmonds J. Maximum matching and a polyhedron with 0,1-vertices // J. Research National Bureau Standards. Sec. B. 1965. Vol. 69. P. 125–130.
10. Reductions to 1-matching polyhedra / J. Araoz, W. H. Cunningham, J. Edmonds, J. Green-Krotki // Networks. 1983. Vol. 13. P. 455–473. doi: 10.1002/net.3230130403 .
11. Gerards A. M. H. Matching // Handbooks in Operations Research and Management Science / eds. M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhause. Amsterdam: Elsevier, 1995. Vol. 7. P. 135–224. doi: 10.1016/S0927-0507(05)80120-3 .
12. Лекции по теории графов / В. А. Емеличев и др. М.: Наука, 1990. 384 с.
13. Maksimenko A. N. The common face of some 0/1-polytopes with NP-complete nonadjacency relation // J. Math. Sci. 2014. Vol. 203, iss. 6. P. 823–832. doi: 10.1007/s10958-014-2172-9 .
Поступила 05.02.2018
Симанчев Руслан Юрьевич
канд. физ.-мат. наук, доцент
зав. каф. ПОЗИ
Омский государственный университет им. Ф.М. Достоевского;
науч. сотрудник
Омский научный центр СО РАН,
г. Омск
e-mail: osiman@rambler.ru
English
R.Yu. Simanchev. On the vertex adjacency in a polytope of connected k-factors.
Combinatorial characteristics of polytopes associated with combinatorial optimization problems can be considered to some extent as the intractability characteristics of these problems. For example, the $NP$-completeness of verifying the nonadjacency of vertices in the polytope of a problem quite often accompanies the $NP$-hardness of the problem. Another important characteristic of the polytope graph of a problem is its clique number. For a rather wide class of algorithms, the clique number is a lower bound for the time complexity of the problem. In addition, for the clique number of polytope graphs, there are known exponential lower bounds for a large number of intractable problems and known polynomial upper and lower bounds for problems solvable in polynomial time. In the present paper we consider the polytope of the problem on a weighted connected spanning $k$-regular subgraph (a connected $k$-factor) of a complete $n$-vertex graph; for $k=2$, this is the polytope of the symmetric traveling salesman problem. For the values of $k$ satisfying the conditions $k\geq 3$ and $\lceil k/2 \rceil \leq n/8 - 1$, we show that the problem of verifying the nonadjacency of vertices of this polytope is $NP$-complete and the clique number is exponential in $n$. The proofs are based on the reduction to the case $k=2$.
Keywords: $k$-factor, polytope, adjacency of vertices, clique number of a graph.
The paper was received by the Editorial Office on February 5, 2018.
Funding Agency:
Russian Foundation for Basic Research (Grant Number 18-07-00599).
Ruslan Yur’evich Simanchev, Cand. Sci. (Phys.-Math.), Omsk State University, Omsk, 644077 Russia; Omsk Scientific Center SB RAS, Omsk, 644040 Russia; Omsk State University, Omsk, 644077 Russia, e-mail: osiman@rambler.ru.
[References on the English button bottom right]
