Eine Frage zu linearen Erweiterungen von Teilaufträgen

12

Wenn Sie eine Sammlung von Teilaufträgen erhalten, werden Sie anhand der topologischen Sortierung darüber informiert, ob eine Erweiterung der Sammlung auf einen Gesamtauftrag vorliegt (eine Erweiterung ist in diesem Fall ein Gesamtauftrag, der mit jedem der Teilaufträge übereinstimmt).

Ich bin auf eine Variante gestoßen:

Fix einen Satz . Sie erhalten Sequenzen von Elementen, die ohne Wiederholung aus gezogen wurden (die Sequenzen haben eine Länge zwischen 1 und ).V V | V |σ1,σkV|V|

Gibt es eine Möglichkeit, die Ausrichtungen für jede der Sequenzen (entweder vorwärts oder rückwärts) festzulegen, sodass die resultierende Sammlung von Ketten (als Teilreihenfolge betrachtet) eine Erweiterung zulässt?

Ist dieses Problem bekannt?

Hinweis: Die Ausrichtung wird für eine gesamte Sequenz ausgewählt. Wenn die Sequenz , können Sie sie entweder oder auf , aber Sie können nichts anderes tun.5 - 4 - 2 - 11-2-4-55-4-2-1

Suresh Venkat
quelle
1
Wenn jede der Sequenzen die Länge hat, kann man sich jede Sequenz als ungerichtete Kante vorstellen und wir fragen, ob ein ungerichteter Graph als DAG ausgerichtet werden kann - wenn es keinen Zyklus gibt. Ein gieriger Algorithmus funktioniert aber auch. Beginnen Sie mit einer Kante und richten Sie sie willkürlich aus. Fahren Sie so lange wie möglich fort. Wenn Sie stecken bleiben, wissen Sie, dass dies nicht möglich ist. Hast du das für deine Variante probiert? Scheint, als könnte es funktionieren. 2
Chandra Chekuri
2
Er, jeder ungerichtete Graph kann als DAG orientiert werden. Wählen Sie einfach eine Reihenfolge der Eckpunkte und verwenden Sie diese Reihenfolge, um die Kanten auszurichten.
David Eppstein
Sie haben natürlich Recht, ich denke nicht klar.
Chandra Chekuri
In meiner Variation hat jede Subsequenz genau die Länge 4, also setzt Yurys Antwort ein. Meine einzige Hoffnung an dieser Stelle ist, dass die Subsequenzen eine sehr spezielle Struktur haben und miteinander in Beziehung stehen. Vielleicht hilft etwas, das für das Problem spezifisch ist. Aber es gibt keinen allgemeinen Hammer.
Suresh Venkat

Antworten:

14

Wenn jede Sequenz die Länge 3 hat, ist das Problem als Betweenness bekannt . Sogar das Betweenness-Problem ist NP-schwer. In diesem Problem erhalten wir eine Menge von Eckpunkten und eine Menge von Bedingungen der Form liegt zwischen v unduv . Unser Ziel ist es, alle Eckpunkte zu ordnen, um die Anzahl der erfüllten Bedingungen zu maximieren. Opantry [1] hat bewiesen, dass die Entscheidungsversion dieses Problems NP-schwer ist. Chor und Sudan [2] haben bewiesen, dass es SNP-schwer ist.w

Der bekannteste Näherungsalgorithmus für das Problem von Chor und Sudan erfüllt die Hälfte aller Bedingungen, wenn die Instanz vollständig erfüllbar ist.

[1] J. Opantry. Total Ordering Problem, SIAM Journal on Computing , 8 (1): 111–114, Februar 1979.

[2] B. Chor und M. Sudan. Eine geometrische Herangehensweise an die Zusammengehörigkeit , SIAM Journal on Discrete Mathematics, 11 (4): 511-523, Nov. 1998.

Änderungen: Es wurde klargestellt, dass die Entscheidungsversion des Problems NP-schwer ist.

Yury
quelle
Ja, bedeutet das, dass das Entscheidungsproblem, ob alle Bedingungen erfüllt werden können, auch schwierig ist?
Chandra Chekuri
1
Ja, das Entscheidungsproblem ist NP-schwer. Darüber hinaus ist es für einige NP-schwer, auch nur einen Bruchteil von 1 - ϵ aller Einschränkungen zu erfüllen (dh das entsprechende Versprechen ist NP-schwer). ϵ>01-ϵ
Yury
4
Wenn die Instanz nicht vollständig erfüllbar ist das Problem sehr hart: Natürlich können Sie erfüllen aller Beschränkungen , die durch eine zufällige Reihenfolge nehmen; aber es ist UGC-schwer zu erfüllen 1 / 3 + ε aller Einschränkungen , wenn O P T = 1 - ε für jede Konstante ε > 0 [Charikar, Guruswami, Manokaran - CCC 2009]. 1/31/3+εÖPT=1-εε>0
Yury
meine frage könnte blöd sein. aber erstreckt sich die 3-reguläre ( für alle i ) Härte natürlich auf 4-regulär? |σich|=3ich
Yixin Cao
1
Ja, hier ist eine Ermäßigung. Betrachten Sie eine 3-reguläre InstanzichyichσichσichyichσichichV{yich}{σich}ichichichyichVVσich{yich}