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