Komplexität topologischer Art mit eingeschränkten Positionen

15

Als Eingabe wird mir ein DAG G von Eckpunkten gegeben, wobei jeder Eckpunkt zusätzlich mit einigen .nxS(x){1,,n}

Eine topologische Art von ist eine Bijektion von den Eckpunkten von nach so dass für alle , , wenn es einen Pfad von nach in dann . Ich möchte entscheiden, ob es eine topologische Art von , die für alle , .f G { 1 , ... , n } x y x y G f ( x ) f ( y ) G x f ( x ) S ( x )GfG{1,,n}xyxyGf(x)f(y)Gxf(x)S(x)

Wie komplex ist dieses Entscheidungsproblem?

[Anmerkungen: Dies ist eindeutig in NP. Wenn Sie sich das Diagramm der zulässigen Scheitelpunkt- / Positionspaare mit ungerichteten Kanten zwischen Paaren ansehen, die in Konflikt stehen, weil sie die Reihenfolge verletzen, erhalten Sie ein Diagramm mit disjunkten Cliquen, in denen Sie höchstens ein Paar pro Clique und höchstens ein Paar pro Clique auswählen möchten Position und höchstens ein Paar pro Scheitelpunkt - es scheint im Zusammenhang mit der dreidimensionalen Übereinstimmung zu stehen, aber ich kann nicht sehen, ob die zusätzliche Struktur dieses spezifischen Problems immer noch schwierig ist.]

a3nm
quelle

Antworten:

9

