Feedback -Bogen eingestellt

Partition eines gerichteten Diagramms in einen minimalen Rückkopplungsbogensatz (rote gestrichelte Kanten) und einen maximalen acyclischen Untergraphen (blaue feste Kanten)

Im Graphentheorie und Graphalgorithmen, a Feedback -Bogen eingestellt oder Feedback Edge Set in einem gerichteter Graph ist eine Teilmenge der Kanten des Graphen, die mindestens einen Rand aus jedem Zyklus im Diagramm enthält. Das Entfernen dieser Kanten aus dem Diagramm bricht alle Zyklen und erzeugt a Regie acyclische Graphen, ein Acyclischer Untergraph der angegebenen Grafik. Der Feedback -Lichtbogen mit den wenigsten möglichen Kanten ist die Mindestfeedback -Lichtbogen gesetzt und seine Entfernung lässt die Maximaler acyclischer Untergraphen; gewichtete Versionen davon Optimierungsprobleme werden auch verwendet. Wenn ein Feedback -Bogensatz minimal ist, was bedeutet, dass das Entfernen einer Kante eine Teilmenge erzeugt, die kein Feedback -Bogensatz ist, hat es eine zusätzliche Eigenschaft: Alle seine Kanten umzukehren, anstatt sie zu entfernen, erzeugt ein gerichtetes acyclisches Diagramm.

Feedback -Lichtbogensätze haben Anwendungen in der Schaltungsanalyse. Chemieingenieurwesen, Sackgasse Auflösung, Rangstimmig, Ranking Wettbewerber bei Sportveranstaltungen, Mathematische Psychologie, Ethologie, und Grafikzeichnung. Finden minimaler Feedback -Lichtbogensätze und maximalen acyclischen Untergraphen sind Np-harte; Es kann genau in gelöst werden Exponentialzeit, oder in Fix-Parameter-Traktable Zeit. Im PolynomzeitDer minimale Rückkopplungsbogensatz kann innerhalb eines Polylogarithmic angenähert werden Annäherungsverhältnisund maximale acyclische Subgraphen können innerhalb eines konstanten Faktors angenähert werden. Beide sind schwer näher als ein konstanter Faktor, ein Unangemessenheit Ergebnis, das unter dem gestärkt werden kann Einzigartige Spiele vermutlich. Zum TurnierdiagrammeDer minimale Feedback -Lichtbogensatz kann genauer angenähert werden und für Planare Graphen Beide Probleme können genau in der Polynomzeit gelöst werden.

Ein eng verwandtes Problem, die, die Feedback -Scheitelpunkt -Set, ist ein Satz von Scheitelpunkten, die mindestens einen Scheitelpunkt aus jedem Zyklus in einem gerichteten oder ungerichteten Diagramm enthalten. Im ungerichtete Grafiken, das Bäume überspannen sind die größten acyclischen Untergraphen, und die Anzahl der Kanten, die bei der Bildung eines Spannungsbaums entfernt wurden Schaltungsrang.

Anwendungen

Die Punktzahlen von Herren -Strandvolleyball bei den Olympischen Spielen 2016, Pool F und das Ranking von Minimum-Upset für diese Ergebnisse. Die Pfeile werden vom Verlierer an den Gewinner jedes Spiels gerichtet und blau gefärbt, wenn das Ergebnis mit der Rangliste übereinstimmt, und rot für eine Überraschung, ein Ergebnis, das mit der Rangliste unvereinbar ist. Mit dieser Rangliste ist nur ein Match eine Überraschung, in der die USA Qat besiegten. Das tatsächliche Ranking, das bei den Olympischen Spielen verwendet wurde, unterschied sich, indem ESP vor QAT im Set -Verhältnis platziert wurde, was dazu führte, dass ihr Match als eine weitere Überraschung eingestuft wurde.^[1]

Mehrere Probleme bei der Suche nach Rankings oder Bestellungen können gelöst werden, indem ein Feedback -Lichtbogen auf a gesucht wird Turnierdiagramm, ein gerichtetes Diagramm mit einer Kante zwischen jedem Eckpaar. Die Umkehrung der Kanten des Feedback -Bogensatzes erzeugt a Regie acyclische Graphen deren einzigartig Topologische Ordnung Kann als gewünschtes Ranking verwendet werden. Die Anwendungen dieser Methode umfassen Folgendes:

