Можно ли эффективно равномерно выбрать соседа вершины в графе многогранника?

15

У меня есть многогранник определенный как .P{x:Axb,x0}

Вопрос: Учитывая вершину из P , есть ли алгоритм полиномиального времени для равномерной выборки из соседей v в графе P ? (Многочлен в измерении, число уравнений и представление б . Я могу предположить, что число уравнений является полиномиальным в измерении.)vPvPb

Обновление: я думаю, что я смог показать, что это сложный NP, см. Мой ответ, который объясняет аргумент. (И под NP жестким я подразумеваю, что алгоритм за полиномиальное время докажет RP=NP ... не уверен, какая здесь правильная терминология.)

Обновление 2: есть 2-строчное доказательство NP -твердости (учитывая правильный комбинаторный многогранник), и мне удалось найти его в статье Хачияна. Смотрите ответ для описания и ссылку. :-D


Эквивалентная проблема :

В комментариях Петр Шор указал, что этот вопрос эквивалентен вопросу о том, можем ли мы равномерно выбирать из вершин данного многогранника. (Я думаю, что эквивалентность выглядит следующим образом: в одном направлении мы можем перейти от многогранника P с вершиной v к фигуре вершины в v , P/v , и выборка вершин P/v эквивалентна выборке соседей v на п В другом направлении мы можем перейти от многогранника п к многограннику Q одного более высокого измерения, добавив конус с вершиной v и основанием п, Тогда выборка соседей v в Q эквивалентна выборке вершин п )

Эта формулировка вопроса уже задавалась ранее: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope


Лоренцо Найт
источник
Я не знаю ответа на ваш вопрос, но, насколько мне известно, не существует известной NP-твердости для равномерной выборки вершины многогранника, заданного явно. Например, приблизительно циклы отбора проб являются NP-сложными. Однако, если бы существовала какая-то линейная программа, вершины которой кодируют циклы, то очень вероятно, что вы сможете оптимизировать длину цикла и таким образом решить цикл Гамильтона.
Хэн Го
Еще одно замечание: даже если ваш вопрос имеет положительный ответ, он не дает единого сэмплера для вершин (при условии гипотезы 0-1 многогранника). Каркас многогранника в большинстве интересных случаев не является регулярным, и степени могут изменяться экспоненциально.
Хэн Го
@HengGuo Еще раз спасибо за комментарии, они очень полезны. Вы знаете хороший пример, где степени меняются в геометрической прогрессии? (Я не удивлен, что это может случиться с обычными многогранниками; было бы неплохо иметь комбинаторный пример, если узнаешь один из них на макушке головы.)
Лоренцо Найт
Рассмотрим многогранник независимых множеств двудольного графа. Две вершины (два независимых множества) связны, если их симметрическая разность индуцирует связный подграф. Теперь возьмем двудольный граф, одна сторона которого имеет только две вершины, соединяется с каждой вершиной на другой стороне и v 2 только одна. Рассмотрим независимые множества { v 1 } и { v 2 } . v1v2{v1}{v2}
Хэн Го
5
Равномерная выборка соседних вершин данной вершины многогранника - это та же проблема, что и выборка случайной вершины многогранника равномерно. Отрубить конус бесконечно близко к вершине. Затем у каждого есть новый многогранник, и если вы можете выбрать вершину этого нового многогранника, можно выбрать соседнюю вершину исходного многогранника. Я предполагаю, что делать это примерно в BPP, но я не могу найти ни одной бумаги, которая доказывает это.
Питер Шор

Ответы:

4

Изменить 2: смущающе, есть две строки доказательства NP -твердости, если начать с правильного многогранника.

Во-первых, вспомнить циркулярный многогранник графа внизу страницы 4 Трудно сгенерировать все вершины многогранника .

Его вершины находятся в биективном соответствии с направленными простыми циклами. Поэтому их трудно отобрать или подсчитать по предложению СП 5.1 . :-D

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


Изменить: я записал аргумент ниже, и он выглядит правильно. Тем не менее, есть гораздо более простой аргумент, который я изложу здесь:

а) Анализ алгоритмов возврата для перечисления всех вершин и всех граней выпуклого многогранника (Фукуда и др.) сильно затрудняет решение следующей задачи на многогранниках:

Вход: многогранник Ax=b,x0 в Rn подмножестве Sn

Вывод: существует ли вершина v из P , которая отлична от нуля на каждой из координат в S .

б) Учитывая это, можно сделать следующую конструкцию: ввести новые переменные yik для iS и k=1,,d и ввести неравенство 0yikxi . Назовите получившийся многогранник PS,d . Смысл этой конструкции состоит в том, чтобы ввести гиперкуб над каждой вершиной размерности d|supp(x)S|,

в) Можно проверить, что все вершины этого многогранника лежат над вершинами старого многогранника и что число вершин над вершиной равно 2d|supp(x)S|где supp - функция, которая отправляет вершину в координаты, где она отлична от нуля.

d) Из обычной цепочки аргументов типа бигонов следует, что, беря d достаточно большого размера, равномерная выборка из вершин PS,d (с высокой вероятностью) даст выборку из вершин, максимизирующую размер их пересечения с S ,

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


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

Лоренцо Найт
источник
Это очень интересный аргумент! Я не полностью проверил все детали в части 3) (что это за функции , H 0 , l e a v e s ?), Но в принципе любая не охватывающая структура может подвергаться только суперэкспоненциальному взрыву, который таким образом, можно контролировать, принимая d полинома большим. H1H0leavesd
Хэн Го
@HengGuo Спасибо за чтение! По Я имею в виду количество компонентов и | H 1 | размерность пространства цикла (ранг цепи) и «оставляет» количество вершин степени 1. Я добавлю эти определения. |H0||H1|
Лоренцо Найт
Там должно быть что-то не так с этим. Если есть многогранник, вершинами которого являются лассо и простые циклы, разве мы не можем использовать линейное программирование, чтобы максимизировать любую линейную функцию, которую мы хотим, над этим многогранником? И разве это не позволило бы нам найти охватывающее лассо за полиномиальное время?
Питер Шор
@PeterShor Я думаю, что этого не происходит, потому что многогранник живет внутри гиперплоскости, определенной путем установки суммы граничных переменных в единицу. Так что этот функционал постоянен по многограннику. Функция, которая представляет количество ребер, является размером опоры вектора, которая является нелинейной на этом многограннике.
Лоренцо Найт
@PeterShor Я добавил доказательство того, что функция «число ребер» не может быть линейной, см. Рисунок внизу.
Лоренцо Найт