Ph.D. C.S. Thesis Defense: Ivy D. Ordanel (Algorithms and Complexity of Some Variants of the Poset Cover Problem)

Meeting ID: 852 7778 8877

Meeting Password: gsatdm2021

________________

Panel Members

Henry N. Adorna, Adviser

Jaime D.L. Caro, Panel Chairman

Proceso L. Fernandez, Jr., Reader

Marrick C. Neri, Member

Jan Michael C. Yap, Member

ABSTRACT

The Poset Cover Problem is an optimization problem where the goal is to determine a minimum set P∗ of posets that covers a given set Υ of linear orders. This problem is relevant in the field of data mining, specifically on determining directed networks that explain the ordering of objects in a large sequential dataset. The decision version of the Poset Cover Problem is NP-hard. In this study, we investigate the complexity of its variants using different deterministic approaches to hard problems. We show that the variant Exact k-Poset Cover Problem, where |P∗| = k and there exists no other smaller set of posets that covers Υ, is in P for any fixed k. The Hammock(a1, ... , ah)–Poset Cover Problem where ai = 2 for i = 1, ... , h, which is on determining a minimum set of hammock(a1, ... , ah) posets that covers the input is also known to be NP-hard for h ≥ 3 and in P for h = 1; the complexity for h = 2 is not yet known. In this study, we show that the more restricted variant of the problem when h = 2, which is called Rectangular Hammock(2,2)-Poset Cover Problem, is still in P. We also show that the NP-hard cases, that is when h ≥ 3, belong to APX class of optimization problems. Moreover, we also derived different properties on posets and their transposition graphs, efficient algorithms for some other variants and exponential algorithms which are still significantly better than brute force algorithms.