The Algorithmic Power of the Greene-Kleitman Theorem

For a given n-vertex DAG G = (V, E) with transitive-closure TC(G), a chain is a directed path in TC(G) and an antichain is an independent set in TC(G). The maximum k-antichain problem asks for computing the maximum k-colorable subgraph of the transitive closure. The related maximum h-chains problem asks for computing h disjoint chains (i.e., cliques in TC(G)) of largest total lengths. The celebrated Greene-Kleitman (GK) theorem [J. of Comb. Theory, 1976] demonstrates the (combinatorial) connections between these two problems. In this work we translate the combinatorial properties implied by the GK theorem into time-efficient covering algorithms. In contrast to prior results, our algorithms are applied directly on G, and do not require the precomputation of its transitive closure. Let α_k(G) be the maximum number of vertices that can be covered by k antichains. We show: For every n-vertex m-edge DAG G = (V, E), one can compute at most (2k−1) disjoint antichains that cover α_k(G) vertices in time m¹⁺o⁽¹⁾ (hence, independent in k). This extends the recent m¹⁺o⁽¹⁾-time Maximum-Antichain algorithm (where k = 1) by [Cáceres et al., SODA 2022] to any value of k. For every n-vertex m-edge Partially-Ordered-Set (poset) P = (V, E), one can compute (1 + ϵ)k disjoint antichains that cover α_k(P) vertices in time O(√m · α_k(P) · n^o(1)/ϵ), hence at most n²⁺o⁽¹⁾/ϵ. This improves over the exact solution of O(n³) time of [Gavril, Networks 1987] at the cost of producing (1 + ϵ)k antichains instead of exactly k. The heart of our approach is a linear-time greedy-like algorithm that translates suitable chain collections C into an parallel set of antichains A, in which |Cj ∩Ai| = 1 for every Cj ∈ C and Ai ∈ A. The correctness of this approach is underlined by the GK theorem.