文章基本信息

标题：Reachability in K_{3,3}-free and K_5-free Graphs is in Unambiguous Logspace
本地全文：下载
作者：Thomas Thierauf ; Fabian Wagner
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2014
卷号：2014
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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