Probability of generating a desired permutation by random swaps
I think that whether p&gt;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