Efficient Constructions of Antichain Cutsets

A subset \(S\) of an ordered set \(P\) is called a cutset if each maximal chain of \(P\) has nonempty intersection with \(S\); if, in addition, \(S\) is also an antichain, it is an antichain cutset. We consider new characterizations and generalizations of these and related concepts. The main generalization is to make our definitions in graph theoretic terms. For instance, a cutset is a subset \(S\) of the vertex set \(V\) of graph \(G = (V, E)\) which meets each extremal path of \(G\). Our principal results include (1)a characterization, by means of a closure property, of those antichains which are cutsets;(2) a characterization, by means of “forbidden paths” in the graph, of those graphs which can be expressed as the union of antichain cutsets;(3) a simpler proof of an existing result about \(N\)-free orders; and (4) efficient algorithms for many related problems, such as constructing antichain cutsets containing or excluding specified elements or forming a chain.

We include a brief discussion of the use of antichain cutsets in a parsing problem for \(LR(k)\) languages.