Finding parity difference by involutions Original Research Article

Parity difference equal to 0 or ±1 is a necessary condition for the existence of minimal change generation algorithms for many combinatorial objects. We prove that finding pairty difference for linear extensions of posets is #P-complete. We also show a new method of finding parity difference for strings representing forests and a combinatorial interpretation of this results as well as all cases when this value is equal to 0 or ±1 (see, Ko and Ruskey, 1988).