Approximation and computational complexity of some hammock variations of the poset cover problem - Ordanel, Ivy D.; Fernandez Jr., Proceso L.; Juayong, Richelle Ann B.; Adorna, Henry N. (2020)
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 𝑨𝑨𝑨𝑨𝑨𝑨 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. (Author's abstract)
Includes bibliographical references (page 211)
Keywords: Algorithm; Approximation; Complexity; Poset