Une question sur les extensions linéaires des commandes partielles

Si vous recevez une collection d'ordres partiels, le tri topologique vous indiquera s'il existe une extension de la collection à un ordre total (une extension dans ce cas est un ordre total cohérent avec chacun des ordres partiels).

Je suis tombé sur une variation:

Correction d' un ensemble . On vous donne des séquences d'éléments tirés de sans répétition (les séquences sont de longueur comprise entre 1 et ). $V$ $\sigma_1, \ldots \sigma_k$ $V$ $|V|$

Existe-t-il un moyen de fixer les orientations pour chacune des séquences (en avant ou en arrière) afin que la collection résultante de chaînes (considérée comme un ordre partiel) admette une extension?

Ce problème est-il bien connu?

Remarque: L'orientation est choisie pour une séquence entière. Donc, si la séquence est , vous pouvez soit la conserver de cette façon, soit la retourner à , mais vous ne pouvez rien faire d'autre. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Suresh Venkat
la source

Si chacune des séquences est de longueur

alors on peut considérer chaque séquence comme un bord non orienté et nous demandons si un graphe non orienté peut être orienté pour être un DAG - ssi il n'y a pas de cycle. Mais un algorithme gourmand fonctionne également. Commencez par un bord et orientez-le arbitrairement et continuez aussi longtemps que vous le pouvez et si vous êtes coincé, vous savez que ce n'est pas possible. Avez-vous essayé cela pour votre variation? Il semble que cela puisse fonctionner.

2

$2$

Chandra Chekuri

Euh, chaque graphe non orienté peut être orienté pour être un DAG. Choisissez simplement un ordre des sommets et utilisez cet ordre pour orienter les bords.

David Eppstein

Vous avez raison bien sûr, moi je ne pense pas droit.

Chandra Chekuri

Dans ma variation, chaque sous-séquence a une longueur exactement de 4, donc la réponse de Yury entre en jeu. Mon seul espoir à ce stade est que les sous-séquences ont une structure très spéciale et sont liées les unes aux autres, donc peut-être que quelque chose de spécifique au problème aiderait. Mais il n'y a pas de marteau général.

Suresh Venkat

Réponses:

Si chaque séquence a une longueur de 3, le problème est connu sous le nom d' interdépendance . Même le problème de l'interdépendance est difficile à NP. Dans ce problème, on nous donne un ensemble de sommets et un ensemble de contraintes de la forme se situe entre et . Notre objectif est de classer tous les sommets afin de maximiser le nombre de contraintes satisfaites. Opantry [1] a prouvé que la version de décision de ce problème est NP-difficile. Chor et le Soudan [2] ont prouvé qu'il est difficile à SNP. $u$ $v$ $w$

L'algorithme d'approximation le plus connu pour le problème, par Chor et Soudan, satisfait la moitié de toutes les contraintes si l'instance est complètement satisfaisable.

[1] J. Opantry. Total Ordering Problem, SIAM Journal on Computing , 8 (1): 111-114, février 1979.

[2] B. Chor et M. Soudan. Une approche géométrique de l'interdépendance , SIAM Journal on Discrete Mathematics, 11 (4): 511-523, novembre 1998.

Modifications: a précisé que la version de décision du problème est NP-difficile.

Yury
la source

Yury, cela signifie-t-il que le problème de la décision de savoir si toutes les contraintes peuvent être satisfaites est également difficile?

Chandra Chekuri

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

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\}$