• In Sportwettbewerben mit Round-Robin-SpielDie Ergebnisse jedes Spiels können aufgenommen werden, indem ein Vorteil vom Verlierer an den Gewinner jedes Spiels geleitet wird. Das Finden eines minimalen Feedback -Bogens, der im resultierenden Diagramm eingestellt, seine Kanten umgekehrt und die topologische Ordnung umgekehrt ist, erzeugt ein Ranking für alle Konkurrenten. Unter all den verschiedenen Möglichkeiten für die Auswahl eines Rankings minimiert es die Gesamtzahl der Upsets, bei denen ein Konkurrent mit niedrigerem Rang einen höheren Konkurrenten übertraf.^[2][3][4] Viele Sportarten verwenden einfachere Methoden für Gruppenturnierranking -Systeme basierend auf Punkten für jedes Spiel;^[5] Diese Methoden können eine konstante Annäherung an das Ranking von Minimum-Upset bieten.^[6]
• Im Primatologie und allgemeiner in Ethologie, Dominanzhierarchien werden häufig durch die Suche nach einer Ordnung mit den wenigsten Umkehrungen im beobachteten Dominanzverhalten bestimmt, eine andere Form des Mindestproblems für Rückkopplungsbogen.^[7][8][9]
• Im Mathematische PsychologieEs ist von Interesse, die Rangfolge der Probanden an Objektsätzen gemäß einem bestimmten Kriterium zu bestimmen, wie z. B. ihre Präferenz oder ihre Wahrnehmung der Größe, basierend auf paarweisen Vergleichen zwischen allen Objektpaaren. Der Mindestrang, der in einem Turnierdiagramm eingestellt ist, bietet ein Ranking, das mit so wenigen paarweisen Ergebnissen wie möglich nicht einverstanden ist.^[2][10] Alternativ, wenn diese Vergleiche für jede paarweise Ordnung zu unabhängigen Wahrscheinlichkeiten führen, dann die dann die Maximum-Likelihood-Schätzung des Gesamtrangs kann erhalten werden, indem diese Wahrscheinlichkeiten in umwandeln Log-Likelihoods und Finden eines Mindestgewichts-Feedback-Bogens im resultierenden Turnier.^[2][3]
• Die gleiche Bestellung für maximale Likelihood kann verwendet werden Seriationdas Problem in Statistiken und Explorationsdatenanalyse Elemente in eine lineare Reihenfolge zu ordnen, in Fällen, in denen Daten verfügbar sind, die paarweise Vergleiche zwischen den Elementen bieten.^[3][11][12]
• Im Rangstimmig, das Kemeny -Young -Methode kann als eine Bestellung bezeichnet werden, die die Summe über Paare von Kandidaten der Anzahl der Wähler minimiert, die die entgegengesetzte Ordnung für dieses Paar bevorzugen.^[13] Dies kann als Mindestgewichts-Feedback-Bogen-Set-Problem formuliert und gelöst werden, bei dem die Scheitelpunkte Kandidaten darstellen, die Kanten angewiesen werden, den Gewinner jedes Kopf-an-Kopf-Wettbewerbs darzustellen, und die Kosten jeder Kante stellen die Anzahl der Wähler dar Wer würde unglücklich gemacht werden, indem er dem Kopf-an-Kopf-Verlierer höher rangiert.^[14]

