Максимальное количество внутренне непересекающихся вершин нечетной длины st путей

18

Пусть - неориентированный простой граф, и пусть - различные вершины. Пусть длина простого st-пути будет числом ребер на пути. Мне интересно вычислить максимальный размер набора простых st-путей, чтобы каждый путь имел нечетную длину, а наборы вершин каждой пары путей попарно пересекались только по s и t. Другими словами, я ищу максимальное количество внутренне непересекающихся вершин st нечетной длины. Я думаю, что это должно быть вычислено за полиномиальное время с помощью методов сопоставления или потока, но я не смог придумать алгоритм. Вот что я знаю о проблеме.Gs,tV(G)

  1. Мы можем заменить ограничение на нечетную длину четной длиной; это на самом деле не влияет на проблему, так как одно превращается в другое, если мы подразделяем все ребра, попадающие на s.

  2. Если нет ограничений на четность путей, то теорема Менгера дает ответ, который может быть получен путем вычисления максимального потока.

  3. Задача определения максимального числа непересекающихся вершин циклов нечетной длины, попарно пересекающихся только в данной вершине v, вычисляется за полиномиальное время с помощью соответствующего трюка: построить граф G 'как несвязное объединение и , добавление ребер между двумя копиями одной вершины; максимальное совпадение в этом графе размера означает, что максимальное число нечетных циклов через равно ; эта конструкция описана в доказательстве леммы 11 « О нечетно-минорном варианте гипотезы Хадвигера» .( G - N G [ v ] ) | V ( G ) | - | N G [ v ] | + k v k(Gv)(GNG[v])|V(G)||NG[v]|+kvК

  4. Если граф направлен, то проверка существования единственного st-пути четной длины уже NP-завершена.

  5. Статья Проблема четного пути для графов и орграфов Лапо и Пападимитриу может быть актуальной, но, к сожалению, наша библиотека не подписана на онлайн-архив, и у нас нет бумажной копии.

Любые идеи будут высоко оценены!

Барт Янсен
источник
1
Документ кажется очень актуальным. Я могу получить его в понедельник, если никто другой не получит его до тех пор.
Домоторп
Андрас Саламон уже прислал мне копию; Спасибо за предложение!
Барт Янсен

Ответы:

5

Во-первых, отметим, что: для заданного графа , двух выделенных вершин s , t V и целого числа k задача о том, существует ли k внутренне непересекающихся вершин путей нечетной длины между s и t, является полиномиальной эквивалентно решению, существует ли k путей четной длины между s и t . Снижение легко. Чтобы уменьшить от одного случая до другого, просто подразделите каждое ребро, смежное с t . Пусть G G=(V,E)s,tVkkstksttGбыть полученным графиком. Тогда имеет K нечетной длиной вершин непересекающихся путей между й и т тогда и только тогда G ' имеет к даже длинам вершин непересекающихся путей между й и т .GkstGkst

Поэтому, если одна из этих проблем является NP-полной, то и другая. Теперь Итай, Перл и Шилоах показывают, что проблема определения, существует ли непересекающихся вершин длиной пять между s и t, является NP-полной [ Сложность нахождения максимальных непересекающихся путей с ограничениями длины . Сети, том 12, выпуск 3, страницы 277-286, 1982.] Сокращение от 3SAT, и в построенном графе пути нечетной длины между s и t имеют длину ровно пять. Следовательно, проблема непересекающихся вершин путей нечетной длины в NP-полной, как и вершинно-непересекающиеся пути четной длины.kstsT

Надеюсь это поможет.

Сомнатх
источник
«Следовательно, задача о путях нечетной длины вершинного дизъюнкта является NP-полной».
Крис
Спасибо за ваше понимание Сомнатх; сокращение в статье очень актуально. Однако я не согласен с вашим утверждением, что «в построенном графе пути нечетной длины между s и t имеют длину ровно пять»; глядя на примерный график на рис. 5 на странице 282 их статьи, (s; w1,1; x1,1; c3; -x1,1; y1,1; z1,1; t) - это нечетный путь длина 7. Однако, похоже, что конструкцию можно использовать для доказательства NP-полноты моей задачи; Благодарность!
Барт Янсен
6

(Это не ответ, но я пока не могу комментировать) Я думаю, что приведенный выше ответ не работает, потому что он не гарантирует, что пути будут непересекающимися. Один путь может использовать u ', а другой u "в G'; в G они будут использовать одну и ту же вершину u.

Каролина Солтыс
источник
Это должен быть комментарий к этому ответу.
Деррик Столи
@ Деррик: Вам нужно 15 репутации, чтобы добавлять комментарии, которых у Каролины еще не было.
Чарльз Стюарт
@Charles: Nitpicking: это 50, а не 15.
Tsuyoshi Ito
Ах, к сожалению. Продолжать.
Деррик Столи