Chicago Journal of Theoretical Computer Science

Volume 2014

Article 3

Published by the Department of Computer Science, The University of Chicago.

Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction

Mark Huber
Claremont McKenna College
Claremont CA
mhuber AT

June 8, 2014


A linear extension of a poset $([n],\preceq)$ is a permutation $\sigma$ such that if $\sigma(i) \preceq \sigma(j)$, then $i \leq j$. The problem considered here is sampling uniformly from the set of linear extensions. The best known algorithm for the general problem requires time $O(n^3\ln n)$. This work presents the first new method that is provably faster for a nontrivial class of posets. Specifically, when the poset is height-2 (so there do not exist distinct elements with $i \preceq j \preceq k$) and has bounded interaction (so for each $i$ there are at most $\Delta$ elements $i'$ with $i \preceq i'$ or $i' \preceq i$), then the new algorithm runs in time $O(n\Delta^2 \ln n)$. Such posets arise naturally as corrugated surfaces on graphs, where $\Delta - 1$ is the maximum degree of the graph. Therefore, finding corrugated surfaces on a fixed family of lattices takes $O(n \ln n)$ (near-linear time.) The ability to sample from the set of linear extensions can be used to build approximation algorithms for counting the number of linear extensions. Using the new method, an approximation scheme that counts the number of linear extensions to within a factor of $1 + \epsilon$ with fixed probability runs in $O(n^2 \Delta^2 [\ln n]^6\epsilon^{-2})$ time.

Submitted November 10, 2012, revised May 24, 2014, published June 8,2014.

DOI: 10.4086/cjtcs.2014.003

[] Article 2 [back] Volume 2014 [back] Published articles
[CJCTS home]