Eine weitere frühe Anwendung von Feedback -Bogensätzen betrifft die Gestaltung von Sequentielle Logik Schaltungen, in denen sich Signale in Zyklen durch den Schaltkreis ausbreiten können, anstatt immer von Eingängen zu Ausgängen zu entwickeln. In solchen Schaltungen charakterisiert ein Mindestrückkopplungsbogensatz die Anzahl der Punkte, an denen eine Verstärkung erforderlich ist, damit sich die Signale ohne Informationsverlust vermehren können.^[15] Im Synchronschaltungen Synchronisation aus asynchronen Komponenten kann durch Platzieren von Taktentoren an den Kanten eines Rückkopplungsbogensatzes erreicht werden.^[16] Zusätzlich reduziert das Schneiden einer Schaltung auf einem Feedback ein Satz die verbleibende Schaltung auf KombinationslogikDie Vereinfachung der Analyse und der Größe des Feedback -Lichtbogensatzes steuert, wie viel zusätzliche Analyse erforderlich ist, um das Verhalten der Schaltung über den Schnitt zu verstehen.^[15] In ähnlicher Weise in Prozessablaufblatt in Chemieingenieurwesen, Brechen von Rändern von a Prozessflussdiagramm Bei einem Feedback -Lichtbogen kann der Rest des Prozesses aufgrund seiner Akyklizität systematisch analysiert werden, und ermöglicht das Erraten oder Versuch aller Möglichkeiten für die Werte an diesen Kanten. In dieser Anwendung wird die Idee, Kanten auf diese Weise zu brechen, als "Tränen" bezeichnet.^[17]

Im Layered Graph DrawingDie Scheitelpunkte eines bestimmten gerichteten Diagramms werden in eine geordnete Abfolge von Teilmengen (die Schichten der Zeichnung) unterteilt, und jede Teilmenge wird entlang einer horizontalen Linie dieser Zeichnung platziert, wobei die Kanten zwischen diesen Schichten nach oben und nach unten fallen. In dieser Art der Zeichnung ist es wünschenswert, dass die meisten oder alle Kanten konsistent nach unten ausgerichtet sind, anstatt nach oben und unten zu mischen, damit die Erreichbarkeitsbeziehungen in der Zeichnung visuell offensichtlicher sind. Dies wird erreicht, indem ein minimales oder minimales Rückkopplungsbogensatz gefunden, die Kanten in diesem Satz umgekehrt und dann die Partition in Schichten auf eine Weise ausgewählt werden, die mit einer topologischen Reihenfolge des resultierenden acyclischen Graphen übereinstimmt.^[18][19] Feedback -Lichtbogensätze wurden auch für ein anderes Teilproblem der Schicht -Graphenzeichnung verwendet, die Reihenfolge von Scheitelpunkten in aufeinanderfolgenden Schichtenpaaren.^[20]

Im Sackgasse Auflösung in BetriebssystemeDas Problem, die geringste Anzahl von Abhängigkeiten zum Brechen eines Deadlocks zu beseitigen, kann als eine der Mindestrückkopplungsbogenmodelle modelliert werden.^[21][22] Aufgrund der rechnerischen Schwierigkeit, diesen Satz zu finden, und der Notwendigkeit der Geschwindigkeit innerhalb von Betriebssystemkomponenten, werden in dieser Anwendung häufig Heuristiken und nicht genaue Algorithmen verwendet.^[22]

Algorithmen

Äquivalenzen

Der minimale Rückkopplungsbogensatz und der maximale acyclische Subgraphen sind für die Zwecke der exakten Optimierung äquivalent, da einer die Komplement -Set des anderen. Für die parametrisierte Komplexität und Näherung unterscheiden sie sich jedoch, da die für diese Arten von Algorithmen verwendete Analyse jedoch von der Größe der Lösung und nicht nur von der Größe des Eingangsdiagramms und des minimalen Rückkopplungsbogensatzes und der maximalen acyclischen Subgraphen abhängt Größen voneinander.^[23]

Ein Feedback -Bogensatz eines bestimmten Diagramms ${\ displayStyle g}$ ist dasselbe wie a Feedback -Scheitelpunkt -Set von einem gerichteten Liniendiagramm von ${\ displayStyle g}$. Hier wird ein Feedback -Scheitelpunktsatz analog zu einem Rückkopplungsbogensatz definiert, als Teilmenge der Scheitelpunkte des Graphen, dessen Löschung alle Zyklen beseitigen würde. Die Liniengrafik eines gerichteten Diagramms ${\ displayStyle g}$ hat einen Scheitelpunkt für jede Kante von ${\ displayStyle g}$, und eine Kante für jeden Zweikantenweg in ${\ displayStyle g}$. In der anderen Richtung der minimale Rückkopplungsscheibensatz eines bestimmten Diagramms ${\ displayStyle g}$ kann von der Lösung zu einem minimalen Feedback -Bogen -Set -Problem in einem Diagramm erhalten werden, das durch Spalten jeder Scheitelpunkt von erhalten wird ${\ displayStyle g}$ in zwei Eckpunkte, eine für eingehende Kanten und eine für ausgehende Kanten. Diese Transformationen ermöglichen es genaue Algorithmen für Feedback -Bogensätze und für Rückkopplungsscheiben -Vertex -Sets, die mit einer geeigneten Übersetzung ihrer Komplexitätsgrenzen ineinander umgewandelt werden. Diese Transformation bewahrt jedoch keine Annäherungsqualität für das maximale acyclische Subgraph -Problem bei.^[21][24]

