Задачи, которые просты для невзвешенных графов, но трудны для взвешенных графов

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

Однако есть некоторые (хотя, вероятно, значительно меньше) проблемы, которые решаются за полиномиальное время в невзвешенном случае, но становятся трудными (или имеют открытый статус) в взвешенном случае. Вот два примера:

1. Для заданного вершинного полного графа и целого числа найдите охватывающий подграф с минимально возможным числом ребер. Это разрешимо за полиномиальное время, используя теорему Ф. Харари, которая сообщает структуру оптимальных графов. С другой стороны, если ребра взвешены, то найти минимальный вес связного остовного подграфа является трудным.k ≥ 1 $n$$k\geq 1$$k$$k$$NP$

2. В недавней (декабрь 2012 г.) статье С. Чечика, М. П. Джонсона, М. Партера и Д. Пелега (см. Http://arxiv.org/pdf/1212.6176v1.pdf ) рассматривается, среди прочего, проблема пути, которую они звоните Минимальный путь экспозиции. Здесь ищется путь между двумя указанными узлами, так что количество узлов на пути плюс количество узлов, у которых есть сосед на пути, минимально. Они доказывают, что в ограниченных графах степеней это может быть решено за полиномиальное время для невзвешенного случая, но становится трудным в взвешенном случае, даже с оценкой степени 4. (Примечание: ссылка была найдена как ответ на вопрос, что является сложность этой проблемы пути? )$NP$

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

В мире алгоритмов аппроксимации существует проблема емкостного покрытия вершин. Учитывая и целочисленные емкости c ( v ) для каждого v ∈ V, цель состоит в том, чтобы найти покрытие вершин минимального размера для G, где число ребер, покрываемых v , не больше c ( v ) . Эта задача имеет аппроксимацию с постоянным множителем в невзвешенном случае (то есть мы хотим минимизировать размер покрытия вершин), в то время как она является Ω ( log n ) -твердой (если только$G=(V,E)$$c(v)$$v \in V$$G$$v$$c(v)$$\Omega(\log n)$ ) во взвешенном случае (каждая вершина имеет вес w ( v ), и мы хотим минимизировать вес покрытия).$P = NP$$w(v)$

Мой любимый пример - проблема независимого доминирования (учитывая граф и целое число k , имеет ли G максимальный независимый набор, включающий не более k вершин?). Благодаря хорошему результату благодаря Мартину Фарберу ( см. Здесь ), невзвешенная версия полиномиально разрешима в хордовых графах. Джерард Чанг доказывает, что взвешенная версия является NP-полной для хордальных графов ( см. Здесь ).$G$$k$$G$$k$

Задача идеального соответствия в двудольных графах находится в то время как точный вес идеального соответствия двудольного графа равен N P -полному .$P$$NP$

После ответа Мухаммеда Аль-Туркистани кажется, что многие из решаемых невзвешенных задач за полиномиальное время можно было бы сделать -полными в взвешенном случае, если мы спросим, ​​есть ли решение, которое имеет точно заданный вес. Причина в том, что это может позволить закодировать проблему суммы подмножеств в рассматриваемую задачу.$NP$

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

Балансировка графика (также известная как Min Out-Степень ориентации) является еще одним примером этого явления. В этой задаче нам дан неориентированный гранично-взвешенный граф. Цель состоит в том, чтобы ориентировать края так, чтобы максимальный выходной градус полученного орграфа (взвешенный) был минимизирован.

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

Проблема в NP-hard и APX-hard, даже если все веса равны 1 или 2 (см. Ebenlendr и др. «Балансировка графика: особый случай планирования несвязанных параллельных машин» в SODA 2008). Тем не менее, он находится в P для невзвешенных графов (см. Асахиро и др. «Классы графов и сложность ориентации графа, минимизирующая максимальную взвешенную степень» в CATS 2008).

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

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

$G=(V,E)$$d:V\to\mathbb {N}^+$$c:\to\mathbb {N}^+$$D\in \mathbb {N}^+$$s,t\in V$

$s-t$$D$

$\forall v\in V:d(v) =1$$hop-count$

Если проблема взвешена, она становится ограниченным кратчайшим путем , который, как известно, является NP-полным даже на DAG.

Проблема Local Max Cut с окрестностью FLIP является PLS-полной в общих целочисленных графах.

А. А. Шеффер и М. Яннакакис. (1991). Простые проблемы локального поиска, которые трудно решить. SIAM Journal of Computing, 20 (1): 56-87.

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

Подобное происходит и в других «потенциальных играх».

Торговый продавец открыт на графиках проданных сеток, но цикл Гамильтона (невзвешенный вариант), как известно, является полиномиальным.

Обсуждение обоих на проекте открытых проблем:

http://cs.smith.edu/~orourke/TOPP/P54.html

На 2K_1-свободном максимальном срезе многочлен, а взвешенный максимальный срез - NP-полный.