Parameterized Algorithm for the Poset Cover Problem

Authors

Ivy D. Ordanel, University of the Philippines Diliman, College of Engineering
Proceso L. Fernandez, Ateneo de Manila University
Richelle Ann B. Juayong, University of the Philippines Diliman, College of Engineering
Jhoirene B. Clemente, University of the Philippines Diliman, College of Engineering
Henry N. Adorna, University of the Philippines Diliman, College of Engineering

Document Type

Article

Publication Date

2-1-2024

Abstract

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.

Recommended Citation

Ordanel I et al. 2024. Parameterized Algorithm for the Poset Cover Problem. Philipp J Sci 153(1): 23–32.