Eine gerichtete Grafik mit drei stark verbundene Komponenten, das rechte davon kann beim Artikulationsscheitelpunkt aufgeteilt werden ${\ displayStyle d}$ in zwei bikonbedingte Komponenten, jeweils ein Zyklus von zwei Eckpunkten. Das Feedback -ARC -Set -Problem kann in jeder stark verbundenen Komponente und in jeder zweifleischigen Komponente einer stark verbundenen Komponente getrennt gelöst werden.

Sowohl in genauen als auch in ungefähren Lösungen für das Feedback -Bogen -Set -Problem reicht es aus, jeweils getrennt zu lösen stark verbundene Komponente der angegebenen Grafik und um diese stark verbundenen Komponenten noch weiter zu ihrer zu brechen bikonbedingte Komponenten Indem Sie sie bei Artikulationsscheitelpunkten aufspalten. Die Wahl der Lösung in einem dieser Teilprobleme betrifft die anderen nicht, und die Kanten, die in keiner dieser Komponenten erscheinen, sind für die Aufnahme in den Rückkopplungsbogensatz nutzlos.^[25] Wenn eine dieser Komponenten durch Entfernen von zwei Scheitelpunkten in zwei getrennte Untergraphen unterteilt werden kann Triconnected -Komponenten seiner stark verbundenen Komponenten.^[26]

Genau

Eine Möglichkeit, den minimalen Feedback -Arc -Set zu finden, besteht darin, nach einer Bestellung der Eckpunkte zu suchen, so dass so wenige Kanten wie möglich von späteren Scheitelpunkten zu früheren Eckpunkten in der Bestellung gerichtet sind.^[27] Alle suchen Permutationen von einem ${\ displayStyle n}$-Scheitel Graph würde dauern Zeit ${\ displayStyle o (n!)}$, aber a Dynamische Programmierung Methode basierend auf der Held -Karp -Algorithmus kann die optimale Permutation finden in Zeit ${\ displayStyle o (n2^{n})}$, Auch eine exponentielle Menge an Platz verwenden.^[28][29] A Divide-and-Conquer-Algorithmus Dadurch werden alle Partitionen der Eckpunkte in zwei gleiche Teilmengen getestet und in jeder Teilmenge wiederholt Zeit ${\ displayStyle o (4^{n}/{\ sqrt {n}})}$, Verwendung Polynomraum.^[29]

Im Parametrisierte KomplexitätDie Zeit für Algorithmen wird nicht nur in Bezug auf die Größe des Eingangsdiagramms, sondern auch in Bezug auf einen separaten Parameter des Diagramms gemessen. Insbesondere für das Mindestproblem für das Feedback-Lichtbogen ist das sogenannte sogenannte Problem Natürlicher Parameter ist die Größe des minimalen Feedback -Bogensatzes. Auf Grafiken mit ${\ displayStyle n}$ Scheitelpunkte mit natürlicher Weise Parameter ${\ displayStyle K}$, Das Feedback -Bogen -Set -Problem kann in gelöst werden Zeit ${\ displayStyle o (n^{4} 4^{k} k^{3} k!)}$, Indem Sie es in ein äquivalentes Feedback -Scheitelpunkt -Set -Problem umwandeln und einen parametrisierten Rückkopplungs -Scheitelpunkt -Set -Algorithmus anwenden. Weil der Exponent von ${\ displayStyle n}$ In diesem Algorithmus ist das Konstante ${\ displayStyle 4}$, unabhängig von ${\ displayStyle K}$, Dieser Algorithmus soll mit festem Parameter geeignet sein.^[30]

