# On Finding Two Posets that Cover Given Linear Orders
## 4 Algorithm for the 2-Poset Cover Problem  
As mentioned earlier, there is already a polynomial-time solution for the 1-Poset Cover Problem [10]. We can determine in \(O(mn^{2})\) time, where \(m\) is the number of linear orders over a base set of \(n\) elements, the poset that covers a given set of linear orders. Let us denote the algorithm for the 1-Poset Cover Problem as GeneratePoset. The input to GeneratePoset is a set of linear orders and it returns a poset, if there exists such, that covers the input; otherwise it returns null. Now, for the 2-Poset Cover Problem with input \(Y\), a brute-force algorithm is then to determine \(Y_{1}\), \(Y_{2}\subseteq Y\) such that \(Y_{1}\cup Y_{2}=Y\) and then use GeneratePoset to determine if there is a poset that covers \(Y_{1}\) and a poset that covers \(Y_{2}\). Since there are \(3^{m}\) possibilities for values of \(Y_{1}\) and \(Y_{2}\), the brute-force algorithm entails a running time of \(O(3^{m}mn^{2})\). Theorem 1 suggests a strategy of partitioning \(Y\). Given a pair \((a,b)\in V\times V\), we can partition \(Y\) into \(Y_{1}=\{L\in Y|a<_{L}b\}\) and \(Y_{2}=\{L\in Y|b<_{L}a\}\). Suppose there exist two posets, say \(P=(V,<_{p})\) and \(P^{\prime}=(V,<_{p^{\prime}})\) that cover \(Y\). If \((a,b)\in<_{p}\) and \((b,a)\in<_{p^{\prime}}\), then we just have partitioned \(Y\) perfectly because \(Y_{1}=\mathcal{L}(P)\) and \(Y_{2}=\mathcal{L}(P^{\prime})\). Hence, we can determine \(P\) and \(P^{\prime}\) using GeneratePoset with \(Y_{1}\) and \(Y_{2}\) as inputs, respectively. This is executed in Lines 7 and 8 of Algorithm 1. However, such a pair does not always exist. There can be also instances where \(a\perp_{P}b\) and \(a||_{P}b\) and vice versa--there also exists a different pair, say \((c,d)\) where \(c||pd\) and \(c\perp_{P}d\). Without lost of generality on \(a\perp_{P}b\), suppose \(a<_{P}b\). Then, if we apply the same partitioning strategy, \(Y_{1}=\mathcal{L}(P)\cup\{L\in\mathcal{L}(P^{\prime})|a<_{L}b\}\) and \(Y_{2}=\{L\in\mathcal{L}(P^{\prime})|b<_{L}a\}\). We are not sure if there exists a poset that covers \(Y_{1}\), however, we are sure from Theorem 1 that there exists a poset that covers \(Y_{2}\), say \(P_{2}\). Moreover, with the use of the equations in the Theorem, we can determine or reconstruct the relation of \(P^{\prime}\) from \(P_{2}\). These are executed in Lines 22-32. We can also determine \(P\) in a similar way with the pair \((c,d)\). This is executed in Lines 10-20 in the Algorithm. Theorem 2: _Algorithm 1 produces a solution to the 2-Poset Cover Problem in \(O(2^{m}mn+mn^{4}+m^{2})\) time._  
Proof. : Let \(P\) and \(P^{\prime}\) be the two different posets that cover \(Y\), i.e., \(\mathcal{L}(P)\cup\mathcal{L}(P^{\prime})=Y\). In the following, we want to show that \(P\) and \(P^{\prime}\), if there exist such, can be determined and generated by the 2-Poset Cover Algorithm. With the assumption that \(P\
eq P^{\prime}\) means also that \(<_{P}\
eq<_{P^{\prime}}\), then there must exist, without loss of generality, at least one \((a,b)\) such that \((a,b)\in<_{P}\) but \((a,b)\
ot\in<_{P}\). On the other hand, there must also exist \((c,d)\) such that \((c,d)\in<_{P^{\prime}}\) but \((c,d)\
ot\in<_{P}\), otherwise, \(<_{P}\subset<_{P}\) and by Lemma 1, \(Y\) can be covered by a single poset \(P^{\prime}\). Let us first take the case where \((a,b)\in<_{P}\) but \((a,b)\
ot\in<_{P^{\prime}}\). With this, we have two further cases. 1. \((b,a)\in<_{P^{\prime}}\) In this case, \(Y_{1}=\mathcal{L}(P)\) and \(Y_{2}=\mathcal{L}(P^{\prime})\). Hence, posets \(P_{1}=P\) and \(P_{2}=P^{\prime}\) can be generated in Lines 5 and 6, respectively and are returned in Line 8. 2. \((b,a)\
ot\in<_{P^{\prime}}\) In this case, \(a||_{P^{\prime}}b\). Hence, there exist linear extensions of \(P^{\prime}\) where \(a<b\) and linear extensions where \(b>a\). Let \(E=\{L\in\mathcal{L}(P^{\prime})|a<_{L}b\}\) and \(F=\{L\in\mathcal{L}(P^{\prime})|b<_{L}a\}\). This implies that \(Y_{1}=\mathcal{L}(P)\cup E\) and \(Y_{2}=F\).