Philippine Journal of Science
149 (1): 201-211, March 2020
ISSN 0031 – 7683
Date Received: 22 Oct 2019

 

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

 

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

 

1Department of Computer Science,
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: ivyordanel@gmail.com

 

[Download]
Ordanel I et al. 2020. Approximation and Computational Complexity of Some
Hammock Variations of the Poset Cover Problem. Philipp J Sci 149(1): 201–211.
https://doi.org/10.56899/149.01.20

 

ABSTRACT

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