Eine Frage zu linearen Erweiterungen von Teilaufträgen

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$ $\sigma_1, \ldots \sigma_k$ $V$ $|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. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Suresh Venkat
quelle

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

$2$

Chandra Chekuri

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:

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 und $u$ $v$ . 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

Ja, das Entscheidungsproblem ist NP-schwer. Darüber hinaus ist es für einige

NP-schwer, auch nur einen Bruchteil von

aller Einschränkungen zu erfüllen (dh das entsprechende Versprechen ist NP-schwer).

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

Yury

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

aller Einschränkungen , wenn

für jede Konstante

[Charikar, Guruswami, Manokaran - CCC 2009].

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

Yury

meine frage könnte blöd sein. aber erstreckt sich die 3-reguläre (

für alle

) Härte natürlich auf 4-regulär?

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

Yixin Cao

Ja, hier ist eine Ermäßigung. Betrachten Sie eine 3-reguläre Instanz

I

${\cal I}$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

σ_{i}^{'}

$\sigma_i'$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

I^{'}

${\cal I}'$

V \cup {y_{i}}

$V \cup\{y_i\}$

{σ_{i}^{'}}

$\{\sigma_i'\}$

I^{'}

${\cal I}'$

I

${\cal I}$

I

${\cal I}$

y_{i}

$y_i$

V

$V$

V

$V$

σ_{i}

$\sigma_i$

{y_{i}}

$\{y_i\}$