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

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

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

ds.algorithms graph-theory Jagadish
источник

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

Робин Котари

Это правильно, но равномерное распределение не было запрошено (если возможно подразумевается).

Рафаэль

Да, меня не волнует единообразие. Я хотел бы дать каждому графу в семействе негамильтоновых графов некоторый шанс быть выбранным. Проблема с равномерной выборкой довольно проста: AFAIK, мы не знаем, как сделать выборку равномерно из семейства графиков размера n, не говоря уже о гамильтоновых циклах.

Джагадиш

Ответы:

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

Ноам
источник

Вы предполагаете, что такая функция относится к классу негамильтоновых графов. Это только в том случае, если мы хотим, чтобы распределение было равномерным. См. Также комментарий Аарона ниже: cstheory.stackexchange.com/questions/562/…

Охад Каммар

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

Ноам

Я согласен, важна не равномерность распределения, а тот факт, что все негамильтоновы графы имеют ненулевую вероятность. Если хотя бы один из них имеет нулевую вероятность, ваше доказательство не применяется (без дополнительных знаний о поддержке дистрибутива).

Охад Каммар

@Ohad: если один из них пропущен, то вы можете просто добавить это в справочную таблицу. Я думаю, что проблемы начинаются только в том случае, если вы пропускаете положительную часть из них, но тогда вы не делаете выборку равномерно.

Эмиль

1 - ϵ

$1-\epsilon$

ϵ

$\epsilon$

ϵ \to 0

$\epsilon \rightarrow 0$

\infty

$\infty$

$G_{n,m}$ $m$ $n$

$n$

Аарон Рот
источник

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

JimN

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

Мухаммед Аль-Туркистани
источник

Я думаю, что ответ Туркистани поднимает интересный вопрос. В общем, возможно ли сэмплировать единообразно на языке, совместимом с NP?

Суреш Венкат

.... и Ноам отвечает на это отрицательно.

Суреш Венкат