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