# On Finding Two Posets that Cover Given Linear Orders
## 5 Algorithm for the 2-Tree-Poset Cover Problem  
From Theorem 2, the part of Algorithm 1 that makes its running-time exponential is determining the latter components of Equations (3) or (4). However, with Corollary 1, the said components become simpler if the posets are tree-posets. Hence, we can then modify Algorithm 1 to specifically consider only tree-posets. The resulting algorithm is Algorithm 2. Consequently, the running time of the algorithm becomes polynomial. With these results, we can then say that the 2-Tree-Poset Cover Problem is in P.  
Algorithm 2 produces a solution to the 2-Tree-Poset Cover Problem in \(O(n^{5}+mn^{4}+m^{2})\).  
The theoretical bases of Algorithm 2 is the same as Algorithm 1 for the 2-Poset Cover Problem except that we use Equations (5) and (6) for tree-posets as given in Corollary 1 instead of Equations (3) and (4) for general posets. Consequently, the running time then of the Algorithm differs on the following points.  
1. \(B\) is empty and there is only one element in \(A\) that could cover \(v\) or \(u\). This follows from Corollary 1. Hence, \(|A|=O(n)\)
2. There is a need to check if the poset is a tree-poset. This can be done in \(O(n^{2})\)  
Hence, the inner for-loops runs in \(O(n(mn+n^{2}))=O(mn^{2}+n^{3})\). The first outermost for-loop then run in \(O(n^{2}(mn^{2}+n^{3}))=O(mn^{4}+n^{5})\). The running time of the second-outermost for loop remains the same, i.e., \(O(m^{2})\). The running time then of the algorithm is \(O(n^{5}+mn^{4}+m^{2})\).  
```
Input: A set \(\mathrm{Y}=\{L_{1},L_{2},...,L_{m}\}\) of linear orders on \(V=\{1,2,...,n\}\) Output: A pair of tree-poses \(\{P,P^{\prime}\}\), \(P\
eq P^{\prime}\) where \(\mathcal{L}(P)\cup\mathcal{L}(P^{\prime})=\mathrm{Y}\) and \(\mathcal{L}(P)\) is neither a subset nor a superset of \(\mathcal{L}(P^{\prime})\), if there exist such.
1\(P^{*}:=\emptyset\)for each pair \((a,b)\in V\times V\)do
2\(\mathrm{Y}_{1}:=\{L\in\mathrm{Y}|a<_{L}b\}\)\(\mathrm{Y}_{2}:=\{L\in\mathrm{Y}|b<_{L}a\}\)\(\mathrm{P}_{1}:=\mathrm{GeneratePoset(Y_{1})}\)\(\mathrm{P}_{2}:=\mathrm{GeneratePoset(Y_{2})}\)if\(P_{1}\
eq null\) and \(P_{2}\
eq null\)then
3 if\(P_{1}\) is a tree and \(P_{2}\) is a treethen
4 return\(\{P_{1},P_{2}\}\)
5 elseif\(P_{1}\
eq null\)then
6\(P_{3}:=(V,<_{P_{3}})\) where \(\prec_{P_{3}}=\prec_{P_{1}}\setminus\{(a,b)\}\)if\(\mathcal{L}(P_{3})\subset\mathrm{Y}\) and \(P_{3}\) is a treethen
7\(P^{*}:=P^{*}\cup\{P_{3}\}\)
8 else
9\(A:=\{u\in V|u<_{P_{3}}a\}\)for each \(u\in A\)do
10\(P_{3}:=(V,<_{P_{3}})\prec_{P_{3}}=\prec_{P_{1}}\setminus\{(a,b)\}\cup\{(u,b)\}\)if\(\mathcal{L}(P_{3})\subset\mathrm{Y}\) and \(P_{3}\) is a treethen
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 Y\) and \(P_{3}\) is a treethen
15\(P^{*}:=P^{*}\cup\{P_{3}\}\)
16 else
17\(A:=\{u\in V|u<_{P_{3}}b\}\)for each each \(u\in A\)do
18\(P_{3}:=(V,<_{P_{3}})\) where \(\prec_{P_{3}}=\prec_{P_{2}}\setminus\{(b,a)\}\cup\{(u,a)\}\)if\(\mathcal{L}(P_{3})\subset\mathrm{Y}\) and \(P_{3}\) is a treethen
19\(P^{*}:=P^{*}\cup\{P_{3}\}\)
20
21 for each \(P_{i},P_{j}\in P^{*}\), \(P_{i}\
eq P_{j}\)do
22 ift\(\mathcal{L}(P_{i})\cup\mathcal{L}(P_{j})=\mathrm{Y}\)then
23 return\(\{P_{i},P_{j}\}\)
24 returnnull
```  
**Algorithm 2**2-Tree-Poset Cover Algorithm