10
$\begingroup$

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=(1,2,\ldots,n)$ (i.e., the identity permutation), at each time step $t\in [m]$ we swap the $i_t^{th}$ element in $L$ with the $(i_t+1)^{st}$ element, with independent probability $1/2$. Let $p$ be the probability that $\sigma$ is produced as output.

I'd like to know (any of) the following:

  • Is deciding whether $p>0$ an $NP$-complete problem?
  • Is calculating $p$ exactly $\#P$-complete?
  • What can we say about approximating $p$ to within a multiplicative constant? Is there a PTAS for this?

The variant where the swaps don't need to be of adjacent elements is also of interest.

Note that it's not hard to reduce this problem to edge-disjoint paths (or to integer-valued multicommodity flow); what I don't know is a reduction in the other direction.

Update: OK, checking Garey & Johnson, their problem [MS6] ("Permutation Generation") is as follows. Given as input a target permutation $\sigma\in S_n$, together with subsets $S_1,\ldots,S_m\in [n]$, decide whether $\sigma$ is expressible as a product $\tau_1 \cdots \tau_m$, where each $\tau_i$ acts trivially on all indices not in $S_i$. Garey, Johnson, Miller, and Papadimitriou (behind a paywall, unfortunately) prove that this problem is $NP$-hard.

If the swaps don't need to be adjacent, then I believe this implies that deciding whether $p>0$ is also $NP$-hard. The reduction is simply this: for each $S_1,S_2,\ldots$ in order, we'll offer a set of "candidate swaps" that corresponds to a complete sorting network on $S_i$ (i.e., capable of permuting $S_i$ arbitrarily, while acting trivially on everything else). Then $\sigma$ will be expressible as $\tau_1 \cdots \tau_m$, if and only if it's reachable as a product of these swaps.

This still leaves open the "original" version (where the swaps are of adjacent elements only). For the counting version (with arbitrary swaps), it of course strongly suggests that the problem should be $\#P$-complete. In any case, it rules out a PTAS unless $P=NP$.

$\endgroup$
  • 1
    $\begingroup$ Not sure I understand the question. Where is the probability coming in? Is it that you swap with probability 1/2 and don't with probability 1/2? $\endgroup$ – arnab Aug 4 '14 at 6:47
  • $\begingroup$ @arnab yes. Scott, so you've proved that with $|S_i|=2$, it's still NP-hard. Mi intuition is that you "original" problem should be easier, but first I'd try to play with the paper's reduction. $\endgroup$ – Diego de Estrada Aug 4 '14 at 7:14
14
$\begingroup$

I think that whether p>0 can be decided in polynomial time.

The problem in question can be easily cast as the edge-disjoint paths problem, where the underlying graph is a planar graph consisting of m+1 layers each of which contains n vertices, plus m degree-4 vertices to represent the possible adjacent swaps. Note that the planarity of this graph follows from the fact that we allow only adjacent swaps.

If I am not mistaken, this falls in the special case of the edge-disjoint paths problem solved by Okamura and Seymour [OS81]. In addition, Wagner and Weihe [WW95] give a linear-time algorithm for this case.

See also Goemans’ lecture notes [Goe12], which gives a nice exposition of the Okamura–Seymour theorem and the Wagner–Weihe algorithm.

References

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

[OS81] Haruko Okamura and Paul D. Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B, 31(1):75–81, August 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner and Karsten Weihe. A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica, 15(1):135–150, March 1995. http://dx.doi.org/10.1007/BF01294465

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.