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

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

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

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

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

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

Див. також

• Гіпогамільтонів граф