# On Finding Two Posets that Cover Given Linear Orders
## 1 Introduction
### Poset Cover Problem  
Instance: A set \(\mathrm{Y}=\{L_{1},L_{2},...,L_{m}\}\) of linear orders over the set \(V=\{1,2,3,...,n\}\).  
Solution: A set \(P^{*}=\{P_{1},P_{2},...,P_{k}\}\) of posets where \(\bigcup_{P_{i}\in P^{*}}\mathcal{L}(P_{i})=\mathrm{Y}\) and \(k\) is minimum.  
The Poset Cover Problem finds application in data mining where there is a massive set of sequential data and the goal is to determine directed networks that explain the ordering of objects in the sequential data. A simple example of this is in marketing, when the business wants to generate a directed process model from the logs of customers' purchases of their products. The logs can be treated as linear orders of the products. Determining directed process models, which explains the purchasing behavior of the customers, can then be represented as getting a set of posets that generate the linear orders (logs). The process model can then be used to predict other customers' future purchases, and the business could develop marketing campaigns from it. Similar to this kind of data mining, the problem is also relevant in other areas such as in neuroscience [4], chemical engineering [5], epidemiology [6], paleontology [7; 8], and systems biology [9].  
The decision version of the Poset Cover Problem has been shown to be NP-Hard [3]. To deepen the knowledge about the Poset Cover Problem, efforts in the past have focused on studying constrained cases of the problem and trying to draw boundaries of the cases that are in \(P\) and cases that are NP-Hard. There are essentially two ways in which the problem can be restricted or constrained. The first is to consider only a specific number of posets, say \(k\). The problem when \(k=1\), or the 1-Poset Cover Problem, is in \(\mathrm{P}\)[10]. The computational complexity of the problem when \(k=2\), or the 2-Poset Cover Problem, is not yet known. What have been devised are heuristics for the 2-Poset Cover Problem [11]. The other way of restricting the problem is to consider only a specific class of posets according to their Hasse diagram, such as a tree-poset. The poset in Figure 1 is an example of a tree-poset since its Hasse diagram is a tree. The restricted cases of the Poset Cover Problem are similarly important as there may also be instances wherein the class of posets to be reconstructed are known. For example in paleontology, the goal is to construct evolutionary ordering of fossil sites from sequential data about the taxa that occur in each site [7; 8]. Evolutionary orderings are usually expressed using trees because evolution starts with an origin and branches out to descendants. Other classes of posets that have been studied are hammock posets and leveled posets [10]. The 2-Tree-Poset Cover Problem then is a contrained variation where the goal is to determine if there exist two tree-posets that cover exactly all of the given set of linear orders.  
In our study, we derived properties on posets, which lead to an exact solution for the 2-Poset Cover Problem. The algorithm runs in exponential time. However, if the posets to be considered are tree-posets, the running time of the algorithm becomes polynomial. This proves that the 2-Tree-Poset Cover Problem is also in P.