The Algorithmic Power of the Greene-Kleitman Theorem

The Algorithmic Power of the Greene-Kleitman Theorem

Authors Shimon Kogan, Merav Parter



PDF
Thumbnail PDF

File

LIPIcs.ESA.2024.80.pdf
  • Filesize: 0.68 MB
  • 14 pages

Document Identifiers

Author Details

Shimon Kogan
  • Weizmann Institute of Science, Rehovot, Israel
Merav Parter
  • Weizmann Institute of Science, Rehovot, Israel

Cite As Get BibTex

Shimon Kogan and Merav Parter. The Algorithmic Power of the Greene-Kleitman Theorem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) https://doi.org/10.4230/LIPIcs.ESA.2024.80

Abstract

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^{1+o(1)} (hence, independent in k). This extends the recent m^{1+o(1)}-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^{2+o(1)}/ε. 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 𝒞 into an parallel set of antichains 𝒜, in which |C_j ∩ A_i| = 1 for every C_j ∈ 𝒞 and A_i ∈ 𝒜. The correctness of this approach is underlined by the GK theorem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Chains
  • Antichains
  • DAG

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ron Aharoni and Irith Ben-Arroyo Hartman. On greene-kleitman’s theorem for general digraphs. Discret. Math., 120(1-3):13-24, 1993. Google Scholar
  2. Manuel Cáceres. Minimum chain cover in almost linear time. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 31:1-31:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPICS.ICALP.2023.31.
  3. Manuel Cáceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, and Alexandru I. Tomescu. Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 359-376. SIAM, 2022. Google Scholar
  4. Glenn G. Chappell. Polyunsaturated posets and graphs and the greene-kleitman theorem. Discret. Math., 257(2-3):329-340, 2002. Google Scholar
  5. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 612-623. IEEE, 2022. Google Scholar
  6. RP Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, pages 161-166, 1950. Google Scholar
  7. András Frank. On chain and antichain families of a partially ordered set. J. Comb. Theory, Ser. B, 29(2):176-184, 1980. Google Scholar
  8. Fǎnicǎ Gavril. Algorithms for maximum k-colorings and k-coverings of transitive graphs. Networks, 17(4):465-470, 1987. Google Scholar
  9. Curtis Greene and Daniel J Kleitman. The structure of sperner k-families. Journal of Combinatorial Theory, Series A, 20(1):41-68, 1976. Google Scholar
  10. Alan J. Hoffman and D. E. Schwartz. On partitions of a partially ordered set. J. Comb. Theory, Ser. B, 23(1):3-13, 1977. Google Scholar
  11. Shimon Kogan and Merav Parter. Beating matrix multiplication for n^1/3-directed shortcuts. In The 49th EATCS International Colloquium on Automata, Languages and Programming ICALP 2022, 2022. Full version available at URL: https://www.weizmann.ac.il/math/parter/sites/math.parter/files/uploads/main-lipics-full-version_3.pdf.
  12. Shimon Kogan and Merav Parter. Faster and unified algorithms for diameter reducing shortcuts and minimum chain covers. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 212-239. SIAM, 2023. Google Scholar
  13. Nathan Linial. Extending the greene-kleitman theorem to directed graphs. J. Comb. Theory, Ser. A, 30(3):331-334, 1981. Google Scholar
  14. Carsten Lund and Mihalis Yannakakis. The approximation of maximum subgraph problems. In Svante Carlsson Andrzej Lingas, Rolf G. Karlsson, editor, Automata, Languages and Programming, 20th International Colloquium, volume 700 of Lecture Notes in Computer Science, pages 40-51, July 1993. Google Scholar
  15. Leon Mirsky. A dual of dilworth’s decomposition theorem. The American Mathematical Monthly, 78(8):876-877, 1971. Google Scholar
  16. Giri Narasimhan. The maximum k-colorable subgraph problem. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1989. Google Scholar
  17. Michael Saks. A short proof of the existence of k-saturated partitions of partially ordered sets. Advances in Mathematics, 33(3):207-211, 1979. Google Scholar
  18. Michael E. Saks. Kleitman and combinatorics. Discret. Math., 257(2-3):225-247, 2002. Google Scholar
  19. Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 503-514. IEEE, 2023. Google Scholar
  20. Douglas B. West. "Poly-unsaturated" posets: The Greene-Kleitman theorem is best possible. J. Comb. Theory, Ser. A, 41(1):105-116, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail