NP-vollständige Grapheneigenschaft, die erblich, aber nicht additiv ist?

Eine Grapheneigenschaft wird als erblich bezeichnet, wenn sie in Bezug auf das Löschen von Eckpunkten geschlossen wird (dh alle induzierten Untergraphen erben die Eigenschaft). Eine Grapheneigenschaft wird als additiv bezeichnet, wenn sie in Bezug auf disjunkte Gewerkschaften geschlossen ist.

Es ist nicht schwer, Eigenschaften zu finden, die erblich, aber nicht additiv sind. Zwei einfache Beispiele:

$\;\;\;$ (1) Die Grafik ist vollständig.

$\;\;\;$ (2) Der Graph enthält keine zwei vertex-disjunkten Zyklen.

In diesen Fällen ist es offensichtlich, dass die Eigenschaft von induzierten Teilgraphen geerbt wird. Wenn Sie jedoch zwei nicht zusammenhängende Graphen mit der Eigenschaft verwenden, wird sie möglicherweise durch ihre Vereinigung nicht beibehalten.

Beide obigen Beispiele sind entscheidbare Polyzeiteigenschaften (obwohl sie für (2) etwas weniger trivial sind). Wenn wir härtere Eigenschaften wünschen, können sie immer noch nach dem Muster von (2) erstellt werden, wobei jedoch die Zyklen durch kompliziertere Diagrammtypen ersetzt werden. Dann können wir jedoch leicht in die Situation geraten, in der das Problem unter Standard-Komplexitätsannahmen wie nicht einmal in verbleibt . Es scheint weniger trivial zu sein, ein Beispiel zu finden, das innerhalb von bleibt , aber es ist immer noch schwierig. $NP$ $NP\neq coNP$ $NP$

Frage: Kennen Sie eine (möglichst natürliche) vollständige Grapheneigenschaft, die erblich, aber nicht additiv ist? $NP$

cc.complexity-theory graph-theory graph-algorithms np Andras Farago
quelle

Sie haben jetzt eine Reihe von Fragen zu "natürlichen" Eigenschaften gestellt. Es kann hilfreich sein, die Motivation für einige dieser Fragen zu verstehen.

Suresh Venkat

@Suresh Ich möchte besser verstehen, was ein Problem natürlich macht, im Gegensatz zu künstlich erfundenen. Ich denke, das Konzept der Natürlichkeit ist eine wichtige Brücke zwischen Theorie und Realität und es lohnt sich, es zu erkunden. Was mich fasziniert, ist, dass obwohl wir keine formale Definition der "natürlichen" Probleme haben, die Leute normalerweise einen klaren Konsens darüber haben, ob ein bestimmtes Problem natürlich ist oder nicht. Vielleicht werde ich eine separate Frage zu diesem Thema stellen, um herauszufinden, wie andere es sehen.

Andras Farago

Antworten:

Ich denke, das Clique-Cover-Problem, das fragt, ob es eine Aufteilung der Vertices in Sets gibt, so dass jedes Set eine Clique auslöst, hat die gewünschten Eigenschaften. $k$ $k$

Es ist klar, dass das Aufnehmen induzierter Untergraphen die Mindestgröße einer solchen Partition nicht erhöhen kann. Auf der anderen Seite müssen Sie, wenn Sie die disjunkte Vereinigung von zwei Graphen nehmen, die Vereinigung der Partition in Cliquen von jedem nehmen.

Vinicius dos Santos
quelle

In ähnlicher Weise funktionieren Scheitelpunktabdeckung / dominierende Menge von Größen höchstens

ähnlich.

k

$k$

Aber beide Probleme, die Sie erwähnt haben, sind Polynome für festes

, richtig? Ich denke, wenn Sie

zwingen , Teil der Eingabe zu sein, dann ist es keine genau definierte Eigenschaft im Sinne der gestellten Frage mehr.

k

$k$

k

$k$

Vinicius dos Santos

Das

