Path-Precedence Orders in Trees

Abstract

This dissertation studies classes of partial orders defined by the precedence of paths in trees, using two different notions of precedence. Strict precedence uses the same notion that interval orders use, where one path $x$ precedes another $y$ if $x$ ends before $y$ begins. Weak precedence requires only that $x$ start before and end before $y$, but the paths may intersect. Partial orders given by the weak precedence of intervals are exactly equal to the two-dimensional partial orders. Therefore, both of these notions of precedence, when applied to paths in a tree, generalize well-known and well-studied classes of partial orders.

Linear-time algorithms that construct the realizer for partial orders with a tree dia-gram are presented for both rooted and general trees. A forbidden induced-suborder characterization and new certifying recognition algorithm are given for partial orders of strict precedence in a rooted tree. The orders of weak precedence in a rooted tree are shown to have a nice intersection characterization, and such partial orders that are also bipartite can be recognized in $O(m+n)$ time. The independent set and clique problems for both of these classes are studied, and algorithms for these problems are presented which, given the tree-model as input, are asymptotically more efficient than the well-known algorithms for these problems on comparability graphs. Finally, a forbidden induced-suborder characterization of general, strict path-precedence orders is shown, leading to an $O(n^2)$ certifying recognition algorithm.