Complexité du tri topologique avec des positions contraintes

15

On me donne en entrée un DAG de sommets où chaque sommet est en outre étiqueté avec quelques .n x S ( x ) { 1 , , n }GnxS(x){1,,n}

Une sorte topologique de est une bijection des sommets de vers telle sorte que pour tout , , s'il y a un chemin de à dans alors . Je souhaite décider s'il existe une sorte topologique de telle que pour tout , .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)

Quelle est la complexité de ce problème de décision?

[Notes: Il s'agit clairement de NP. Si vous regardez le graphique des paires vertex / position autorisées, avec des arêtes non dirigées entre les paires qui entrent en conflit parce qu'elles violent l'ordre, vous obtenez un graphique des cliques disjointes où vous voulez choisir au plus une paire par clique, au plus une paire par position et au plus une paire par sommet - cela semble lié à la correspondance en trois dimensions, mais je ne vois pas si c'est encore difficile avec la structure supplémentaire de ce problème spécifique.]

a3nm
la source

Réponses:

9

Je pense que ce problème est NP-difficile. J'essaie d'esquisser une réduction de MinSAT. Dans le problème MinSAT, on nous donne un CNF et notre objectif est de minimiser le nombre de clauses satisfaites. Ce problème est NP-difficile, voir par exemple http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec

Divisez les sommets en deux groupes - certains représenteront des littéraux, les autres clauses, donc où est le nombre de variables du CNF (généralement dénoté par ) et est le nombre de clauses. Dirigez une arête de chaque sommet littéral vers le sommet de la clause où elle se produit. Définissez pour un sommet littéral qui représente comme (où est un paramètre arbitraire), donc soit et ou et . Pour chaque clause-vertix, soitn=2v+cvncSxi{i,i+v+k}kf(xi)=if(x¯i)=i+v+kf(x¯i)=if(xi)=i+v+kkS={v+1,,v+k,2v+k+1,,n}, donc des vertex de clause sont `` petits ''.k

Maintenant, le CNF a une affectation où au moins clauses sont fausses si et seulement si votre problème peut être résolu pour l'instance ci-dessus. Le problème MinSAT est exactement de tester si une formule CNF φ a une affectation qui rend faux au moins k clauses, donc cela montre que votre problème est NP-difficile.kφk

Pour vous aider à comprendre cette réduction, voici l'intuition: les petites étiquettes ( ) correspondent à la valeur de vérité Faux et les grandes étiquettes ( v + k + 1 , , 2 v + k ) correspondent à Vrai. Les contraintes pour les sommets littéraux garantissent que chaque x i est soit vrai soit faux et que ¯ x i1,2,,v+kv+k+1,,2v+kxixi¯a la valeur de vérité opposée. Les arêtes garantissent que si un littéral est vrai, tous les sommets de clause qui le contiennent sont également affectés True. (En revanche, si tous les littéraux d'une clause se voient attribuer la valeur False, cette structure de graphe permet d'affecter le vertex de la clause à False ou True.) Enfin, le choix de garantit que k des vertex de la clause sont False et c - k d'entre eux ont la valeur True. Donc, s'il y a une sorte topologique valide de ce graphe, alors il y a une affectation aux variables qui fait au moins k des clauses de φkkckkφfalse (tous les vertex de clause affectés à False, plus peut-être certains de ceux à True). Inversement, s'il y a une affectation aux variables qui rend au moins des clauses de φ faux, alors il y a une sorte topologique valide de ce graphique (nous remplissons les étiquettes pour les sommets littéraux de la manière évidente; et pour chaque clause de φ qui est vraie, nous donnons à sa clause-sommet correspondante une étiquette qui correspond à True; les autres clauses-sommets peuvent recevoir des étiquettes correspondant à une valeur de vérité arbitraire).kφφ

domotorp
la source
Merci pour votre réponse! J'essaie de comprendre ton croquis. Pourriez-vous expliquer ce qu'est ? k
a3nm
1
@ a3nm: k est un paramètre donné pour l'entrée MinSAT.
domotorp du
1
@Marzio: SAT n'est pas équivalent à MinSAT avec , comme dans ce dernier problème, il faudrait que toutes les clauses soient fausses. Votre ϕ n'a pas de fausse affectation pour toutes les clauses. Bien sûr, cela ne prouve pas que ma réduction est correcte ...k=|c|ϕ
domotorp
C'est une magnifique réduction! @ a3nm, j'ai suggéré une modification de la réponse pour expliquer plus en détail l'élégante réduction de domotorp; s'il est approuvé, j'espère qu'il vous aidera à mieux comprendre les idées.
DW
@domotorp: vous avez raison, j'ai complètement raté ce qu'est MinSAT. Belle réduction !!!
Marzio De Biasi
2

Notez que si vous relâchez le problème en permettant à d'être arbitraire (pas nécessairement bijectif), alors il devient polynomial. L'algorithme procède de manière similaire au tri topologique: vous numérotez les sommets un par un, en conservant l'ensemble U de sommets non numérotés dont les voisins voisins ont été numérotés. Dans la mesure du possible, vous choisissez un sommet x U et le numérotez avec le plus petit élément de S ( x ) supérieur au nombre de ses voisins. Il n'est pas difficile de voir qu'une instance ( G , S ) a une solution si l'algorithme précédent s'exécute ( G ,fUxUS(x)(G,S) se termine par tous les sommets numérotés.(G,S)

Super0
la source
Bon point, cette relaxation signifie qu'une heuristique gourmande fonctionne, et c'est même dans le cas où n'est pas le nombre de sommets mais une valeur arbitraire. Sommes-nous d'accord que dans ce dernier cas, où l'injectivité et la surjectivité ne sont plus équivalentes, vous devrez vous détendre à la fois (et pas seulement un) pour que l'heuristique gourmande fonctionne? n
a3nm
2

Une observation banale est que si pour tout x , alors ce problème est résoluble en temps polynomial, par réduction à 2SAT.|S(x)|2x

Voici comment. Introduisez une variable pour chaque sommet x et chaque i tel que i S ( x ) . Pour chaque paire x , y de sommets, s'il y a un chemin de x à y , on obtient des contraintes: si i S ( x ) , j S ( y ) , et i > j , alors on obtient la contrainte ¬ v x , ivx,ixiiS(x)x,yxyiS(x)jS(y)i>j . La bijectivité nous donne un autre ensemble de contraintes: pour chaque paire x , y de sommets avec x y , si i S ( x ) et i S ( y ) , on ajoute ¬ v x , i¬ v y , i . Enfin, l'exigence d'attribuer une étiquette à chaque sommet nous donne encore un autre ensemble de contraintes: pour chaque x , si S (¬vx,i¬vy,jx,yxyiS(x)iS(y)¬vx,i¬vy,ix , on obtient la contrainte v x , iv x , j . (Notez que seul le dernier ensemble de contraintes exploite la promesse que | S ( x ) |2 pour chaque x .)S(x)={i,j}vx,ivx,j|S(x)|2x

Je réalise que cette observation ne vous aidera pas dans votre situation particulière. Désolé pour ça.

DW
la source