NP-полный граф свойство, которое является наследственным, но не аддитивным?

12

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

Нетрудно найти свойства, которые являются наследственными, но не аддитивными. Два простых примера:

$\;\;\;$ (1) График полон.

$\;\;\;$ (2) Граф не содержит двух вершинно-непересекающихся циклов.

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

Оба приведенных выше примера являются разложимыми по полимеру свойствами (хотя для (2) это несколько менее тривиально). Если нам нужны более сложные свойства, их все равно можно создать, следуя шаблону (2), но заменив циклы более сложными типами графов. Затем, однако, мы можем легко работать в ситуацию , когда проблема даже не останется в , при стандартных предположениях сложности, таких как . Кажется менее тривиальным найти пример, который остается в пределах , но это все еще сложно. $NP$ $NP\neq coNP$ $NP$

Вопрос: Известно ли вам (предпочтительно естественное) свойство полного графа, которое наследственное, но не аддитивное? $NP$

cc.complexity-theory graph-theory graph-algorithms np Андрас Фараго
источник

4

Вы задали несколько вопросов о «естественных» свойствах. Может быть полезно понять, какова мотивация для некоторых из этих вопросов.

Суреш Венкат

1

@Suresh Я хотел бы лучше понять, что делает проблему естественной, а не надуманной, искусственной. Я думаю, концепция естественности является важным мостом между теорией и реальностью, и ее стоит изучить. Что меня интересует, так это то, что, хотя у нас нет формального определения того, какие проблемы являются «естественными», люди обычно имеют четкое согласие относительно того, является ли конкретная проблема естественной или нет. Возможно, я опубликую отдельный вопрос об этой проблеме, чтобы узнать больше о том, как другие видят ее.

Андрас Фараго

9

$k$ $k$

Ясно, что взятие индуцированных подграфов не может увеличить минимальный размер такого раздела. С другой стороны, когда вы берете несвязное объединение двух графов, вы должны взять объединение разбиения на клики каждого из них.

Виниций душ Сантуш
источник

k

$k$

k

$k$

k

$k$

k

$k$

h e r e d i t a r y

$hereditary$

k

$k$

k

$k$

4

k

$k$

k

$k$

1

k = 3

$k=3$

G_{1}

$G_1$

G_{2}

$G_2$

1

Рассмотреть эту проблему

$G$ $P$ $Q$

Он остается NP завершенным, даже если свойства являются наследственными.

Теперь ясно, что решение вышеуказанной проблемы для графа также обеспечивает решение для индуцированных подграфов. Но при объединении графов того же семейства, что и G, это решение не может быть решено.

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

Dibyayan
источник

1

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

Андрас Фараго

1

$G = (V,E)$ $C_1,\ldots,C_m$ $C_i$ $V$ $E$ $C_i$

$k \geq 3$ $G$ $k$

$k = 2$

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

(ПРИМЕЧАНИЕ ДОБАВЛЕНО: гипотеза (2) отличается от «гипотезы о двойном цикле покрытия» Секереса и Сеймура, несмотря на то, что это однозначно).

Super8
источник

1

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

Андрас Фараго

G

$G$

G

$G$

v

$v$

v

$v$

k

$k$

NP-полный граф свойство, которое является наследственным, но не аддитивным?

Ответы: