Search

It is already known that the 1-Poset and 2-Poset Cover Problems are in 𝑷. In this paper, we extended the previous results and devised an algorithm for the 𝒌-Poset Cover Problem, for any 𝒌 number of posets that cover the input. The algorithm runs in 𝑶(𝒎2k 𝒏2), where 𝒎 and 𝒏 are the input size. With this running time, we can say that the problem belongs to XP (slicewise polynomial). The algorithm runs efficiently for small fixed 𝒌 but runs exponentially for large 𝒌. While the algorithm running time has yet not to be efficient for large 𝒌, we have shown a significant improvement from a brute-force solution, which runs in 2𝒎 𝒏2 + 𝑶(􀷌𝒌 𝒊 􀰸 1 2𝒎𝒊𝒏) - exponential even for small fixed [ABSTRACT FROM AUTHOR]

The Hammock(2, 2 ,..., 2/k)-Poset Cover Problem is a variation of the Poset Cover Problem with the same input - set {L1, L2, ..., Lm} of linear orders over the set {1, 2, ..., n}, but the solution is restricted to a set of simple hammock(2, 2 ,..., 2/k) posets. The problem is NP-Hard when k = 3 but is in P when k = 1. The computational complexity of the problem when k = 2 is not yet known. In this paper, we determine the approximation complexity of the cases that have been shown to be NP-Hard. We show that the Hammock(2, 2 ,..., 2/k)-Poset Cover Problem is in APX and, in particular, (1 + 1/2K)-approximable, for k = 3. On the other hand, we also explore the computational complexity for the case where k = 2 [Hammock(2,2)-Poset Cover Problem]. We show that it is in P when the transposition graph of the input set of linear orders is rectangular. [ABSTRACT FROM AUTHOR]

The Hammock-Poset Cover Problem is a variation of the Poset Cover Problem with the same input - set (...) of linear orders over the set {L1, L2, ...,L3}, but the solution is restricted to a set of simple hammock (...) posets. The problem is NP-Hard when K ≥ 3 but is in P when k = 1. The computational complexity of the problem when k = 2 is not yet known. In this paper, we determine the approximation complexity of the cases that have been shown to be NP-Hard. We show that the Hammock (...)-Poset Cover Problem is in APX and, in particular, (1 + 1/2k)-approximable, for k ≥ 3. On the other hand, we also explore the computational complexity for the case where k = 2 [Hammock(2,2)-Poset Cover Problem]. We show that it is in P when the transposition graph of the input set of linear orders is rectangular. [ABSTRACT FROM AUTHOR]