Probleme, die bei ungewichteten Diagrammen einfach sind, bei gewichteten Diagrammen jedoch schwer

Viele algorithmische Graphenprobleme können sowohl in ungewichteten als auch in gewichteten Graphen in Polynomzeit gelöst werden. Einige Beispiele sind der kürzeste Pfad, der minimale Spannbaum, der längste Pfad (in gerichteten azyklischen Graphen), der maximale Fluss, der minimale Schnitt, der maximale Abgleich, die optimale Arboreszenz, bestimmte dichteste Subgraphenprobleme, maximale disjunkte gerichtete Schnitte, die maximale Clique in bestimmten Graphenklassen, die maximale Unabhängigkeit in bestimmten Grafikklassen festgelegt, verschiedene Probleme mit maximal disjunkten Pfaden usw.

Es gibt jedoch einige (wenn auch wahrscheinlich bedeutend weniger) Probleme, die im ungewichteten Fall in polynomialer Zeit lösbar sind, im gewichteten Fall jedoch hart werden (oder einen offenen Status haben) . Hier sind zwei Beispiele:

1. Angesichts die -eckiges vollständigen Graphen, und eine ganze Zahl , finden eine Spanning -zusammenhängender Subgraphen mit der minimal möglichen Anzahl von Kanten. Dies ist in der Polynomzeit lösbar, wobei ein Satz von F. Harary verwendet wird, der die Struktur der optimalen Graphen angibt. Wenn andererseits die Kanten gewichtet sind, ist das Finden des minimalen Gewichts verbundener übergreifender Teilgraph hart.k ≥ $n$$k\geq 1$k N $k$$k$$NP$

