From 9de99d825e2011290e2ed49418f47774077ad30a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 27 Feb 2008 13:47:45 +0100 Subject: [PATCH] Straightening. --- rank.tex | 58 +++++++++++++++++++++++++++++++++----------------------- 1 file changed, 34 insertions(+), 24 deletions(-) diff --git a/rank.tex b/rank.tex index 0021e55..ceea89f 100644 --- a/rank.tex +++ b/rank.tex @@ -421,13 +421,21 @@ The diversity of the characterizations of restricted permutations brings both good and bad news. The good news is that we can use the plethora of known results on bipartite matchings. Most importantly, we can efficiently determine whether there exists at least one permutation satistying a~given set of restrictions: -It is sufficient to reduce the particular matching problem to finding a~maximum flow in a~suitable -unit-capacity network. The flow can be then found using the Dinic's algorithm -in time $\O(\sqrt{n}\cdot m)$. Here $m$~is the number of edges in the network, which -is linear in the size of the graph~$G$, therefore at worst $\Theta(n^2)$. -(See \cite{dinic:flow} for the algorithm, \cite{even:dinic} for the time bound + +\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. + +\proof +It is sufficient to verify that there exists a~perfect matching in the +given graph. By a~standard technique, this can be reduced in linear time to finding a~maximum +flow in a~suitable unit-capacity network. This flow can be then found using the Dinic's +algorithm in time $\O(\sqrt{n}\cdot m)$. +(See \cite{dinic:flow} for the flow algorithm, \cite{even:dinic} for the time bound and \cite{schrijver} for more references on flows and matchings.) +\qed +\para The bad news is that computing the permanent is known to be~$\#P$-complete even for zero-one matrices (as proven by Valiant in \cite{valiant:permanent}). As a~ranking function for a~set of~matchings can be used to count all such @@ -438,23 +446,26 @@ If there is a~polynomial-time algorithm for lexicographic ranking of permutation a~set of restrictions which is a~part of the input, then $P=\#P$. \proof -We will show that such a~ranking algorithm would enable us to compute the permanent -of an~arbitrary zero-one matrix, which is a~$\#P$-complete problem. Let~$G$ be the -bipartite graph with its bipartite adjacency matrix equal to the given matrix. -The permanent of the matrix is then equal to the number of perfect matchings -in~$G$, which is one more than the rank of the lexicographically maximal perfect -matching in~$G$. As ranking of perfect matchings in~$G$ corresponds to ranking -of permutations restricted by~$G$, it remains to show that we can find the -lexicographically maximal permitted permutation in polynomial time. +We will show that a~polynomial-time ranking algorithm would imply a~polynomial-time +algorithm for computing the permanent of an~arbitrary zero-one matrix, which +is a~$\#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 +by a~graph~$G$ whose bipartite adjacency matrix is~$M$. The permanent is +therefore equal to the number of such permutations, which is one more than the +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. 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 -extended to a~complete permutation. We can do this for example by using the -Dinic's algorithm as described above on~the graph of remaining restrictions -(i.e., $G$ with the vertices 1 and~$\pi[1]$ and removed together with the corresponding -edges). Once we have~$\pi[1]$, we can fix it and proceed by finding $\pi[2]$ -in the same way, using the reduced graph. This way we construct the whole -maximal permutation~$\pi$ in~$\O(n^2)$ calls to the Dinic's algorithm. +extended to a~complete permutation. This can be verified using the previous +theorem on~the graph of the remaining restrictions, i.e., on~$G$ with the vertices +1~on one side and~$\pi[1]$ on the other side removed. +Once we have~$\pi[1]$, proceed by finding $\pi[2]$ in the same way, using the reduced +graph. This way we construct the whole maximum permutation~$\pi$ +in~$\O(n^2)$ calls to the verification algorithm. \qed \para @@ -582,10 +593,9 @@ the number of matchings instead. As~$G_n$ is a~complete bipartite graph without edges of a~single perfect matching, the graph~$G$ must be also complete bipartite with some non-touching edges -missing (but this matching is not necessarily perfect). Two such graphs -$G$ and~$G'$ are therefore isomorphic if and only if they have the same -number of vertices and also the same number of missing edges. -As the number of matchings is an~isomorphism invariant, the lemma follows. +missing. Two such graphs $G$ and~$G'$ are therefore isomorphic if and only if they have the +same number of vertices and also the same number of missing edges. As the +number of matchings is an~isomorphism invariant, the lemma follows. \qed \defn @@ -604,7 +614,7 @@ As we already observed (\ref{hatcheck}) that the number of derangements on~$[n]$ we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with insertion, deletion, ranking and unranking on them in constant time. -The submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$ is described by either +When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, it is described by either $z'=z-1$ and~$Z'=Z\setminus\{x\}$ (if $x\in Z$) or $z'=z$ and $Z'=Z$ (if $x\not\in Z$). All computations of~$N_0$ in the algorithm can therefore be replaced by looking up the appropriate $n_0(z',\vert A\vert-1)$ in a~precomputed table. Moreover, we can -- 2.39.2