исключение негамильтоновых путей в графе

Question

Предположим, что у нас есть случайный граф. Как удалить или добавить ребра за минимальное количество шагов, чтобы каждое ребро в результирующем графе находилось на пути Гамильтона?

Я был бы очень признателен, если бы кто-то мог поделиться какими-либо идеями.

Answer 1

Существует алгоритм быстрого поиска путей Гамильтона в определенных случайных графах из-за Angluin – Valiant .Возможно, вы могли бы запустить его несколько раз для каждого ребра в графе, чтобы расширить это ребро до пути Гамильтона, добавляя ребра в случае неудачи.