Fast Möbius and Zeta Transforms

Abstract

Möbius inversion of functions on partially ordered sets (posets) $\mathcal{P}$ is a classical tool in combinatorics. For finite posets it consists of two, mutually inverse, linear transformations called zeta and Möbius transform, respectively. In this paper we provide novel fast algorithms for both that require $O(nk)$ time and space, where $n=|\mathcal{P}|$ and $k$ is the width (length of longest antichain) of $\mathcal{P}$, compared to $O(n^2)$ for a direct computation. Our approach assumes that $\mathcal{P}$ is given as directed acyclic graph (DAG) $(\mathcal{E},\mathcal{P})$. The algorithms are then constructed using a chain decomposition for a one time cost of $O(|\mathcal{E}|+|{\mathcal{E}}_{\text{red}}|k)$, where ${\mathcal{E}}_{\text{red}}$ is the number of edges in the DAG's transitive reduction. We show benchmarks with implementations of all algorithms including parallelized versions. The results show that our algorithms enable Möbius inversion on posets with millions of nodes in seconds if the defining DAGs are sufficiently sparse.

16 pages, 7 figures, submitted for review