Andere Parameter als der natürliche Parameter wurden ebenfalls untersucht. Ein fixierter Parameter-Traktable-Algorithmus unter Verwendung dynamischer Programmierung kann minimale Rückkopplungsbogensätze in feststellen Zeit ${\ displayStyle o (2^{r} m^{4} \ log m)}$, wo ${\ displayStyle r}$ ist der Schaltungsrang der zugrunde liegenden undirezierten Grafik. Der Schaltungsrang ist ein ungerichtetes Analogon des Rückkopplungsbogensatzes, die minimale Anzahl von Kanten, die von einem Diagramm entfernt werden müssen, um es auf a zu reduzieren Spannungsbaum; Es ist viel einfacher zu berechnen als der minimale Feedback -Lichtbogensatz.^[24] Für Grafiken von Baumbreite ${\ displayStyle t}$, Dynamische Programmierung auf einer Baumabteilung des Diagramms kann den minimalen Rückkopplungsbogen in der Zeitpolynom in der Graphengröße und Exponentials ermitteln in ${\ displayStyle o (t \ log t)}$. Unter dem Exponentialzeithypothese, keine bessere Abhängigkeit von ${\ displayStyle t}$ ist möglich.^[31]

Anstatt die Größe des Feedback -Lichtbogensatzes zu minimieren, haben die Forscher auch untersucht, ob die maximale Anzahl der von jedem Scheitelpunkt entfernt wurden. Diese Variation des Problems kann in gelöst werden lineare Zeit.^[32] Alle minimalen Feedback -Lichtbogensätze können von einem Algorithmus mit aufgeführt werden Polynomverzögerung pro Satz.^[33]

Ungefähr

Der bekannteste Algorithmus zur Polynomzeit-Annäherung für den Feedback-Bogen-Set hat den Nicht-Konstanten Annäherungsverhältnis ${\ displayStyle o (\ log n \ log \ log n)}$. Dies bedeutet, dass die Größe des Feedback -Bogensatzes, den es findet, höchstens diesen Faktor ist als das Optimum.^[21] Die Bestimmung, ob der Rückkopplungsbogensatz einen Annäherungsalgorithmus mit konstantem Verhältnis hat oder ob ein nicht konstantes Verhältnis erforderlich ist, bleibt ein offenes Problem.^[34]

Das maximale acyclische Subgraphenproblem hat einen einfachen Annäherungsalgorithmus, der ein Annäherungsverhältnis erreicht von ${\ displayStyle {\ tfrac {1} {2}}}$:

• Beheben Sie eine willkürliche Bestellung der Eckpunkte
• Partitionieren Sie die Kanten in zwei acyclische Untergraphen, die aus den Kanten bestehen, die konsistent mit der Ordnung gerichtet sind, und das andere, der aus den Kanten besteht, die sich entgegengesetzt gegen die Bestellung richten.
• Geben Sie den größeren der beiden Untergraphen zurück.

Dies kann durch die Verwendung a verbessert werden Gieriger Algorithmus Auswahl der Bestellung. Dieser Algorithmus findet und löscht einen Scheitelpunkt, dessen Anzahl eingehender und ausgehender Kanten so weit wie möglich voneinander entfernt ist, bestellt rekursiv das verbleibende Diagramm und platziert dann den gelöschten Scheitelpunkt an einem Ende der resultierenden Reihenfolge. Für Grafiken mit ${\ displayStyle m}$ Kanten und ${\ displayStyle n}$ Eckpunkte erzeugen einen acyclischen Untergraphen mit ${\ displayStyle m/2+n/6}$ Kanten in linearer Zeit, die ein Annäherungsverhältnis geben von ${\ displaystyle {\ tfrac {1} {2}}+\ omega (n/m)}$.^[35] Ein weiterer, komplizierterer Polynomzeitnäherungsalgorithmus gilt für Diagramme mit maximal Grad ${\ displayStyle \ Delta}$, und findet einen acyclischen Untergraphen mit ${\ displayStyle m/2+\ Omega (m/{\ sqrt {\ delta}})}$ Kanten, die ein Annäherungsverhältnis von dem geben bilden ${\ displaystyle {\ tfrac {1} {2}}+\ omega (1/{\ sqrt {\ delta})}}$.^[36][37] Wann ${\ displayStyle \ Delta = 3}$das Annäherungsverhältnis ${\ displayStyle 8/9}$ Kann erreicht werden.^[38]

