NP-сложные проблемы на деревьях

47

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

Шива Кинтали
источник
1
Юкка, это спорно , если «вики сообщества» необходимо здесь. Очевидно, что надуманные проблемы с малой актуальностью, в любом случае, вероятно, будут отвергнуты.
Райан Уильямс
1
Я также склонен думать, что CW не нужен
Суреш Венкат
2
Не уверен, что нужен CW. Я не могу думать ни о какой проблеме вне головы. Похоже, постеры должны быть вознаграждены за ответы на этот вопрос.
Робин Котари
5
Несколько случайных обращений Google к исследовательским работам, которые показывают, что проблема NP-сложна, даже если входные данные - дерево: маршрутизация с использованием емкостного транспортного средства , проблема минимальной задержки , планирование вызовов ...
Юкка Суомела,
4
Это не то, о чем вы просили, но стоит упомянуть здесь: есть некоторые проблемы, которые просты на деревьях, но трудны на ограниченной ширине дерева. Например, непересекающиеся по краям пути (Nishizeki, Vygen, Zhou '01) и диапазон матрицы ограничений (McDiarmid, Reed '03).
Диего де Эстрада

Ответы:

23

Вы можете найти «естественные» и «общеизвестные» примеры проблем с графами, которые являются сложными, даже если они ограничены деревьями из нашей стандартной ссылки . Примеры:

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


Более общий рецепт для создания задач, которые сложны для деревьев: Возьмите любую NP-сложную задачу, связанную с суперпоследовательностями , суперструнами , подстроками и т. Д. Затем заново интерпретируйте строку как помеченный граф путей. Затем задайте аналогичный вопрос для общих графов (подпоследовательность - младший граф, подстрока - подграф). И мы знаем, что проблема NP-трудна даже на деревьях (и на дорожках).


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

  • TSP с двумя путешественниками : с учетом взвешенного по ребрам графа и предела , можем ли мы найти два закрытых блуждания и в таких, что каждый брутто имеет общий вес не более , а каждый узел покрыт хотя бы одним ходить?W C 1 C 2 G W GGWC1C2GWG

Опять же, легко придумать варианты темы.

Юкка Суомела
источник
Жаль, что сборник больше не обновляется.
Энтони Лабарр
Что такое «помеченный граф путей»?
Дэвид
29

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

Смотри, например, Gregori, IPL 1989 .

Дэвид Эппштейн
источник
Итак, это подразумевает твердость прямолинейного рисунка деревьев? Есть ли степень, которая сохраняет твердость?
Мухаммед Аль-Туркистани
2
В отношении степени: если существует вершина степени больше четырех, то вложение в сетку невозможно.
Дэвид Эппштейн
Спасибо Дэвид, просто заявить, но интересная проблема.
Мухаммед Аль-Туркистани
О, дерево ввода также является двоичным деревом. Замечательно!
Cyriac Antony
24

Задача Group Steiner - хороший пример. Вход в эту задачу - неориентированный гранично-взвешенный граф и k групп вершин . Цель состоит в том, чтобы найти дерево минимального веса, которое содержит хотя бы одну вершину из каждой группы. Легко видеть, что проблема Set Cover является особым случаем, даже когда G - звезда. Таким образом, проблему трудно приблизить с точностью до если P = NP. Более того, Гальперин и Краутгамер показали, что проблему трудно приблизить с точностью до фактора для любого фиксированного если только NP не имеет рандомизированных алгоритмов квазиполиномиального времени ( см. документ для точного утверждения). ЕстьS 1 , S 2 , , S k O ( log n ) O ( log 2 - ϵ n ) ϵ > 0 O ( log 2 n )G=(V,E)S1,S2,,SkO(logn)O(log2ϵn)ϵ>0O(log2n) приближение на деревьях Гаргом, Коньеводом и Рави.

