Probabilité de générer une permutation souhaitée par swaps aléatoires

Je suis intéressé par le problème suivant. On nous donne en entrée une "permutation cible" , ainsi qu'une liste ordonnée d'indices . Ensuite, en commençant par la liste (c'est-à-dire la permutation d'identité), à chaque pas de temps nous l' dans avec le élément, avec probabilité indépendante . Soit la probabilité que soit produit en sortie.i 1 , ... , i m ∈ [ n - 1 ] L = ( 1 , 2 , ... , n ) t ∈ [ m ] i t h t L ( i t + 1 ) s t 1 / 2 p $\sigma\in S_n$$i_1,\ldots,i_m\in [n-1]$$L=(1,2,\ldots,n)$$t\in [m]$$i_t^{th}$$L$$(i_t+1)^{st}$$1/2$$p$$\sigma$

J'aimerais savoir (n'importe lequel) des éléments suivants:

• Décider si un problème complet?N $p>0$$NP$
• Le calcul de exactement terminé?# $p$$\#P$
• Que pouvons-nous dire sur l'approximation de à l'intérieur d'une constante multiplicative? Existe-t-il un PTAS pour cela?$p$

La variante où les swaps n'ont pas besoin d'être d'éléments adjacents est également intéressante.

Notez qu'il n'est pas difficile de réduire ce problème à des chemins bord-disjoints (ou à un flux multicommodité à valeur entière); ce que je ne sais pas, c'est une réduction dans l'autre sens.

Mise à jour: OK, en vérifiant Garey & Johnson, leur problème [MS6] ("Permutation Generation") est le suivant. Étant donné en entrée une permutation cible , avec les sous-ensembles , décidez si est exprimable en tant que produit , où chaque agit trivialement sur tous les indices ne sont pas dans . Garey, Johnson, Miller et Papadimitriou (derrière un mur payant, malheureusement) prouvent que ce problème est dur.S 1 , … , S m ∈ [ n ] σ τ 1 ⋯ τ m τ i S $\sigma\in S_n$$S_1,\ldots,S_m\in [n]$$\sigma$$\tau_1 \cdots \tau_m$$\tau_i$$S_i$$NP$

Si les swaps n'ont pas besoin d'être adjacents, je pense que cela implique que décider si est également dur. La réduction est simplement la suivante: pour chaque dans l'ordre, nous proposerons un ensemble de "swaps candidats" qui correspond à un réseau de tri complet sur (c'est-à-dire capable de permuter arbitrairement, tout en agissant trivialement sur tout le reste). Alors sera exprimable sous la forme , si et seulement si elle est accessible en tant que produit de ces échanges.N P S 1 , S 2 , … S i S i σ τ 1 ⋯ τ $p>0$$NP$$S_1,S_2,\ldots$$S_i$$S_i$$\sigma$$\tau_1 \cdots \tau_m$

Cela laisse toujours ouverte la version "originale" (où les échanges sont uniquement des éléments adjacents). Pour la version de comptage (avec des échanges arbitraires), cela suggère bien sûr fortement que le problème devrait être -complete. Dans tous les cas, il exclut un PTAS sauf si .P = N $\#P$$P=NP$

Je pense que si p> 0 peut être décidé en temps polynomial.

Le problème en question peut être facilement converti en problème de chemins bord-disjoints, où le graphe sous-jacent est un graphe plan composé de m +1 couches dont chacune contient n sommets, plus m sommets de degré 4 pour représenter les permutations adjacentes possibles. Notez que la planarité de ce graphique découle du fait que nous n'autorisons que les swaps adjacents.

Si je ne me trompe pas, cela tombe dans le cas particulier du problème des chemins bord-disjoints résolu par Okamura et Seymour [OS81]. De plus, Wagner et Weihe [WW95] donnent un algorithme de temps linéaire pour ce cas.

Voir aussi les notes de cours de Goemans [Goe12], qui donnent une belle exposition du théorème d'Okamura – Seymour et de l'algorithme de Wagner – Weihe.

Références

[Goe12] Michel X. Goemans. Notes de cours, 18.438 Advanced Combinatorial Optimization, cours 23 . Massachusetts Institute of Technology, printemps 2012. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura et Paul D. Seymour. Flux multi-commodités dans les graphes planaires. Journal of Combinatorial Theory, série B , 31 (1): 75–81, août 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner et Karsten Weihe. Un algorithme de temps linéaire pour les chemins bord-disjoints dans les graphes planaires. Combinatorica , 15 (1): 135-150, mars 1995. http://dx.doi.org/10.1007/BF01294465