Komplexität beim Finden eines Graphentrennzeichens mit einer bestimmten Eigenschaft

Gibt es bekannte Ergebnisse zur Komplexität der Suche nach einem Separator (beliebiger Größe), der eine bestimmte Eigenschaft erfüllt?

Ich weiß, dass ein Cliquentrenner leicht zu finden ist (Polynomzeit), und ich weiß auch, dass viele Artikel das Problem betrachten, kleine Trennzeichen oder Trennzeichen zu finden, bei denen verbundene Komponenten mit einer Größe von höchstens einem Bruchteil der Größe des ursprünglichen Diagramms verbleiben. Aber was ist, wenn man einen Separator mit anderen Eigenschaften benötigt, beispielsweise einen kubischen, zweiteiligen oder 2-fach getrennten Separator? Es ist auch einfach, Eigenschaften zu erstellen, die NP-schwer zu entscheiden sind, daher wäre es interessant, zwischen P- und NPC-Fällen zu unterscheiden.

Bearbeiten: Jemand (der kein Benutzer dieser Website ist) hat mir gerade gesagt, dass das Problem polynomisch ist, wenn die Eigenschaft "einen universellen Scheitelpunkt hat" und NP-vollständig ist, wenn die Eigenschaft "eine unabhängige Menge induziert" oder "eine vollständige induziert" zweiteiliger Graph ".

Unser Papier:

http://arxiv.org/abs/1110.4765

zeigt, dass viele dieser Probleme mit festen Parametern nachvollziehbar sind, dh wir können in der Zeit f (k) * O (n + m) entscheiden, ob ein st-Trennzeichen der Größe k existiert. Dies gilt zum Beispiel für das Problem, einen verbundenen st-Separator oder einen Separator zu finden, der eine unabhängige Menge ist, oder einen Separator, der einen zweigeteilten Graphen induziert. Ein bevorstehendes Papier befasst sich mit dem Problem, einen 2-verbundenen St-Separator zu finden.

Es ist auch schwierig zu bestimmen, ob ein Graph einen Schnitt hat, der einen getrennten Graphen induziert , oder einen Graphen mit genau k Komponenten für alle k> = 2 . Auf der anderen Seite ist der verbundene Schnitt einfach (das heißt k = 1).