Eingeschränkte Eingaben

In gerichteter Planare GraphenDas Feedback -Bogen -Set -Problem ist Dual auf das Problem, eine Reihe von Kanten zusammenzubringen, um das resultierende Diagramm zu erstellen stark verbunden.^[39] Dieses doppelte Problem ist polynomial lösbar,^[40] und daher ist auch das planare Mindestproblem für Feedback -Bogen eingestellt.^[41][40] Es kann gelöst werden Zeit ${\ displayStyle o (n^{5/2} \ log n)}$.^[42] Eine gewichtete Version des Problems kann gelöst werden Zeit ${\ displayStyle o (n^{3})}$,^[39] oder wenn die Gewichte positive Ganzzahlen sind, die höchstens a sind Nummer ${\ displayStyle n}$, in Zeit ${\ displayStyle o (n^{5/2} \ log nn)}$.^[42] Diese planaren Algorithmen können auf die Grafiken erweitert werden, die nicht die haben Dienstprogrammdiagramm ${\ displayStyle k_ {3,3}}$ Als ein Graph Minorunter Verwendung der Tatsache, dass die trikonbezogenen Komponenten dieser Graphen entweder planar oder von begrenzter Größe sind.^[26] Planare Diagramme wurden auch auf eine andere Art und Weise verallgemeinert als eine Klasse von gerichteten Graphen genannt schwach acyclische Digraphen, definiert durch die Integralität von einem bestimmten Polytope, die mit ihren Rückkopplungsbogensätzen verbunden sind. Jedes planar gerichtete Diagramm ist in diesem Sinne schwach acyclisch, und das Feedback -Bogen -Set -Problem kann in der Polynomzeit für alle schwach acyclischen Digraphen gelöst werden.^[43]

Das Reduzierbare Durchflussdiagramme sind eine weitere Klasse von gerichteten Diagrammen, auf denen das Feedback -Bogen -Set -Problem in der Polynomzeit gelöst werden kann. Diese Grafiken beschreiben den Kontrollfluss in strukturierten Programmen für viele Programmiersprachen. Obwohl strukturierte Programme häufig planar gerichtete Durchflussdiagramme produzieren, erfordert die Definition der Reduktibilität nicht, dass das Diagramm planar ist.^[44]

Wenn das Problem mit dem Mindestrückmeldungsbogen eingestellt ist, ist es beschränkt Turniere, es hat ein Polynom-Zeit-Approximationsschema, die sich auf eine gewichtete Version des Problems verallgemeinert.^[45] Ein unterexponentieller parametrisierter Algorithmus für gewichtete Rückkopplungsbogensätze für Turniere ist ebenfalls bekannt.^[14] Das maximale acyclische Subgraph -Problem für dichte Grafiken hat auch ein Polynom-Zeit-Näherungsschema. Die Hauptideen sind zu bewerben randomisierte Rundung zu einem Lineare Programmierrelaxation von dem Problem und zu Derandomisieren der resultierende Algorithmus mit Spaziergängen auf Expander -Diagramme.^[34][46]

Härte

NP-Hardness

Das NP-Completess-Reduktion Von Karp und Lawler, von der Scheitelpunktabdeckung des großen gelben Diagramms bis hin zu minimalem Rückkopplungsbogen, das in der kleinen blauen Graphe eingestellt ist, erweitert jeder gelbe Scheitelpunkt in zwei benachbarte blaue Graphen und jede ungerichtete gelbe Kante in zwei entgegengesetzte gerichtete Kanten. Die minimale Scheitelpunktabdeckung (obere linke und unten rechts gelbe Scheitelpunkte) entspricht dem roten Minimum -Feedback -Lichtbogensatz.

