Гамільтонове доповнення

Задача гамільтонового доповнення — це задача знаходження найменшого числа ребер, які потрібно додати в граф, щоб він став гамільтоновим.

Ясно, що задача в загальному випадку NP-складна (оскільки її розв'язок дає відповідь на NP-повну задачу визначення, чи має граф гамільтонів цикл). Пов'язана задача розв'язності, чи може додавання K ребер в заданий граф дати гамільтонів граф, є NP-повною.

Понад це, Ву, Лу і Лі показали, що існування ефективних алгоритмів зі сталим коефіцієнтом апроксимації для цієї задачі малоймовірне.

Задачу можна розв'язати за поліноміальний час для деяких класів графів, серед яких паралельно-послідовні графи і їх узагальнення, які включають зовніпланарні графи. До цих класів належать також реберні графи дерев і кактуси.

Гамарник і Свириденко використовували алгоритм лінійного часу для розв'язання задачі на деревах для вивчення асимптотичного числа ребер, які потрібно додати до розрідженого випадкового графу, щоб зробити його гамільтоновим.

Примітки

1. Wu, Lu, Lee, 2000, с. 156 – 167.
2. Takamizawa, Nishizeki, Saito, 1982, с. 623–641.
3. Корниенко, 1984, с. 109-111.
4. Raychaudhuri, 1995, с. 299 – 306.
5. Agnetis, Detti, Meloni, Pacciarelli, 2001, с. 17 – 24.
6. Detti, Meloni, 2004, с. 197 – 215.
7. Gamarnik, Sviridenko, 2005, с. 139 – 158.

Література

• Takamizawa K., Nishizeki T., Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // . — 1982. — Т. 29, вип. 3 (17 червня). — С. 623–641. — DOI:10.1145/322326.322328.
• Wu Q. S., Lu C. L., Lee R. C. T. An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree // Algorithms and Computation / Goos G., Hartmanis J., van Leeuwen J. — Springer, 2000. — Т. 1969. — (Lecture Notes in Computer Science) — .^{[недоступне посилання з Март 2020]}
• Korneyenko N. M. Combinatorial algorithms on a class of graphs // . — 1994. — Т. 54, вип. 2-3 (17 червня).
• Raychaudhuri A. The total interval number of a tree and the Hamiltonian completion number of its line graph. — Information Processing Letters. — 1995. — Т. 56.
• Agnetis A., Detti P., Meloni C., Pacciarelli D. A linear algorithm for the Hamiltonian completion number of the line graph of a tree. — Information Processing Letters. — 2001. — Т. 79.
• Detti P., Meloni C. A linear algorithm for the Hamiltonian completion number of the line graph of a cactus // Discrete Applied Mathematics. — 2004. — Т. 136, вип. 2-3 (February).
  • Н.М. Корниенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вип. 3 (17 червня). — С. 109-111.
• Gamarnik D., Sviridenko M. Hamiltonian completions of sparse random graphs // Discrete Applied Mathematics. — 2005. — Т. 152 (17 червня). з джерела 25 січня 2022. Процитовано 4 січня 2021.