Finding parity difference by involutions (Q1356534)

For a finite set of combinatorial objects (for example the set of linear extensions of a fixed partial order) we look for an algorithm listing these objects one by one, such that consecutive objects differ as little as possible (in the example: by one transposition only). Such a minimal change generating algorithm defines a hamiltonian path in the graph \(G\) on the set of objects in which two objects are adjacent if and only if they differ by a minimal change. If this minimal change graph is bipartite, then a necessary condition for the existence of a hamiltonian path (or a minimal change generating algorithm) is that the size of the partite sets (colour classes) differs by at most one. This paper shows that computing this parity difference for linear extensions of posets is in GapP and \#P-hard (\#P is not closed under difference, unless PH collapses to UP [\textit{M. Ogiwara} and \textit{L. A. Hemachandra}, J. Comput. Syst. Sci. 46, 295-325 (1993; Zbl 0798.68060)]). The main part of the paper deals with the generation of trees. Let \(\vec{n} = (n_0,n_1,\ldots,n_k)\) and \(n = n_0+n_1+\cdots+n_k\). By \({\mathcal T}(\vec{n})\) we denote the set of strings \(A=a_1a_2a_3\ldots a_n\) consisting of \(n_i\) characters \(i\) for \(i=1,\ldots,k\) such that \(a_1+a_2+\cdots+a_j \leq j\) for all \(j=1,\ldots,n\). Again, a minimal change for such a multiset permutation \(A\) is a transposition of two consecutive characters in the string \(A\). The paper extends a result obtained by \textit{D. W. Ko} and \textit{F. Ruskey} [Discrete Math. 71, No. 1, 47-56 (1988; Zbl 0689.05007)] on the parity difference of \({\mathcal T}(\vec{n})\).