"Gerichtete" Probleme, die einfacher sind als ihre "ungerichtete" Variante.

28

Ich hielt einen Vortrag über Pfannkuchensortierung und erwähnte Folgendes:

Was mich zum Nachdenken brachte. In gewisser Weise ist "signierte" Sortierung "gerichtet" - Sie können das Zeichen als eine Richtung betrachten (und dies ist in der Tat die Motivation der Evolutionsbiologie). Aber es ist ein einfacheres Problem! Dies ist ungewöhnlich, da allgemein (zumindest in Diagrammen) gerichtete Probleme schwerer (oder zumindest genauso schwer) sind wie ihre ungerichteten Gegenstücke.

Gibt es unter der Annahme einer großzügigen Definition von "gerichtet" Beispiele für gerichtete Probleme, die einfacher sind als ihre ungerichteten Gegenstücke?

ds.algorithms Suresh Venkat
quelle

2

Sie können Horn 3SAT (jede Klausel kann als (A AND B) C dargestellt werden) als gerichtete Klauseln betrachten, da sie als Implikationen angesehen werden können. Hier ist also der gerichtete Fall einfach, während der ungerichtete 3SAT schwierig ist.

\to

$\to$

Mohammad Al-Turkistany

1

Ich habe eine ähnliche Frage für eine Klasse gestellt, die ich unterrichtete (wobei wir LP zur Annäherung der IP-Lösung verwendeten): Gibt es eine Klasse von Problemen, bei denen das Finden einer ganzzahligen Lösung einfacher war als das Finden einer rationellen Lösung

Gopi

17

Das Zählen von Eulerschaltungen für gerichtete Graphen ist in Polynomzeit unter Verwendung des BEST-Theorems möglich , während anscheinend das gleiche Problem für ungerichtete Graphen # P-vollständig ist .

Timothy Sun.
quelle

Alle Antworten sind großartig, aber wenn ich eine akzeptieren muss, dann deshalb, weil die Lücke groß und das Problem sehr sauber ist.

Suresh Venkat

15

Ein interessanter und weniger bekannter Fall ist der folgende. Angenommen, wir haben einen kantengewichteten Graphen und einen Wurzelknoten . Wir wollen den kostenminimalen Subgraphen von so, dass es kantendisjunkte Pfade von zu jedem Knoten im Graphen gibt. Wenn dies das Minimalkosten-Arboreszenzproblem in gerichteten Graphen und in ungerichteten Graphen äquivalent zum MST-Problem. Beide sind in Poly-Time lösbar, obwohl der ungerichtete Fall einfacher ist. Das Problem ist jedoch in gerichteten Graphen für jedes während es in ungerichteten Graphen für NP-hart ist (da es die minimalen Kosten erfasst) $G$ $r$ $G$ $k$ $r$ $k=1$ $k$ $k=2$ Rand-verbundenes Subgraphen-Problem). $2$

Chandra Chekuri
quelle

13

Vielleicht ist dies nicht das beste Beispiel, aber betrachten Sie (gerichtete) Zyklusabdeckung, wo die Aufgabe darin besteht, alle Scheitelpunkte durch vertex-disjunkte (gerichtete) Zyklen abzudecken. Im gerichteten Fall kann dies auf eine zweiteilige Anpassung reduziert und in Polynomzeit gelöst werden. Im ungerichteten Fall kann das Problem auf eine nicht-partielle Übereinstimmung (und umgekehrt) reduziert werden, was ein schwierigeres Problem darstellt, das jedoch immer noch polynomiell lösbar ist.

Daniel Marx
quelle

10

Ein eindrucksvolleres ähnliches Beispiel ist das folgende: Sei

ein gerichteter gewichteter Graph (Gewichte können negativ sein). Mit dem Ford-Bellman-Algorithmus können wir prüfen, ob es in

einen negativen Zyklus gibt . Aber wenn

ungerichtet ist, wird das Problem viel schwieriger (aber immer noch mehrmals lösbar).

G

$G$

G

$G$

G

$G$

Ilyaraz

Dies ist definitiv ein gutes Beispiel, und zwar in Anlehnung an das, woran ich gedacht habe, als ich die Frage gestellt habe.

Suresh Venkat

2

Ich hatte immer den Eindruck, dass "Probleme mit Zyklen" bei gerichteten Graphen einfacher sind. Vielleicht steckt dahinter ein Prinzip, dass 2-zusammenhängende Komponenten "weniger strukturiert" sind als stark zusammenhängende Komponenten ("Probleme mit Zyklen" = solche, die durch Betrachtung der einzelnen Komponenten gelöst werden können).

Diego de Estrada

3

Diego: Wenn ein gerichteter geschlossener Gang durch einen Scheitelpunkt v verläuft, verläuft ein gerichteter Zyklus durch v. Die analoge Aussage gilt nicht für ungerichtete Graphen. So können wir in gerichteten Graphen oft über Spaziergänge statt über Zyklen nachdenken. Spaziergänge sind robuster und weniger graphentheoretisch als Zyklen, was von Vorteil sein könnte. Vielleicht ist dies eine formale Erklärung für Ihren Eindruck.

Daniel Marx

9

Hier ist ein Problem, das, wie ich kürzlich festgestellt habe, in ungerichteten Diagrammen tatsächlich schwieriger aussieht als in gerichteten.

$m\sqrt{n}\log C$ $m$ $n$ $C$ $n^3, mn\log n$

$m\sqrt{n}\log C$ $n^3, mn\log n$

virgi
quelle

aber hier bedeutet "hart" nur in Bezug auf die (polynomiellen) Laufzeiten der Algorithmen, die wir kennen; es könnte natürlich sein, dass uns eine

technik

2

Das ist ein weiteres interessantes Beispiel. Und herzlichen Glückwunsch zu dem erstaunlichen neuen Ergebnis.

Suresh Venkat

1

Danke, Suresh! In einem anderen Punkt habe ich gerade bemerkt, dass Ilyaraz meine Antwort in einem Kommentar zu Daniel Marx 'Antwort hatte ... Entschuldigung für das Duplikat.

Virgi

"Gerichtete" Probleme, die einfacher sind als ihre "ungerichtete" Variante.

Antworten: