# On Finding Two Posets that Cover Given Linear Orders
## 4 Algorithm for the 2-Poset Cover Problem
Let \(P_{1}\) and \(P_{2}\) be the return of GeneratePoset for \(Y_{1}\) and \(Y_{2}\) in Lines 4 and 5, respectively. We know that \(P_{2}\) is not null because from Theorem 1 there exists a poset that covers \(Y_{2}\). Moreover, we can also reconstruct \(P^{\prime}\) from \(P_{2}\) using Equation (4), i.e., \(\prec_{P^{\prime}}=\prec_{P_{2}}\setminus\{(b,a)\}\cup\{C\cup D\}\) where \(C=\{(u,a)\in\prec_{P^{\prime}}|u<_{P^{\prime}}b\}\) and \(D=\{(b,v)\in\prec_{P^{\prime}}|a<_{P^{\prime}}v\}\). In reconstructing \(P^{\prime}\) from \(P_{2}\), let \(P_{3}\) be our working poset. First, we let \(\prec_{P_{3}}=\prec_{P^{\prime}}\setminus\{(b,a)\}\) and if \(\mathcal{L}(P_{3})\subset Y\), then we can already disregard the components \(\{C\cup D\}\) of \(\prec_{P^{\prime}}\). This is because \(\prec_{P_{2}}\setminus\{(b,a)\}\subset\prec_{P_{2}}\setminus\{(b,a)\}\cup\{C \cup D\}\). With Lemma 1, whatever set of linear orders that are covered by the poset with the later cover relation can be already covered by the poset with theformer cover relation. These are executed with the \"If\" condition in Lines 23-24. Otherwise (the else part), we have to determine \(C\) and \(D\). However, in the Algorithm, what we have only generated and know is the relation of \(P_{2}\). We do not know \(P^{\prime}\) yet hence we also do not know \(C\) and \(D\). However, we know that \(C\subseteq\{(u,b)\in<_{P^{\prime}}\}\) and \(D\subseteq\{(a,v)\in<_{P^{\prime}}\}\), and with Equation (2), \((u,b)\in<_{P_{2}}\) and \((a,v)\in<_{P_{2}}\). Hence, \(C\subseteq A\) where \(A=\{(u,b)\in<_{P_{2}}\}\) and \(D\subseteq B\) where \(B=\{(a,v)\in<_{P_{2}}\}\). Hence, we can try all possible subsets of \(A\) and \(B\) for \(\prec_{P_{3}}\). This is what we have done in Lines 26-32. Every possible poset from each combination is a candidate poset and added to \(P^{*}\). ```
Input: A set \(\Upsilon=\{L_{1},L_{2},...,L_{m}\}\) of linear orders on \(V=\{1,2,...,n\}\) Output: A pair of posets \(\{P,P^{\prime}\}\), \(P\
eq P^{\prime}\) where \(\mathcal{L}(P)\cup\mathcal{L}(P^{\prime})=\Upsilon\) and \(\mathcal{L}(P)\) is neither a subset nor a superset of \(\mathcal{L}(P^{\prime})\), if there exist such. 1\(P^{*}:=\emptyset\)foreach pair \((a,b)\in V\times V\)do
2\(\Upsilon_{1}:=\{L\in\Upsilon|a<_{L}b\}\)\(\Upsilon_{2}:=\{L\in\Upsilon|b<_{L}a\}\)\(\Upsilon_{1}:=\)GeneratePoset(\(\Upsilon_{1}\))\(P_{2}:=\)GeneratePoset(\(\Upsilon_{2}\)) if\(P_{1}\
eq null\) and \(P_{2}\
eq null\)return\(\{P_{1},P_{2}\}\)
3 elseif\(P_{1}\
eq null\)then
4\(P_{3}:=(V,<_{P_{3}})\) where \(\prec_{P_{3}}=\prec_{P_{1}}\setminus\{(a,b)\}\)if\(\mathcal{L}(P_{3})\subset\Upsilon\)then
5\(P^{*}:=P^{*}\cup\{P_{3}\}\)
6 else
7\(A:=\{u\in V|u<_{P_{1}}a\}\)\(B:=\{v\in V|b<_{P_{1}}v\}\)
8 forach\(C\subseteq A\)do
9 forach\(D\subseteq B\)do
10\(P_{3}:=(V,<_{P_{3}})\) where \(\prec_{P_{3}}=\prec_{P_{1}}\setminus\{(a,b)\}\cup\{\{(c,a)|c\in C\}\cup\{(b,d)| d\in D\}\}\)if\(\mathcal{L}(P_{3})\subset\Upsilon\)then
11\(P^{*}:=P^{*}\cup\{P_{3}\}\)
12
13 elseif\(P_{2}\
eq null\)then
14\(P_{3}:=(V,<_{P_{3}})\) where \(\prec_{P_{3}}=\prec_{P_{2}}\setminus\{(b,a)\}\)if\(\mathcal{L}(P_{3})\subset\Upsilon\)then
15\(P^{*}:=P^{*}\cup\{P_{3}\}\)
16 else
17\(A:=\{u\in V|u<_{P_{1}}b\}\)\(B:=\{v\in V|a<_{P_{1}}v\}\)
18 forach\(C\subseteq A\)do
19 forach\(D\subseteq B\)do
20\(P_{3}:=(V,<_{P_{3}})\) where \(\prec_{P_{3}}=\prec_{P_{2}}\setminus\{(b,a)\}\cup\{\{(c,a)|c\in C\}\cup\{(b,d)| d\in D\}\}\)if\(\mathcal{L}(P_{3})\subset\Upsilon\)then
21\(P^{*}:=P^{*}\cup\{P_{3}\}\)
22
23 forach\(P_{i},P_{j}\in P^{*},P_{i}\
eq P_{j}\)do
24 if\(\mathcal{L}(P_{i})\cup\mathcal{L}(P_{j})=\Upsilon\)then
25 return\(\{P_{i},P_{j}\}\)
26 return\(\ null\)
```  
**Algorithm 1**2-Poset Cover Algorithm  
We can also do the same in determining \(P\) when the iteration evaluates the pair \((c,d)\) where \((c,d)\
otin<_{P}\) but \((c,d)\in<_{P^{\prime}}\). Lastly, to get \(P\) and \(P^{\prime}\) in \(P^{*}\), we can try all possible pairs of posets that exactly cover \(\Upsilon\) in Lines 33-35.