Welche Graphprobleme sind

10

Nach den entsprechenden Fragen zur NP-Vollständigkeit (siehe Gewichtsfrage und gerichtete Frage ) habe ich mich gefragt, wie parametrisierte Probleme von diesen Attributen beeinflusst werden.

Welche harten Graphenprobleme sind -Hard in gerichteten Graphen, aber feste Parameter, die in ungerichteten Graphen nachvollziehbar sind? $NP$ $W[1]$

Welche harten Graphprobleme sind -Hard in gewichteten Graphen, aber feste Parameter, die in ungewichteten Graphen nachvollziehbar sind? $NP$ $W[1]$

OK, wir haben also Probleme, die für die gerichtete Version schwieriger werden. Was ist mit Gewichten? Können sie das parametrisierte Problem erschweren?

Es gibt einige Fälle, die nicht genau gleich und nicht bekannt sind. zB ist die Berechnung der Baumbreite in ungerichteten Graphen fpt, aber die Berechnung der gerichteten Baumbreite ist nicht bekannt, wenn fpt ist. In der Arbeit von Johnson et al. gibt es jedoch eine fpt 3-Näherung.

Saeed

2

Oder in einem anderen Fall, wenn wir ein DAG-Breitenspiel in ungerichteten Graphen spielen, erhalten wir eine Baumzerlegung. Die Berechnung der Baumbreite ist FPT, aber die Berechnung der Tag-Breite ist PSPACE-vollständig .

Saeed

9

Das Problem der disjunkten Pfade: Bei gegebenen und Knotenpaaren gibt es knotendisjunkte Pfade, die die gegebenen Paare verbinden. Parametrisiert durch in FPT, wenn von der wegweisenden Arbeit von Robertson und Seymour ungerichtet ist. NP-Hard für wenn gerichtet ist - aus Arbeiten von Fortune, Hopcroft und Wylie (1980). $G$ $k$ $k$ $G$ $k=2$ $G$

Chandra Chekuri
quelle

3

Die Berechnung der Baumbreite und der Baumzerlegung in ungerichteten Graphen ist der Parameter FPT wrt width. Viele Digraphenbreitenmaße (oder das entsprechende Spiel) entsprechen der Baumbreite in ungerichteten Diagrammen. Die genaue Komplexitätsklasse vieler von ihnen ist nicht bekannt, hat aber kürzlich gezeigt, dass die DAG-Breite PSPACE-vollständig ist .

Saeed
quelle

Welche Graphprobleme sind

Antworten: