\thm
There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
-a~permutation satisfying a~given restriction graph.
+a~permutation satisfying a~given restriction graph. The $n$ and~$m$ are the number
+of vertices and edges of the restriction graph.
\proof
It is sufficient to verify that there exists a~perfect matching in the
\qed
\para
-The bad news is that computing the permanent is known to be~$\#P$-complete even
+The bad news is that computing the permanent is known to be~$\#\rm P$-complete even
for zero-one matrices (as proven by Valiant \cite{valiant:permanent}).
As a~ranking function for a~set of~matchings can be used to count all such
matchings, we obtain the following theorem:
\thm\id{pcomplete}%
If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
-a~set of restrictions which is a~part of the input, then $P=\#P$.
+a~set of restrictions which is a~part of the input, then $\rm P=\#P$.
\proof
We will show that a~polynomial-time ranking algorithm would imply a~po\-ly\-nom\-ial-time
algorithm for computing the permanent of an~arbitrary zero-one matrix, which
-is a~$\#P$-complete problem.
+is a~$\#\rm P$-complete problem.
We know from Lemma \ref{permchar} that non-zero
summands in the permanent of a~zero-one matrix~$M$ correspond to permutations restricted
rank of the lexicographically maximum such permutation.
It therefore remains to show that we can find the lexicographically maximum
permutation permitted by~$G$ in polynomial time.
+\looseness=1 %%HACK%%
We can determine $\pi[1]$ by trying all the possible values permitted by~$G$
in decreasing order and stopping as soon as we find~$\pi[1]$ which can be
by deleting vertices), ranking is easy as well. The key will be once again
a~recursive structure, similar to the one we have seen in the case of plain
permutations in \ref{permrec}.
+\looseness=1 %%HACK%%
\nota\id{restnota}%
As we will work with permutations on different sets simultaneously, we have
This translates to the following counterparts of algorithms \ref{rankalg}
and \ref{unrankalg}:
+\goodbreak %%HACK%%
\alg\id{rrankalg}%
$\<Rank>(\pi,i,n,A,M)$: Compute the lexicographic rank of a~permutation $\pi[i\ldots n]\in{\cal P}_{A,M}$.
and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
\qed
-\rem
-In cases where the efficient evaluation of the permanent is out of our reach,
+\paran{Approximation}%
+In cases where efficient evaluation of the permanent is out of our reach,
we can consider using the fully-polynomial randomized approximation scheme
for the permanent described by Jerrum, Sinclair and Vigoda \cite{jerrum:permanent}.
-Then we get an~approximation scheme for the ranks.
+They have described a~randomized algorithm that for every $\varepsilon>0$
+approximates the value of the permanent of an~$n\times n$ matrix with non-negative
+entries. The output is within relative error~$\varepsilon$ from the correct value with
+probability at least~$1/2$ and the algorithm runs in time polynomial in~$n$ and~$1/\varepsilon$.
+From this, we can get a~similar approximation scheme for the ranks.
-\rem
+\paran{Special restriction graphs}%
There are also deterministic algorithms for computing the number of perfect matchings
in various special graph families (which imply polynomial-time ranking algorithms for
the corresponding families of permutations). If the graph is planar, we can
orientations which runs in time $\O(n^3)$.
It has been recently extended to arbitrary surfaces by Yuster and Zwick
\cite{yuster:matching} and sped up to $\O(n^{2.19})$. The counting problem
-for arbitrary minor-closed classes (cf.~section \ref{minorclosed}) is still
+for arbitrary minor-closed classes (cf.~Section \ref{minorclosed}) is still
open.
%--------------------------------------------------------------------------------