Um die Theorie von anzuwenden NP-Vervollständigung Auf den Mindestrückkopplungsbogensatz muss das Problem von einem Optimierungsproblem geändert werden (wie nur wenige Kanten entfernt werden können, um alle Zyklen zu durchbrechen) in ein Äquivalent Entscheidungsversion, mit einer Ja- oder Nein -Antwort (ist es möglich zu entfernen ${\ displayStyle K}$ Kanten). Somit nimmt die Entscheidungsversion des Feedback -Bogen -Set -Problems sowohl ein gerichtetes Diagramm als auch a ein Nummer ${\ displayStyle K}$. Es wird gefragt, ob alle Zyklen gebrochen werden können, indem höchstens entfernt werden ${\ displayStyle K}$ Kanten oder äquivalent, ob es einen acyclischen Untergraphen mit zumindest gibt ${\ displayStyle | e (g) | -k}$ Kanten. Dieses Problem ist NP-CompleteEs wird erwartet, dass weder IT noch das Optimierungsproblem Polynomzeitalgorithmen aufweisen. Es war einer von Richard M. Karpursprünglicher Satz von 21 NP-Complete-Probleme; Seine NP-Vervollständigung wurde von Karp und bewiesen Eugene Lawler Indem Sie diese Eingaben für ein weiteres hartes Problem zeigen, die Scheitelpunktabdeckungsproblem, könnte in äquivalente Eingaben in das Feedback -Bogen -Festentscheidungsproblem umgewandelt werden ("reduziert") in äquivalente Eingaben.^[47][48]

Einige NP-Complete-Probleme können einfacher werden, wenn ihre Eingaben auf Sonderfälle beschränkt sind. Für den wichtigsten Sonderfall des Feedback-Arc-Set-Problems, der Fall von Turnieren, bleibt das Problem jedoch NP-Vervollständigung.^[49][50]

Unangemessenheit

Die Komplexitätsklasse APX ist definiert als aus Optimierungsproblemen, die einen Polynomzeitnäherungsalgorithmus aufweisen, der eine Konstante erreicht Annäherungsverhältnis. Obwohl solche Annäherungen nicht für das Feedback -Bogen -Set -Problem bekannt sind, ist das Problem bekannt APX-HARDDies bedeutet, dass genaue Annäherungen für sie verwendet werden könnten, um ähnlich genaue Näherungen für alle anderen Probleme in APX zu erreichen. Als Folge seiner Härte, es sei denn P = npEs hat kein Polynomzeitnäherungsverhältnis besser als 1,3606. Dies ist der gleiche Schwellenwert für die für die Scheitelpunktabdeckung bekannt die Ermäßigung Von der Scheitelpunktabdeckung bis zum Feedback -Bogen -Set, das die Qualität der Annäherungen bewahrt.^{[34][51][52][53]} Durch eine andere Reduzierung ist das maximale acyclische Subgraph-Problem ebenfalls APX-HART und NP-HART, um sich innerhalb eines Faktors von 65/66 von Optimal zu entnügen.^[38]

Die Annäherungshärte dieser Probleme wurde ebenfalls unter Unerprobt untersucht Berechnungshärtenannahmen Das sind Standard in der Computerkomplexitätstheorie, aber stärker als P ≠ NP. Wenn die Einzigartige Spiele vermutlich Ist wahr, dann ist das Mindestrückkopplungsbogen -Set -Problem in der Polynomzeit bis zu einem konstanten Faktor schwer annähern von ${\ displaystyle {\ tfrac {1} {2}}+\ varepsilon}$, zum jeder ${\ displayStyle \ varepsilon> 0}$.^[54] Jenseits der Polynomzeit für Annäherungsalgorithmen, wenn die Exponentialzeithypothese ist wahr, dann für jeden ${\ displayStyle \ varepsilon> 0}$ Der minimale Rückkopplungsbogensatz hat keine Annäherung innerhalb eines Faktors ${\ displaystyle {\ tfrac {7} {6}}-\ varepsilon}$ Das kann in der unterenxponentiellen Zeit berechnet werden ${\ displayStyle o (2^{n^{1- \ varepsilon}})}$.^[55]

Theorie

