On Finding Two Posets that Cover Given Linear Orders

• Main Authors: Ordanel, Ivy, Fernandez, Proceso L, Jr, Adorna, Henry
• Format: text
• Published: Archīum Ateneo 2019
• Subjects: partial order; poset; linear extensions; algorithm; complexity; Computer Sciences; Databases and Information Systems; Theory and Algorithms
• Online Access: https://archium.ateneo.edu/discs-faculty-pubs/299; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1300&context=discs-faculty-pubs
• Institution: Ateneo De Manila University

The Poset Cover Problem is an optimization problem where the goal is to determine a minimum set of posets that covers a given set of linear orders. This problem is relevant in the field of data mining, specifically in determining directed networks or models that explain the ordering of objects in a large sequential dataset. It is already known that the decision version of the problem is NP-Hard while its variation where the goal is to determine only a single poset that covers the input is in P. In this study, we investigate the variation, which we call the 2-Poset Cover Problem, where the goal is to determine two posets, if they exist, that cover the given linear orders. We derive properties on posets, which leads to an exact solution for the 2-Poset Cover Problem. Although the algorithm runs in exponential-time, it is still significantly faster than a brute-force solution. Moreover, we show that when the posets being considered are tree-posets, the running-time of the algorithm becomes polynomial, which proves that the more restricted variation, which we called the 2-Tree-Poset Cover Problem, is also in P.