NP полный граф задач о структурных свойствах

20

(Этот вопрос немного «опрос».)

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

Пример проблемы, которую я считаю сопоставимой с той, с которой я имею дело:

Для взвешенного турнира , есть ли дуга обратной связи, заданная в G, ребра которой удовлетворяют неравенству треугольника?G=(V,E,w)G

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

Сталкивались ли вы с какими-либо проблемами с решением, которые похожи на это? Вы помните, были ли они полными или в P ? Любая помощь приветствуется.Nпп

Г. Бах
источник
Возможно, вы сможете объяснить структурные свойства вашей проблемы, здесь есть много экспертов, знакомых с доказательствами NPC, и вместо ссылки вы можете получить подтверждение NPC :-)
Marzio De Biasi
@MarzioDeBiasi Я бы очень хотел, чтобы мне не давали доказательства проблемы, с которой я сталкиваюсь; это первый раз, когда я провожу реальные исследования, и я хотел бы посмотреть, где я могу найти себя самостоятельно
Г. Бах,
1
Для меня вопрос звучит слишком расплывчато, и трудно догадаться, что на самом деле задают. Возможно, вопрос следует сделать более конкретным: что вы подразумеваете под «чувствовать себя похожим на это» и что вы подразумеваете под «дугой обратной связи, заданной в G, ребра которой удовлетворяют неравенству треугольника»; Вы хотите получить ссылку на проблему с набором дуг обратной связи или на другую проблему?
Ёсио Окамото
1
@YoshioOkamoto Я понимаю, что в этом вопросе есть некоторая неопределенность, и я надеялся, что пример прояснит кое-что из этого. Под «множеством дуг обратной связи в G, ребра которого удовлетворяют неравенству треугольника», я имею в виду: если - множество дуг обратной связи и ( a , b ) , ( b , c ) , ( a , c ) F , то w ( a , b ) + w ( b , c ) w ( a , c )F(a,б)(б,с)(a,с) Fвес(a,б)+вес(б,с)вес(a,с)должен держать для чтобы выполнить это свойство. Раньше я сталкивался только с подобными проблемами | F | k , но я хочу, чтобы F имел свойство, не связанное с его количеством элементов. F|F|КF
Г. Бах
может кто-нибудь дать ссылку / ссылку на "традиционную проблему с набором дуг обратной связи" ...?
ВЗН

Ответы:

19

Я думаю, что есть много подобных проблем. Вот два в вершинной версии и один в граничной версии:

1) Имеет ли данный граф независимый набор вершин обратной связи? (нас не волнует размер набора). Эта проблема является NP-полной; доказательство может быть получено из доказательства теоремы 2.1 в Garey, Johnson & Stockmeyer .

2) Имеет ли данный граф покрытие вершин, которое индуцирует дерево ? (нас не волнует размер набора). Эта статья дает доказательство NP-полноты этой задачи (теорема 2); даже для двудольных графов.

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

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

VB Le
источник
5
Это именно те проблемы, которые я ищу!
Г. Бах
3
@ G.Bach Так как это точно отвечает на ваш вопрос, я предлагаю вам принять ответ и присудить награду.
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany Я согласен; по какой-то причине я смогу присудить награду только через час.
Г. Бах
4
Спасибо за ваш хороший пост. Я долго думал над одной и той же строкой.
Мухаммед Аль-Туркистани
4

ССNпNп

Д. У. Банге, А. Е. Баркаускас и П. Дж. Слейтер. Эффективные доминирующие множества в графах . Приложения дискретной математики, Учеб. 3-я SIAM Conf., Clemson / South Carolina 1986, 189-199 (1988)., 1988.

Мухаммед Аль-Туркистани
источник
Другими вариантами Доминирующего набора являются Связанный доминирующий набор и Независимый доминирующий набор .
Раду Куртикапин
2
@RaduCurticapean Но с этими вариантами вы заботитесь о размере решения.
VB Le
Да, я упустил это.
Раду Куртикапин
3

NпNп

Отверстие имеет хордовый цикл длиной более трех. Цикл в ориентированном графе является хордовым, если его длина больше 3, и ни одна из его вершин не соединена ребром ориентированного графа, который не принадлежит циклу.

Nпп .

Nп

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

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