Philippine Journal of Science
153 (1): 23-32, February 2024
ISSN 0031 – 7683
Date Received: 31 Jan 2022

Parameterized Algorithm for the Poset Cover Problem

Ivy D. Ordanel1*, Proceso L. Fernandez Jr.2, Richelle Ann B. Juayong1, Jhoirene B. Clemente1, and Henry N. Adorna1

1Department of Computer Science, College of Engineering, University of the Philippines Diliman, Quezon City 1101 Philippines 2Department of Information Systems and Computer Science, Ateneo De Manila University, Quezon City 1108 Philippines

*Corresponding author: idordanel@up.edu.ph

[Download]

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

ABSTRACT

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 οΏ½