14.3: Chain partitioning

In Chapter 6, we discussed Dilworth's Theorem, which told us that for any poset \(\textbf{P}\) of width \(w\), there is a partition of \(\textbf{P}\) 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 \(\textbf{P}\) 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 \(\textbf{P}\) are \(\{x_1,x_2,…,x_n\}\). We construct a network from \(\textbf{P}\) consisting of the source \(S\), sink \(T\), and two points \(x_i′\) and \(x_i″\) for each point \(x_i\) of \(\textbf{P}\). All edges in our network will have capacity 1. We add edges from \(S\) to \(x_i′\) for \(1≤i≤n\) and from \(x_i″\) to \(T\) for \(1≤i≤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<x_j\) in \(\textbf{P}\).

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

Figure 14.8. A partially ordered set (a) and the associated network (b).

The first step is to create the network, which we show in Figure 14.8.(b). 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<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 Figure 14.9. (Again, we use the convention that thick edges are full, while thin edges are empty.)

Figure 14.9. An initial flow

When we run the labeling algorithm (using priority \(S,T,x_1′,…,x_{10}′,x_1″,…,x_{10}″)\), we obtain the following list of labels:

\(S:(∗,+,∞)\) \(x_9″:(x_5′,+,1)\) \(x_3′:(S,+,1)\)

\(x_3′:(S,+,1)\) \(x_4″:(x_6′,+,1)\) \(x_1″:(x_7′,+,1)\)

\(x_5′:(S,+,1)\) \(x_5″:(x_6′,+,1)\) \(x_2″:(x_7′,+,1)\)

\(x_6′:(S,+,1)\) \(x_1′:(x_3″,−,1)\) \(x_2′:(x_7′,+,1)\)

\(x_9′:(S,+,1)\) \(x_8′:(x_9″,−,1)\) \(T:(x_2″,+,1)\)

\(x_3″:(x_5′,+,1)\) \(x_7′:(x_4″,−,1)\)

Thus, we find the augmenting path \((S,x_6′,x_4″,x_7′,x_2″,T)\), and the updated flow can be seen in Figure 14.10.

Figure 14.10. A better flow

If we run the labeling algorithm again, the algorithm assigns the labels below, leaving the sink unlabeled.

\(S:(∗,+,∞)\) \(x_5′:(S,+,1)\) \(x_3″:(x_5′,+,1)\) \(x_1′:(x_3″,−,1)\)

\(x_3′:(S,+,1)\) \(x_9′:(S,+,1)\) \(x_9″:(x_5′,+,1)\) \(x_8′:(x_9″,−,1)\)

In Figure 14.10, the black vertices are those the labeled in the final run, while the gold vertices are the unlabeled vertices.

Now that we've gone over the part you already knew how to do, we need to discuss how to translate this network flow and cut into a chain partition and an antichain. If there is a unit of flow on an edge \((x_i′,x_j″)\), then a good first instinct is to place \(x_i\) and \(x_j\) in the same chain of a chain partition. To be able to do this successfully, of course, we need to ensure that this won't result in two incomparable points being placed in a chain. A way to see that everything works as desired is to think of starting with \((x_i′,x_j″)\) and then looking for flow leaving \(x_j′\). If there is, it goes to a vertex \(x_k″\), so we may add xk to the chain since \(x_i<x_j<x_k\). Continue in this manner until reaching a vertex in the network that does not have any flow leaving it. Then see if \(x_i″\) has flow coming into it. If it does, it's from a vertex \(x_m′\) that can be added since \(x_m<x_i<x_j\).

Let's see how following this process for the flow in Figure 14.10 leads to a chain partition. If we start with \(x_1′\), we see that \((x_1′,x_3″)\) is full, so we place \(x_1\) and \(x_3\) in chain \(C_1\). Since \(x_3′\) has no flow leaving it, there are no greater elements to add to the chain. However, \(x_1″\) has flow in from \(x_2′\), so we add \(x_2\) to \(C_1\). We now see that \(x_2″\) has flow in from \(x_7′\), so now \(C_1=\{x_1,x_2,x_3,x_7\}\). Vertex \(x_7″\) has no flow into it, so the building of the first chain stops. The first vertex we haven't placed into a chain is \(x_4\), so we note that \((x_4′,x_5″)\) is full, placing \(x_4\) and \(x_5\) in chain \(C_2\). We then look from \(x_5′\) and see no flow leaving. However, there is flow into \(x_4″\) from \(x_6′\), so \(x_6\) is added to \(C_2\). There is no flow out of \(x_6″\), so \(C_2=\{x_4,x_5,x_6\}\). Now the first point not in a chain is \(x_8\), so we use the flow from \(x_8′\) to \(x_9″\) to place \(x_8\) and \(x_9\) in chain \(C_3\). Again, no flow out of \(x_9′\), so we look to \(x_8″\), which is receiving flow from \(x_{10}″\). Adding \(x_{10}\) to \(C_3\) gives \(C_3=\{x_8,x_9,x_{10}\}\), and since every point is now in a chain, we may stop.

Even once we see that the above process does in fact generate a chain partition, it is not immediately clear that it's a minimum chain partition. For this, we need to find an antichain of as many points as there are chains in our partition. (In the example we've been using, we need to find a three-element antichain.) This is where tracking the labeled vertices comes in handy. Suppose we have determined a chain \(C=\{x_1<x_2< \cdot \cdot \cdot <x_k\}\) using the network flow. Since \(x_1\) is the minimal element of this chain, there is no flow into \(x_1″\) and hence no flow out of \(x_1″\). Since \(T\) is unlabeled, this must mean that \(x_1″\) is unlabeled. Similarly, \(x_k\) is the maximal element of \(C\), so there is no flow out of \(x_k′\). Thus, \(x_k′\) is labeled. Now considering the sequence of vertices

\(x_k′,x_k″,x_{k−1}′,x_{k−1}″,…,x_2′,x_2″,x_1′,x_1″\),

there must be a place where the vertices switch from being labeled to unlabeled. This must happen with \(x_i′\) labeled and \(x_i″\) unlabeled. To see why, suppose that \(x_i′\) and \(x_i″\) are both unlabeled while \(x_{i+1}′\) and \(x_{i+1}″\) are both labeled. Because \(x_i\) and \(x_{i+1}\) are consecutive in \(C\), there is flow on \((x_i′,x_{i+1}″)\). Therefore, when scanning from \(x_{i+1}″\), the vertex \(x_i′\) would be labeled. For each chain of the chain partition, we then take the first element \(y\) for which \(y′\) is labeled and \(y″\) is unlabeled to form an antichain \(A=\{y_1,…,y_w\}\). To see that \(A\) is an antichain, notice that if \(y_i<y_j\), then \((y_i′,y_j″)\) is an edge in the network. Therefore, the scan from \(y_i′\) would label \(y_j″\). Using this process, we find that a maximum antichain in our example is \(\{x_1,x_5,x_8\}\).