Document Type


Publication Date



It is already known that the 1-Poset and 2-Poset Cover Problems are in P. In this paper, we extended the previous results and devised an algorithm for the k-Poset Cover Problem, for any k number of posets that cover the input. The algorithm runs in O(m2k n2), where m and n 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 k but runs exponentially for large k. While the algorithm running time has yet not to be efficient for large k, we have shown a significant improvement from a brute-force solution, which runs in (Formula Presented) exponential even for small fixed k.

Included in

Mathematics Commons