Чандра Чекури
источник
4
Аааа: неформатный латекс !! это ранит глаза :)
Суреш Венкат
Ну, я не знаю, как сделать латексное форматирование здесь :). Указатели ??
Чандра Чекури
просто используйте $ .. $ как обычно.
Суреш Венкат
хорошо все исправлено.
Суреш Венкат
22

Одной из самых сложных проблем на деревьях является проблема минимальной пропускной способности. Это твердый материал на деревьях максимальной степени 3. Также он NP-жесткий на круглой гусенице с длиной волос 1.NP

Рекомендации:

Майкл Р. Гэри, Рональд Л. Грэм, Дэвид С. Джонсон и Дональд Э. Кнут. Результаты сложности для минимизации пропускной способности. SIAM J. Appl. Math., 34 (3): 477-495, 1978.

Буркхард Моньен. Задача минимизации полосы пропускания для гусениц с длиной волос 3 является NP-полной. SIAM J. Алгебраические дискретные методы, 7 (4): 505-512, 1986.

У. Унгер. Сложность аппроксимации проблемы пропускной способности. В ВОК, стр. 82–91, 1998

Мухаммед Аль-Туркистани
источник
1
Исправленная версия статьи Унгера « Результаты твердости для аппроксимации пропускной способности» , Чандан Дубей, Уриэль Фейдж и Уолтер Унгер.
Юваль Фильмус
14

Невзвешенная проблема край MultiCut заключается в следующем: Учитывая неориентированный граф , набор пара вершин , и положительные целое число , найти , если существует подмножество из не более ребер в устранение которых отсоединяется каждая пара вершины в коллекции.G K S K GGGkSkG

Эта проблема является NP-сложной (и MAX SNP-сложной) для звезд [ 1 ].

[ 1 ] Гарг, Вазирани и Яннакакис, Алгоритмы примитивного двойного приближения для интегрального потока и мультирез в деревьях , Algorithmica, 18 (1), стр. 3-20, 1997.

gphilip
источник
13

Проблема пожарного в последнее время привлекла к себе значительное внимание, и (несколько удивительно) NP-трудна для деревьев максимальной степени 3 . На самом деле это довольно естественный вопрос, который описывается следующим образом:

Возникает пожар в корне дерева (или, в более общем случае, в указанной вершине графа). На каждом этапе пожарный защищает одну не горящую вершину, после чего огонь распространяется на каждого незащищенного соседа. Процесс заканчивается, когда рядом с огнем нет незащищенной вершины. Есть ли у пожарного стратегия, в которой горят не более вершин?k

Или вариант, также NP-hard : есть ли у пожарного стратегия, при которой не горит лист?

Эндрю Д. Кинг
источник
8

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

Известно, что он является NP-сложным на взвешенных звездных графиках. Тем не менее, открыто, является ли проблема NP-трудной в самолете. Можно утверждать, что NP-твердость происходит не от «древовидности», а от «произвольной метрики», но звездные графы дают вам только ограниченное пространство метрик.

Суреш Венкат
источник
8

TV(T)kϕ:V(T){1,,k}Tii+1KK

k

user13136
источник
8

Империя окраски NP-трудна для деревьев.

rsGr(s,r)sCOLrGs

sCOLrs{3,,2r1}s

Йенс Г.
источник
7

Поток в сети является слитым, если он использует не более одной исходящей дуги на каждом узле. NP-трудность определения максимального потока слияния в дереве (диаметром 4, с несколькими допустимыми стоками) доказана в работе: D. Dressler и M. Strehler, Capacitated Confluent Flows: сложность и алгоритмы, LNCS 6078 (2010) 347-358 ,

Тобиас Мюллер
источник
6

TSTT1TSTT1T

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

Джанлука Делла Ведова
источник
6

Гармоничная раскраска простого графа - это правильная раскраска вершин, так что каждая пара цветов появляется вместе не более чем на одном ребре. Гармоничное хроматическое число графа - это наименьшее количество цветов в гармоничной раскраске графа. Эдвардс и МакДиармид показали, что эта проблема поиска Гармоничного Хроматического Числа является NP-полной на деревьях . Фактически они также показывают, что проблема остается NP-полной для деревьев радиуса 3.

