NP-сложные задачи на рефератах

12

Этот вопрос похож на NP-сложные задачи на деревьях :

Существует большое количество NP-полных задач, которые можно отследить на рефератах . Есть ли какие-либо известные проблемы, которые остаются NP-полными, если они ограничены Cographs?

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

Два замечания:

Для взвешенных рефератов здесь упоминается такая проблема - TSP с двумя путешественниками
Cographs - это «базовый класс» ширины клика, например, деревья - базовый класс для ширины дерева.

ОБНОВИТЬ

Некоторые дальнейшие размышления (я не совсем уверен в этом): Если входные данные на самом деле представляют собой просто реферат, вопрос должен быть типа «Есть ли у реферата свойство X?». Было бы достаточно, если бы такая проблема существовала для деревьев, с тех пор можно было бы задать вопрос: «Имеет ли род семени свойство X?».

cc.complexity-theory np-hardness graph-algorithms Мартин Лакнер
источник

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

Сянь-Чи Чанг 之之

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

Мартин Лакнер,

11

Возможно, моя любимая открытая проблема представляет интерес: проблема краевого кликового покрытия на cographs. В задаче о покрытии кликом по краям вы хотите покрыть края клиграфа минимальным количеством кликов. Неизвестно, является ли эта проблема NP-полной.

Чтобы проиллюстрировать, что проблема, вероятно, трудная, пусть будет полным многочастным графом с раздельными множествами, каждый из которых имеет размер $K_n^m$ $m$ $n$ . Это реферат. Существуют попарно ортогональных латинских квадрата порядка том и только в том случае, если краевой клик-покров равен . Это показали Парк, Ким и Сано . Это формула для «графика коктейльной вечеринки», то есть для случая, когда . $m - 2$ $n$ $K_n^m$ $n^2$ $n = 2$

Тон Клокс
источник

10

Несколько проблем остаются NP-полными, когда они ограничены Cographs. Раскраска списка, ахроматическое число и индуцированный изоморфизм подграфа остаются NP-полными.

[1] Ханс Л. Бодлендер. Ахроматическое число является NP-полным для графиков и интервальных графиков. Inf. Процесс. Lett., 31 (3): 135–138, 1989

[2] Клаус Янсен и Петра Шеффлер. Обобщенная раскраска для древовидных графов. Дискретное приложение Math., 75 (2): 135–155, 1997

[3] Петр Дамашке. Индуцированный изоморфизм подграфа для рефератов является NP-полным. Конспект лекций в области компьютерных наук, 1991, том 484/1991, 72-78,

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

1

Большое спасибо за ваш ответ. Это действительно интересные проблемы, но я думаю, что они не отвечают требованию, чтобы входные данные были только графом: входные данные в [1] представляют собой граф и целое число, [2] график и набор цветов для каждой вершины, [ 3] два графика.

Мартин Лакнер,

3

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

Дэвид Эппштейн

10

Вот NP-полная проблема для двух заданных рефератов, а не для одной, которая очень закрыта для заданного вопроса. Недавно опубликованная статья показывает, что для заданных рефератов и решено , является ли ретрактом $G$ $H$ $H$ $G$ $H$ $G$ $\rho: V(G)\to V(H)$ $\gamma: V(H)\to V(G)$ $\rho\circ \gamma : V(H)\to V(H)$

VB Le
источник

2

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

Дэвид Эппштейн

1

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

В.Б. Ле

1

G

$G$

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

| V (G_{1}) | \leq | V (G_{2}) |

$|V(G_1)|\le|V(G_2)|$

G_{1}

$G_1$

G_{2}

$G_2$

Дэвид Эппштейн

Ах, это хорошо!

VB Ле

NP-сложные задачи на рефератах

Ответы: