Series-parallel partial order

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.

Series-parallel partial orders have also been called multitrees; however the same name has also been applied to polytrees, a different type of partial order. The series-parallel partial orders may be characterizes as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series-parallel graphs. The comparability graphs of series-parallel partial orders are cographs.

Definition

If P and Q are two partially ordered sets, then the series composition of P and Q is the partially ordered set whose elements are the disjoint union of the elements of P and Q. In P ⧀ Q, two elements x and y that both belong to P or that both belong to Q have the same order relation that they do in P or Q respectively. However, for every pair x, y where x belongs to P and y belongs to Q, there is an additional order relation x ≤ y in the series composition. The series composition is written variously as P ⧀ Q or P * Q. It is an associative operation, but not a commutative operation: switching the roles of P and Q will in general produce a different partial order reversing the order relations of pairs with one element in P and one in Q.

The parallel composition of P and Q, denoted as P ⊕ Q or P + Q is defined similarly, from the disjoint union of the elements in P and the elements in Q, with pairs of elements that both belong to P or both to Q having the same order as they do in P or Q respectively. Every pair x, y where x belongs to P and y belongs to Q is incomparable. Parallel composition is both commutative and associative.

The class of series-parallel partial order is the set of partial orders that can be built up from single-element partial orders using these two operations. Equivalently, it is the smallest set of partial orders that includes the single-element partial order and is closed under the series and parallel composition operations.

A weak order is the series parallel partial order obtained from a sequence of composition operations in which all of the parallel compositions are performed first, and then the results of these compositions are combined using only series compositions.

Forbidden suborder characterization

The partial order N with the four elements a, b, c, and d and the three order relations a ≤ b ≥ c ≤ d is an example of a fence or zigzag poset; its Hasse diagram has the shape of the capital letter "N". It is not series-parallel, because there is no way of splitting it into the series or parallel composition of two smaller partial orders. A partial order P is said to be N-free if there does not exist a set of four elements in P such that the restriction of P to those elements is order-isomorphic to N. The series-parallel partial orders are exactly the nonempty finite N-free partial orders.

It follows immediately from this (although it can also be proven directly) that any nonempty restriction of a series-parallel partial order is itself a series-parallel partial order.

Order dimension

The order dimension of a partial order P is the minimum size of a realizer of P, a set of linear extensions of P with the property that, for every two distinct elements x and y of P, x ≤ y in P if and only if x has an earlier position than y in every linear extension of the realizer. Series-parallel partial orders have order dimension at most two. If P and Q have realizers {L₁, L₂} and {L₃, L₄}, respectively, then {L₁L₃, L₂L₄} is a realizer of the series composition P * Q, and {L₁L₃, L₄L₂} is a realizer of the parallel composition P + Q.

It is known that a partial order P has order dimension two if and only if there exists a conjugate order Q on the same elements, with the property that any two distinct elements x and y are comparable on exactly one of these two orders. In the case of series parallel partial orders, a conjugate order that is itself series parallel may be obtained by performing a sequence of composition operations in the same order as the ones defining P on the same elements, but performing a series composition for each parallel composition in the decomposition of P and vice versa. More strongly, although a partial order may have many different conjugates, every conjugate of a series parallel partial order must itself be series parallel.

Connections to graph theory

One may represent a series-parallel partial order by a graph, with a vertex for each element and an edge from x to y whenever x and y are distinct elements of the partial order with x ≤ y. These graphs have been called minimal vertex series parallel graphs.

The transitive closure of directed trees and (two-terminal) series parallel graphs are minimal vertex series parallel graphs; therefore, series parallel partial orders may be used to represent reachability relations in directed trees and series parallel graphs.

The comparability graph of a partial order is the undirected graph with a vertex for each element and an undirected edge for each pair of distinct elements x, y with either x ≤ y or y ≤ x. The comparability graph of a series-partial order is a cograph: the series and parallel composition operations of the partial order give rise to operations on the comparability graph that form the disjoint union of two subgraphs or that connect two subgraphs by all possible edges; these two operations are the basic operations from which cographs are defined. Conversely, if a partial order has a cograph as its comparability graph, then it must be a series-parallel partial order, for otherwise its N suborder would correspond to an induced four-vertex path in the comparability graph, and such paths are forbidden in cographs.

Computational complexity

It is possible to use the forbidden suborder characterization of series-parallel partial orders as a basis for an algorithm that tests whether a given binary relation is a series-parallel partial order, in an amount of time that is linear in the number of related pairs.

If a series-parallel partial order is represented as an expression tree describing the series and parallel composition operations that formed it, then the elements of the partial order may be represented by the leaves of the expression tree. A comparison between any two elements may be performed algorithmically by searching for the lowest common ancestor of the corresponding two leaves; if that ancestor is a parallel composition, the two elements are incomparable, and otherwise the order of the series composition operands determines the order of the elements. In this way, a series-parallel partial order on n elements may be represented in O(n) space with O(1) time to determine any comparison value.

It is NP-complete to test, for two given series-parallel partial orders P and Q, whether P contains a restriction isomorphic to Q.

Although the problem of counting the number of linear extensions of an arbitrary partial order is #P-complete, it may be solved in polynomial time for series-parallel partial orders. Specifically, if L(P) denotes the number of linear extensions of a partial order P, then L(P * Q) = L(P)L(Q) and

$L(P+Q)={\frac {(|P|+|Q|)!}{|P|!|Q|!}}L(P)L(Q),$

so the number of linear extensions may be calculated using an expression tree with the same form as the decomposition tree of the given series-parallel order.