Ашутош Рай
источник
5

uu

Обратите внимание, что в связанной (и более известной) проблеме TSP цель состоит в том, чтобы минимизировать максимум, а не среднюю задержку. Я думаю, что TRP обычно считается более сложной проблемой (на самом деле TSP находится в P для метрик дерева).

NP-твердость на деревьях была показана в РА «Ситтерс» «Проблема минимальной задержки NP-Hard для взвешенных деревьев», ISCO 2002.

Майкл Лэмпис
источник
1
Это хорошая проблема!
Tayfun Pay
3

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

SCG=(V,E)SVCVSC=sS|s|FfF|f|eEteRC×F(c,f)Rcf

sSAsfAs|f||s|PrGr=(c,f)RcsfAseDer=(c,f)DePre(c,f)De|f|te

Если вам не нужны все загрузки , чтобы маршрутизировать , но вместо того, чтобы попытаться максимизировать сумму filesizes скачанных файлов , которые являются маршрутизацией вы можете легко уменьшить подмножество-сумму к этой проблеме: у вас есть один сервер с огромным количеством пространства, один клиент, подключенный к серверу с ребром, емкость которого равна целевому значению экземпляра subset-sum, и для каждого целого числа в экземпляре subset-sum вы создаете файл одинакового размера; Затем клиент желает загрузить все эти файлы.

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

USP(U)uU

sSusu

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

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

Алекс тен Бринк
источник
3

Нерасщепляемая проблема потока. На самом деле UFP жесток даже на одном ребре (рюкзак).

Ариндам Пал
источник
3

G(V,E)NP

Формально проблема заключается в следующем:

РАЗДЕЛЕННЫЙ ГРАФИЧЕСКИЙ ИЗОМОРФИЗМ

T=(V,E)

{E1,E2}ET1=(V,E1)T2=(V,E2)

В колонке NP-полноты цитируется неопубликованная рукопись Грэма и Робинсона «Изоморфная факторизация IX: четные деревья».

Д.С. Джонсон, столбец NP-полноты: постоянное руководство, Journal of Algorithms 3 (1982), 288–300

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

Каким-то образом я пропустил проблему Ахроматического числа в последнем ответе, но это одна из наиболее естественных проблем, о которых я знаю, которые являются NP-полными на деревьях.

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

Яннакакис и Грэвил доказали, что эта проблема NP-трудна в дополнении двудольных графов . Кэрни и Эдвардс расширили этот результат и показали, что проблема является NP-полной на деревьях .

Большая работа была проделана по этой проблеме в области алгоритмов аппроксимации [ 3 , 4 , 5 ].

Ашутош Рай
источник
-1

Является ли Circuit SAT на деревьях NPC? Внутренние вершины дерева помечены как вентили OR / AND. Листья являются входами. Определите, есть ли удовлетворительный набор входов для схемы, чтобы оценить к Истине.

2k1

Чад Brewbaker
источник
1
Хм, схемы, которые являются деревьями, имеют название: формулы. Формула SAT, конечно, является NP-полной, так как 3-SAT или даже полная CNF-SAT являются ее частными случаями.
Эмиль Йержабек поддерживает Монику
1
Как так? Все формулы являются деревьями. Если вы хотите ограничить множественные вхождения переменных, это дополнительное ограничение. (Я также предполагаю, что когда вы пишете «входы», вы на самом деле имеете в виду «литералы», так как Circuit SAT только с AND, OR и положительными литералами тривиально полиномиального времени для начала.)
Эмиль Йержабек поддерживает Monica
1
((a+b)+c)+d((a+b)+c)+a
1
(pq)p
1
Это не проблема игрушек. Это стандартная терминология, когда когда мы говорим, что схема - это дерево, это не означает, что переменные появляются только один раз. В любом случае, независимо от того, что мы называем это, предложенная вами проблема тривиальна, как я написал.
Каве