Ich denke, dieses Problem ist NP-schwer. Ich versuche eine Reduktion von MinSAT zu skizzieren. Im MinSAT-Problem erhalten wir einen CNF und unser Ziel ist es, die Anzahl der erfüllten Klauseln zu minimieren. Dieses Problem ist NP-schwer, siehe z. B. http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Teilen Sie die Eckpunkte in zwei Gruppen ein - einige stellen Literale dar, die anderen Klauseln, also wobei v die Anzahl der Variablen des CNF (normalerweise mit n bezeichnet ) und c die Anzahl der Klauseln ist. Richten Sie eine Kante von jedem Literal-Vertex zu dem Klausel-Vertex, an dem sie auftritt. Definiere S für einen Literal-Vertex, der x i als { i , i + v + k } darstellt (wobei k ein beliebiger Parameter ist), also entweder f ( x i )n=2v+cvncSxich{ich,ich+v+k}k und f ( ˉ x i ) = i + v + k oder f ( ˉ x i ) = i und f ( x i ) = i + v + k . Für jeden Vertix sei S = { v + 1 , , v + k , 2 v + k + 1 , f(xich)=ichf(x¯ich)=ich+v+kf(x¯ich)=ichf(xich)=ich+v+k , also sind k der Klauselknoten `` small ''.S={v+1,,v+k,2v+k+1,,n}k

Jetzt hat der CNF eine Zuweisung, bei der mindestens Klauseln genau dann falsch sind, wenn Ihr Problem für die obige Instanz gelöst werden kann. Das MinSAT-Problem besteht genau darin, zu testen, ob eine CNF-Formel φ eine Zuweisung hat, die mindestens k- Klauseln falsch macht. Dies zeigt also, dass Ihr Problem NP-schwer ist.kφk

Um Ihnen das Verständnis dieser Reduktion zu erleichtern, ist hier die Intuition: Kleine Bezeichnungen ( ) entsprechen dem Wahrheitswert False und große Bezeichnungen ( v + k + 1 , , 2 v + k ) entsprechen Wahr. Die Einschränkungen für literal-Eckpunkte sicherzustellen , dass jedes x i entweder wahr oder falsch ist und dass ¯ x i1,2,,v+kv+k+1,,2v+kxixi¯hat den entgegengesetzten Wahrheitswert. Die Kanten stellen sicher, dass, wenn ein Literal True ist, alle Klauselscheitelpunkte, die es enthalten, ebenfalls True zugewiesen werden. (Wenn im Gegensatz dazu allen Literalen in einer Klausel False zugewiesen wird, kann der Klauselscheitelpunkt in dieser Diagrammstruktur entweder False oder True zugewiesen werden.) Schließlich wird durch die Auswahl von sichergestellt, dass k der Klauselscheitelpunkte False und zugewiesen wird c - k von ihnen sind True zugeordnet. Wenn es also eine gültige topologische Sortierung dieses Graphen gibt, dann gibt es eine Zuordnung zu den Variablen, die mindestens k der Klauseln von φ ergibtkkckkφfalse (alle Klauselscheitelpunkte, denen False zugewiesen wurde, plus möglicherweise einige derjenigen, denen True zugewiesen wurde). Umgekehrt gibt es, wenn es eine Zuordnung zu den Variablen gibt, die mindestens der Sätze von φ falsch macht, eine gültige topologische Sortierung dieses Graphen (wir füllen die Bezeichnungen für die Literalscheitelpunkte auf offensichtliche Weise aus; und für Für jeden Satz von φ , der wahr ist, geben wir seinem entsprechenden Satz-Eckpunkt eine Bezeichnung, die wahr entspricht (die anderen Satz-Eckpunkte können Bezeichnungen erhalten, die einem beliebigen Wahrheitswert entsprechen).kφφ

domotorp
quelle
Danke für deine Antwort! Ich versuche deine Skizze zu verstehen. Würde es Ihnen etwas ausmachen zu erklären, was ist? k
a3nm
1
@ a3nm: k ist ein Parameter, der für den MinSAT-Eingang angegeben wird.
Domotorp
1
@Marzio: SAT entspricht nicht MinSAT mit Wie im letzteren Fall müssten alle Klauseln falsch sein. Ihr ϕ hat keine falsche Zuweisung für alle Klauseln. Das beweist natürlich nicht, dass meine Reduzierung korrekt ist ...k=|c|ϕ
domotorp
Dies ist eine wunderschöne Reduktion! @ a3nm, ich habe eine Bearbeitung der Antwort vorgeschlagen, um die elegante Reduktion von domotorp genauer zu erläutern. Wenn es genehmigt wird, wird es Ihnen hoffentlich helfen, die Ideen klarer zu verstehen.
DW
@domotorp: Sie haben recht, ich habe völlig verpasst, was MinSAT ist. Schöne Ermäßigung !!!
Marzio De Biasi
2

Beachten Sie: Wenn Sie das Problem lösen, indem Sie zulassen, dass willkürlich ist (nicht unbedingt bijektiv), wird es polynomisch. Der Algorithmus funktioniert ähnlich wie bei der topologischen Sortierung: Sie nummerieren die Scheitelpunkte nacheinander und behalten dabei die Menge U der nicht nummerierten Scheitelpunkte bei, deren Nachbarn nummeriert wurden. Wann immer möglich, wählen Sie einen Eckpunkt x U und nummerieren ihn mit dem kleinsten Element von S ( x ), das größer ist als die Anzahl seiner Nachbarn. Es ist nicht schwer zu erkennen, dass eine Instanz ( G , S ) eine Lösung hat, wenn der vorherige Algorithmus auf ( G , S ) ausgeführt wird.fUxUS(x)(G,S) endet mit allen nummerierten Eckpunkten.(G,S)

Super0
quelle
Angemessen, diese Entspannung bedeutet, dass eine gierige Heuristik funktioniert, und das gilt auch für den Fall, dass nicht die Anzahl der Eckpunkte ist, sondern ein beliebiger Wert. Sind wir uns einig, dass im letzteren Fall, in dem Injektivität und Surjektivität nicht mehr gleichwertig sind, Sie beide (und nicht nur einen) entspannen müssen, damit die gierige Heuristik funktioniert? n
Am
2

|S(x)|2x

vx,ichxichichS(x)x,yxyichS(x)jS(y)ich>j¬vx,ich¬vy,jx,yxyichS(x)ichS(y)¬vx,ich¬vy,ichxS(x)={ich,j}vx,ichvx,j|S(x)|2x

Mir ist klar, dass diese Beobachtung Ihnen in Ihrer speziellen Situation nicht helfen wird. Das tut mir leid.

DW
quelle