Directed NP-harte Probleme auf DAGs

Die Baumbreite misst, wie nah ein Diagramm an einem Baum ist. Auf Graphen mit begrenzter Baumbreite lassen sich mehrere NP-harte Probleme nachvollziehen. Wenn ein Problem bei Bäumen NP-hart bleibt, kann uns die Baumbreite nicht retten. Dies war die Motivation für eine meiner vorherigen Fragen zu NP-harten Problemen an Bäumen.

Es gibt verschiedene gerichtete Versionen der Baumbreite, die messen, wie nahe ein gerichteter Graph an einem gerichteten azyklischen Graphen (DAG) liegt. Was sind gerichtete Probleme, die für DAGs NP-schwer bleiben? Ein gerichtetes Problem nutzt im Wesentlichen die Richtungen der Kanten. Beispielsweise ist der Hamilton-Pfad ein gerichtetes Problem, wohingegen dies bei der Scheitelpunktabdeckung nicht der Fall ist. Eine der Antworten auf meine vorherige Frage gab ein allgemeines Rezept für die Erzeugung von Problemen, die für Bäume hart sind. Gibt es so ein Rezept für DAGs?

Dies zielt nur darauf ab, die erste Frage des Beitrags teilweise zu beantworten:

Was sind gerichtete Probleme, die für DAGs NP-schwer bleiben?

In [1] werden einige natürliche Probleme bei gerichteten Graphen angegeben, die für DAGs NP-hart bleiben. Die Motivation des Papiers ist es, ein "gutes" baumbreitenartiges Maß für Digraphen zu finden. Sie argumentieren, dass der Nachteil vieler Maßnahmen für Digraphen darin besteht, dass sie für DAGs konstant sind, aber viele gerichtete Gegenstücke natürlicher Probleme für DAGs NP-schwer bleiben. Weitere Informationen zu diesem Thema finden Sie auch in [2] und den Referenzen dieser Artikel.

[1] Robert Ganian, Petr Hlinen, Joachim Kneis, Alexander Langer, Jan Obdrzálek und Peter Rossmanith: Über Digraphenbreitenmessungen in der parametrisierten Algorithmik. IWPEC 2009: 185-197. Vollversion

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Gibt es gute Digraphenbreitenmaße? IPEC 2010 erscheint. arXiv

Es ist bekannt, dass verschiedene Routing-Probleme NP-hart sind und sich Polynomfaktoren in DAGs nur schwer annähern lassen. Dazu gehören Probleme wie maximale kantendisjunkte Pfade und Überlastungsminimierung. Weitere Hinweise finden Sie in den Zeitungen von Andrews, Chuzhoy, Khanna, Zhang und anderen.

$\varphi:=\exists C_1 C_2 C_3 [\forall x (C_1 x \lor C_2 x \lor C_3 x) \land \bigwedge_{i=1,2,3}\forall x,y(\neg C_i x \lor \neg C_i y\lor \neg E(x,y))]$$G$$G'$$E(x,y)$$\varphi$$E(x,y)\lor E(y,x)$$G\models\varphi\iff G'\models\varphi'$

Das berühmte OPEN-Problem [8] aus der Liste von Garey und Johnson ist jenseits von P, aber es kann erwiesen werden, dass es NP-C ist. Das Problem liegt bei der DAG. In jeder Runde können Sie höchstens drei Eckpunkte löschen, die keine eingehende Kante haben. Entscheiden Sie, ob alle Eckpunkte der DAG in K Runden gelöscht werden könnten? GEÖFFNET ab den 1970er Jahren.