In planar gerichteten Diagrammen folgt das Feedback -Bogen -Set -Problem a a Min-Max-Theorem: Die minimale Größe eines Rückkopplungsbogensatzes entspricht der maximalen Anzahl von Kanten-Disjoint-gerichteten Zyklen, die im Diagramm enthalten sind.^[41][56] Dies gilt nicht für einige andere Grafiken; Zum Beispiel zeigt die erste Illustration eine gerichtete Version des nicht planaren Graphen ${\ displayStyle k_ {3,3}}$ bei der die minimale Größe eines Rückkopplungsbogensatzes zwei beträgt, während die maximale Anzahl der gerichteten Zyklen von Kanten-Disjoint nur eins beträgt.

Jedes Turnierdiagramm hat eine Hamiltonianischer Wegund die Hamiltonschen Pfade entsprechen eins zu eins mit minimalen Rückkopplungsbogensätzen, die vom entsprechenden Pfad entschieden werden. Der Hamiltonsche Weg für einen Feedback -Bogen -Set wird durch Umkehr seines Bögen und die Suche nach einer topologischen Reihenfolge des resultierenden acyclischen Turniers gefunden. Jedes aufeinanderfolgende Paar der Bestellung muss von den Feedback -Lichtbogensätzen nicht mehr als Daher gibt diese Ordnung einen Weg durch Bögen des ursprünglichen Turniers, das alle Scheitelpunkte abdeckt. Umgekehrt bildet der Satz von Kanten, die spätere Scheitelpunkte im Pfad zu früheren, einen Feedback -Bogensatz bilden. Es ist minimal, da jede seiner Kanten zu einem Zyklus mit den Hamiltonschen Pfadkanten gehört, die von allen anderen solchen Zyklen disjunkt sind.^[57] In einem Turnier kann es sein, dass der minimale Feedback -Bogen und der maximale acyclische Untergraphen beide nahe der Hälfte der Kanten sind. Genauer ${\ displaystyle {\ tbinom {n} {2}}/2- \ omega (n^{3/2})}$, und einige Turniere erfordern Größe ${\ displayStyle {\ tbinom {n} {2}}/2-o (n^{3/2})}$.^[58] Zum fast alles Turniere, die Größe ist zumindest ${\ displayStyle {\ tbinom {n} {2}}/2-1.73n^{3/2}}$.^[59] Jeder Regie acyclische Graphen ${\ displayStyle d}$ kann als Untergraphen eines größeren Turnierdiagramms so eingebettet werden, dass so ${\ displayStyle d}$ ist der einzigartige Mindestfeedback -Bogensatz des Turniers. Die Größe dieses Turniers wurde als "Umkehrungszahl" definiert von ${\ displayStyle d}$, und unter gerichteten acyclischen Graphen mit der gleichen Anzahl von Eckpunkten ist es am größten, wenn ${\ displayStyle d}$ ist selbst ein (acyclisches) Turnier.^[60][61]

Eine gerichtete Grafik hat eine Euler Tour Wann immer es ist stark verbunden und jeder Scheitelpunkt hat die gleiche Anzahl eingehender und ausgehender Kanten. Für eine solche Grafik mit ${\ displayStyle m}$ Kanten und ${\ displayStyle n}$ Scheitelpunkte, die Größe eines minimalen Feedback -Lichtbogensatzes ist immer mindestens mindestens ${\ displayStyle (m^{2}+mn)/2n^{2}}$. Es gibt unendlich viele von Eulerian gerichtete Diagramme, für die diese gebundene Grenze eng ist.^[62] Wenn eine gerichtete Grafik hat ${\ displayStyle n}$ Scheitelpunkte, mit höchstens drei Kanten pro Scheitelpunkt, hat es dann einen Feedback -Bogensatz von höchstens ${\ displayStyle n/3}$ Kanten und einige Grafiken erfordern so viele. Wenn eine gerichtete Grafik hat ${\ displayStyle m}$ Kanten, mit höchstens vier Kanten pro Scheitelpunkt, hat es dann einen Feedback -Bogensatz von höchstens ${\ displayStyle m/3}$ Kanten und einige Grafiken erfordern so viele.^[63]

Verweise