Является ли проблема множества вершин обратной связи разрешимой за полиномиальное время для 3-градусных ограниченных графов?

19

Набор вершин обратной связи NP-полон для общих графов. Известно, что он является NP-полным для ограниченных графов степени 8 из-за сокращения от покрытия вершины. В статье в Википедии говорится, что она разрешима по времени для ограниченных графов степени 3 и является NP-полной для ограниченных графов степени 4. Но я нигде не смог найти никаких доказательств этого. Это правда?

Какой минимум d такой, что FVS в ограниченных по степени d графах NP-полон?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree Дэвис Иссак
источник

1

Кто-нибудь знает, сильно ли проблема на 4-й степени регулярных неориентированных графов?

10

Алгоритм Ли и Лю неверен (он опубликован в Китае, хотя и на английском). Алгоритм Уэно и др. Является правильным, и аналогичный алгоритм можно найти в Furst et al. 1 . Оба алгоритма сводят задачу к полиномиально разрешимой проблеме четности матроидов [3].

Его уменьшение от VC обеспечивает NP-твердость для графа степени 6! Как VC уже NP-hard на кубических графах. Спекенмейер утверждал, что его диссертация [4] содержит доказательство NP-твердости FVS на плоских графах максимальной степени четыре, но это очень трудно найти (я буду очень признателен, если кто имеет доступ к его диссертации, может выслать мне копию ). К счастью, новое доказательство NP-твердости ограниченных графов четвертой степени можно найти в 2 :

Замечания по поводу 2 : - Фактически, он доказал, что проблема APX-сложная, но легко проверить, что его сокращения также действительны для доказательства NP-сложности задачи. - Его сокращение не распространяется на плоские графики.

Меррик Л. Фёрст, Джонатан Л. Гросс и Лайл А. МакГеох, «Нахождение вложения графа максимального рода», журнал ACM, vol. 35, нет 3, стр. 523–534, 1988. 10.1145 / 44483.44485
Риззи, Р .: Трудно найти основы фундаментального цикла. Algorithmica 53 (3), 402-424 (2009) 10.1007 / s00453-007-9112-8
Ласло Ловаш, «Проблема соответствия матроидов», в алгебраических методах теории графов, сер. Colloquia Mathematica Societatis János Bolyai, vol. 25, Сегед, Венгрия, 1980, с. 495–517.
Эвальд Спекенмейер, “Задача множества вершин обратной связи Untersuchungen zum в ungerichteten graphen”, кандидатская диссертация, Universität-GH Paderborn, Reihe Informatik, Bericht, 1983.

Исин Цао
источник

9

Есть ли простая причина, почему это «явно неправильно»?

Суреш Венкат

2

@SureshVenkat Извините за поздний ответ: я только что заметил этот вопрос. Критическая ошибка в теореме 4.2, которая является основной теоремой этой статьи. Он утверждает , что дано сопоставление смежности и пару ребер в большем согласующем смежности , но не в , они могут увеличить путем добавления к . Это явно неверно, потому что определение соответствия смежности требует удаления всех ребер соответствия смежности, НЕ отключает граф.

M

$M$

{e_{1}, e_{2}}

$\{e_1,e_2\}$

M^{'}

$M'$

M

$M$

M

$M$

{e_{1}, e_{2}}

$\{e_1,e_2\}$

M

$M$

Исинь Цао

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

M

$M$

v

$v$

M^{'}

$M'$

v

$v$

M

$M$

Исинь Цао

9

Соответствующие ссылки выглядят так:

Уэно, Шуичи; Кадзитани, Йоджи; Gotoh, Shin'ya. О неразделимой задаче о независимом множестве и задаче об обратной связи для графов без степени вершины, превышающей три. Материалы первой японской конференции по теории графов и их приложениям (Hakone, 1986). Дискретная математика 72 (1988), нет. 1-3, 355–360 .

Ли, Деминг; Лю, Янпей. Полиномиальный алгоритм для нахождения минимального множества вершин обратной связи 3-регулярного простого графа. Acta Math. Sci. 19 (1999), № 4, 375–381.

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

Дэвид Эппштейн
источник

Является ли проблема множества вершин обратной связи разрешимой за полиномиальное время для 3-градусных ограниченных графов?

Ответы: