Chain partitioning

In , we discussed , which told us that for any poset \(\bfP\) of width \(w\), there is a partition of \(\bfP\) into \(w\), but no fewer, chains. However, we were only able to devise an algorithm to find this chain partition (and a maximum antichain) in the special case where \(\bfP\) was an interval order. Now, through the magic of network flows, we will be able to devise an efficient algorithm that works in general for all posets. However, to do so, we will require a slightly more complicated network than we devised in the previous section.

Suppose that the points of our poset \(\bfP\) are \(\{x_1,x_2,\dots,x_n\}\). We construct a network from \(\bfP\) consisting of the source \(S\), sink \(T\), and two points \(x'_i\) and \(x''_i\) for each point \(x_i\) of \(\bfP\). All edges in our network will have capacity \(1\). We add edges from \(S\) to \(x'_i\) for \(1\leq i\leq n\) and from \(x''_i\) to \(T\) for \(1\leq i\leq n\). Of course, this network wouldn't be too useful, as it has no edges from the single-prime nodes to the double-prime nodes. To resolve this, we add an edge directed from \(x'_i\) to \(x''_j\) if and only if \(x_i \lt x_j\) in \(\bfP\).

Our running example in this section will be the poset in . We'll discuss the points of the poset as \(x_i\) where \(i\) is the number printed next to the point in the diagram.

The first step is to create the network, which we show in . In this network, all capacities are \(1\), edges are directed from bottom to top, the first row of ten vertices is the \(x'_i\) arranged consecutively with \(x'_1\) at the left and \(x'_{10}\) at the right, and the second row of ten vertices is the \(x''_i\) in increasing order of index. To see how this network is constructed, notice that \(x_1\lt x_3\) in the poset, so we have the directed edge \((x_1',x_3'')\). Similarly, \(x_4\) is less than \(x_3\), \(x_5\), and \(x_9\) in the poset, leading to three directed edges leaving \(x_4'\) in the network. As a third example, since \(x_9\) is maximal in the poset, there are no directed edges leaving \(x_9'\).

We have not yet seen how we might turn a maximum flow (or minimum cut) in the network we've just constructed into a minimum chain partition or a maximum antichain. It will be easier to see how this works once we have a confirmed maximum flow. Rather than running the labeling algorithm starting from the zero flow, we eyeball a flow, such as the one shown in . (Again, we use the convention that thick edges are full, while thin edges are empty.)

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.