2. Eine kürzlich erschienene Veröffentlichung (Dezember 2012) von S. Chechik, MP Johnson, M. Parter und D. Peleg (siehe http://arxiv.org/pdf/1212.6176v1.pdf ) befasst sich unter anderem mit einem Pfadproblem, das sie haben Mindestbelichtungspfad aufrufen . Hier wird nach einem Pfad zwischen zwei angegebenen Knoten gesucht, sodass die Anzahl der Knoten auf dem Pfad plus der Anzahl der Knoten, die einen Nachbarn auf dem Pfad haben, minimal ist. Sie beweisen, dass dies in begrenzten Gradgraphen für den ungewichteten Fall in Polynomzeit gelöst werden kann, im gewichteten Fall jedoch auch bei Gradgrenze 4 hart wird. (Hinweis: Die Referenz wurde als Antwort auf die Frage Was ist gefunden die Komplexität dieses Pfadproblems? )$NP$

Was sind einige andere interessante Probleme dieser Art, das heißt, wenn der Wechsel zur gewichteten Version einen "Komplexitätssprung" verursacht?

In der Welt der Approximationsalgorithmen gibt es das Problem der kapazitiven Vertexabdeckung. Wenn und ganzzahlige Kapazitäten für jedes das Ziel darin, eine Scheitelabdeckung mit minimaler Größe für wobei die Anzahl der von bedeckten Kanten höchstens beträgt . Dieses Problem hat eine konstante Faktorapproximation im ungewichteten Fall (das heißt, wir möchten die Größe der Scheitelpunktabdeckung minimieren), während es im gewichteten Fall (jeweils) -hart ist (es sei denn, ) Scheitelpunkt hat ein Gewicht und wir wollen das Gewicht der Abdeckung minimieren).c ( v ) v ≤ V G v c ( v ) Ω ( log n ) P = N P w ( v $G=(V,E)$$c(v)$$v \in V$$G$$v$$c(v)$$\Omega(\log n)$$P = NP$$w(v)$

Mein Lieblingsbeispiel ist das Problem der unabhängigen Dominanz (bei gegebenem Graphen und der ganzen Zahl , hat eine inklusionsmaximale unabhängige Menge von höchstens Eckpunkten?). Nach einem guten Ergebnis von Martin Farber ( siehe hier ) ist die ungewichtete Version in Akkorddiagrammen polynomiell lösbar. Gerard Chang beweist, dass die gewichtete Version für Akkordgraphen NP-vollständig ist ( siehe hier ).k G $G$$k$$G$$k$

Das perfekte Übereinstimmungsproblem in zweiteiligen Diagrammen liegt in während das genaue gewichtete perfekte Übereinstimmen des zweiteiligen Diagramms N P -komplett ist .$P$$NP$

$NP$

$W$$W$

Ein weiteres Beispiel für dieses Phänomen ist der Graph Balancing (auch als Min Out-Degree Orientation bezeichnet). In diesem Problem erhalten wir einen ungerichteten kantengewichteten Graphen. Das Ziel ist es, die Kanten so auszurichten, dass der (gewichtete) maximale Out-Degree des resultierenden Digraphen minimiert wird.

Das Problem wird häufig durch ein Planungsszenario motiviert. Stellen Sie sich vor, jeder Scheitelpunkt ist ein Prozessor und jede Kante ist ein Job, der nur auf einem seiner beiden Endpunkte ausgeführt werden darf. Das Gewicht einer Kante ist die Länge des entsprechenden Auftrags und das Ziel ist die Minimierung der Makespan.

Das Problem ist NP-hart und APX-hart, auch wenn alle Gewichte 1 oder 2 sind (siehe Ebenlendr et al. "Graph Balancing: Ein Spezialfall für die Planung nicht verwandter paralleler Maschinen" in SODA 2008). Es ist jedoch in P für ungewichtete Diagramme (siehe Asahiro et al. "Diagrammklassen und die Komplexität der Diagrammorientierung, die den maximal gewichteten Grad minimiert" in CATS 2008).

Vielleicht ist dies nur ein triviales Beispiel, und Sie können es als degenerierten Fall betrachten, aber das erste Beispiel, das mir in den Sinn kam, ist das Problem des Handlungsreisenden (bei dem normalerweise davon ausgegangen wird, dass das Diagramm vollständig ist). Beachten Sie, dass die ungewichtete Version Hamilton-Zyklus ist, was für vollständige Diagramme trivial ist.

Das Finden des Pfads mit minimalen Kosten unter Verzögerungseinschränkung (auch bekannt als das Problem des eingeschränkten kürzesten Pfads) scheint hier zu passen.

Angenommen, Sie haben einen Graphen , eine Verzögerungsfunktion d : V → N + , eine Kostenfunktion c : → N + , eine Zahl D ∈ N + und zwei Eckpunkte s , t ∈ $G=(V,E)$$d:V\to\mathbb {N}^+$$c:\to\mathbb {N}^+$$D\in \mathbb {N}^+$$s,t\in V$ .

Das Problem besteht darin, den Pfad mit den minimalen Kosten , so dass die Verzögerung des Pfads nicht mehr als D beträgt$s-t$$D$ .

$\forall v\in V:d(v) =1$$hop-count$ ), ist das Problem trivial (manchmal als Hausaufgabe in Algo-Grundkursen angegeben).

Wenn das Problem gewichtet ist, wird es zum eingeschränkten kürzesten Pfad , von dem bekannt ist, dass er auch bei DAGs NP-vollständig ist.

Das Problem Local Max Cut mit der FLIP-Umgebung ist in allgemeinen ganzzahligen Diagrammen PLS-vollständig.

AA Schaeffer und M. Yannakakis. (1991). Einfache lokale Suchprobleme, die schwer zu lösen sind. SIAM Journal on Computing, 20 (1): 56-87.

Wenn jedoch das größte Gewicht in der Größe des Diagramms polynomisch ist, konvergieren lokale Verbesserungen des Potentials (Gewicht eines Schnitts) in der Polynomzeit, da jede Verbesserung die Potentialfunktion um mindestens eins und die Potentialfunktion erhöht ist polynomial begrenzt. (Mit allgemeinen Gewichten ist es PSPACE-vollständig, eine Lösung zu finden, die durch lokale Verbesserungen ab einem bestimmten Startschnitt erreichbar ist.)

Ähnliches passiert auch bei anderen "potentiellen Spielen".

In verkauften Graphen ist der reisende Verkäufer offen, aber der Hamilton-Zyklus (die ungewichtete Variante) ist als Polynom bekannt.

Diskussion von beiden zum Projekt der offenen Probleme:

http://cs.smith.edu/~orourke/TOPP/P54.html

Bei 2K_1 ist der maximale Schnitt polynomisch und der gewichtete maximale Schnitt ist NP-vollständig.