in der Antwort angegebene Eigenschaft

clique cover ist nicht

. Ein Graph kann eine

Partition in Cliquen haben, aber ein Teilgraph davon erbt diese Eigenschaft möglicherweise nicht. Dies gilt sowohl für die Konstante als auch für die Variable

k

$k$

h e r e d i t a r y

$hereditary$

k

$k$

k

$k$

Andras Farago

Dies kann leicht gelöst werden, indem leere Partitionen zugelassen werden (wenn das ursprüngliche Problem dies nicht zulässt, ziehen Sie einfach diese geänderte Version in Betracht). Anstelle von "Cliquendeckel der Größe

" gilt "der Größe höchstens

k

$k$

k

$k$

Vinicius dos Santos

Ja, ich denke, mit dieser Änderung ist es jetzt eine richtige Antwort! Wenn wir

festlegen , ist die Eigenschaft äquivalent zu " Ist das Komplement von G 3 färbbar?" (was bedeutet, dass das Komplement durch höchstens 3 Farben färbbar ist). Dies ist durch die bekannte NP-Vollständigkeit der graphischen 3-Färbbarkeit erblich und tatsächlich NP-vollständig. Die Eigenschaft ist auch nicht additiv, da, wenn sowohl

als auch

ihre Komplemente 3-färbbar haben, immer noch das Komplement ihrer disjunkten Vereinigung nicht 3-färbbar bleiben kann (es können bis zu 6 Farben erforderlich sein).

k = 3

$k=3$

G_{1}

$G_1$

G_{2}

$G_2$

Andras Farago

Betrachten Sie dieses Problem

$G$ $P$ $Q$

Es bleibt NP vollständig, auch wenn die Eigenschaften erblich sind.

Es ist klar, dass eine Lösung des obigen Problems für einen Graphen auch eine Lösung für die induzierten Teilgraphen liefert. Aber nach der Vereinigung von Graphen der gleichen Familie wie G könnte diese Lösung nicht gelöst werden.

Zum Beispiel ist das Partitionieren von allgemeinen Graphen in disjunkte Einheitsintervallgraphen NP vollständig, aber nach Vereinigung aller möglichen Kanten (Vervollständigung des Graphen) wird das Problem trivial gelöst.

Dibyayan
quelle

Bitte beachten Sie, dass die Frage nach einer Eigenschaft sucht, die nicht additiv ist. In Ihrem Beispiel scheint nichts zu garantieren, dass es zwei Graphen geben muss, die beide die Eigenschaft haben, aber ihre disjunkte Vereinigung nicht.

Andras Farago

Definieren Sie die Zyklusüberdeckungszahl eines Graphen als die minimale Anzahl von Zyklen so dass (i) jedes $G = (V,E)$ $C_1,\ldots,C_m$ $C_i$ $V$ $E$ $C_i$

(1) für $k \geq 3$ $G$ $k$

$k = 2$

Wenn (1) wahr ist, sollte es Ihre Frage beantworten, da es eine Eigenschaft gibt, die erblich, aber eindeutig nicht additiv ist.

(ANMERKUNG HINZUGEFÜGT: Die Vermutung (2) unterscheidet sich von der "Doppelzyklus-Deckungsvermutung" von Szekeres und Seymour, trotz der Homonymität).

Super 8
quelle

Diese Eigenschaft ist nicht erblich. Das Entfernen eines Scheitelpunkts kann die erforderliche Anzahl von Zyklen zum Abdecken aller Kanten erhöhen, da der entfernte Scheitelpunkt möglicherweise einen Zyklus eliminiert, der zum Abdecken vieler Kanten verwendet wurde. Das einfachste Beispiel ist, wenn der gesamte Graph nur ein Zyklus ist. Das Entfernen eines Scheitelpunkts macht jede Fahrradabdeckung unmöglich, da keine Fahrräder übrig bleiben.

Andras Farago

G

$G$

G

$G$

v

$v$

v

$v$

k

$k$