Approximation and Computational Complexity of Some Hammock Variations of the Poset Cover Problem

• Main Authors: Ordanel, Ivy, Fernandez, Proceso L, Jr, Juayong, Richelle Ann B, Adorna, Henry N
• Format: text
• Published: Archīum Ateneo 2020
• Subjects: algorithm; approximation; complexity; partial order; poset; Computer Sciences; Databases and Information Systems; Mathematics
• Online Access: https://archium.ateneo.edu/discs-faculty-pubs/280; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1275&context=discs-faculty-pubs
• Institution: Ateneo De Manila University

The Hammock(⏟ , , … , / )-Poset Cover Problem is a variation of the Poset Cover Problem with the same input – set { , , … , } of linear orders over the set { , , … , }, but the solution is restricted to a set of simple hammock( ⏟, , … , / ) posets. The problem is NP-Hard when ≥ but is in when = . The computational complexity of the problem when = 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, ( + / )-approximable, for ≥ . On the other hand, we also explore the computational complexity for the case where = [Hammock(2,2)-Poset Cover Problem]. We show that it is in when the transposition graph of the input set of linear orders is rectangular