Как получить случайный граф, не имеющий гамильтонова цикла?

28

Пусть класс A обозначает все графы размера которые имеют гамильтонов цикл. Из этого класса легко получить случайный граф - возьмите n изолированных узлов, добавьте случайный гамильтонов цикл и затем случайным образом добавьте ребра.nn

Пусть класс B обозначает все графы размера которых нет гамильтонова цикла. Как мы можем выбрать случайный граф из этого класса? (или сделать что-то близкое к этому)n

Jagadish
источник
3
Как ясно, что первая процедура выдает графики равномерно случайным образом? Понятно, что он всегда создает гамильтоновы графы, но поскольку вы случайно добавляете ребра позже, вы можете ввести больше гамильтоновых циклов, в результате чего некоторые графы появляются чаще, чем другие.
Робин Котари
Это правильно, но равномерное распределение не было запрошено (если возможно подразумевается).
Рафаэль
1
Да, меня не волнует единообразие. Я хотел бы дать каждому графу в семействе негамильтоновых графов некоторый шанс быть выбранным. Проблема с равномерной выборкой довольно проста: AFAIK, мы не знаем, как сделать выборку равномерно из семейства графиков размера n, не говоря уже о гамильтоновых циклах.
Джагадиш

Ответы:

34

Это невозможно (если только NP = coNP), поскольку, в частности, это подразумевает функцию поли-времени, диапазон которой является негамильтоновыми графами (функция переходит от случайной строки к выходному графу), что, в свою очередь, подразумевает NP-доказательство негамильтоновости (чтобы доказать, что G не имеет гамильтонову цепь, покажите x, отображающий ее.)

Ноам
источник
3
Вы предполагаете, что такая функция относится к классу негамильтоновых графов. Это только в том случае, если мы хотим, чтобы распределение было равномерным. См. Также комментарий Аарона ниже: cstheory.stackexchange.com/questions/562/…
Охад Каммар
5
Это не предполагает ничего о вероятностях выбора каждого графа (например, что он равномерен), только то, что графики, которые могут быть выведены алгоритмами, являются именно негамильтоновыми (на). Если вы допустите ошибку с любой стороны, то это действительно возможно.
Ноам
1
Я согласен, важна не равномерность распределения, а тот факт, что все негамильтоновы графы имеют ненулевую вероятность. Если хотя бы один из них имеет нулевую вероятность, ваше доказательство не применяется (без дополнительных знаний о поддержке дистрибутива).
Охад Каммар
1
@Ohad: если один из них пропущен, то вы можете просто добавить это в справочную таблицу. Я думаю, что проблемы начинаются только в том случае, если вы пропускаете положительную часть из них, но тогда вы не делаете выборку равномерно.
Эмиль
3
1ϵϵϵ0
11

Gn,mmn

n

Аарон Рот
источник
Это хорошая идея, хотя мы можем пропустить весь вероятностный алгоритм для нахождения цикла Хэма. Вопрос не задает, что процедура выборки выполняется в ожидаемое время или что-то еще. Поэтому создайте случайный граф из вашего любимого дистрибутива, определите, является ли он гамильтоновым с каким-то точным алгоритмом, а если это гамильтонов, то отбросьте его и повторите процесс. Если используемое распределение было равномерным распределением по всем помеченным графам, это фактически приведет к созданию каждого негамильтонова помеченного графа с равномерной вероятностью.
JimN
1

Первая задача проста, потому что гамильтоновы графы легко проверяются. Тем не менее, нет известных коротких доказательств, которые можно эффективно проверить, чтобы убедиться, что данный граф не является гамильтоновым.

Мухаммед Аль-Туркистани
источник
1
Я думаю, что ответ Туркистани поднимает интересный вопрос. В общем, возможно ли сэмплировать единообразно на языке, совместимом с NP?
Суреш Венкат
5
.... и Ноам отвечает на это отрицательно.
Суреш Венкат