2026-08-16T21:58:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12263 2024-03-06T10:49:28Z ddc:004 open_access

Parameterized Complexity of Two-Interval Pattern Problem Bose, Prosenjit Mehrabi, Saeed Mondal, Debajyoti Interval graphs Two-interval pattern problem Comparability Multicoloured clique problem Parameterized complexity W[1]-hardness A 2-interval is the union of two disjoint intervals on the real line. Two 2-intervals D₁ and D₂ are disjoint if their intersection is empty (i.e., no interval of D₁ intersects any interval of D₂). There can be three different relations between two disjoint 2-intervals; namely, preceding (<), nested (⊏) and crossing (≬). Two 2-intervals D₁ and D₂ are called R-comparable for some R∈{<,⊏,≬}, if either D₁RD₂ or D₂RD₁. A set 𝒟 of disjoint 2-intervals is ℛ-comparable, for some ℛ⊆{<,⊏,≬} and ℛ≠∅, if every pair of 2-intervals in ℛ are R-comparable for some R∈ℛ. Given a set of 2-intervals and some ℛ⊆{<,⊏,≬}, the objective of the {2-interval pattern problem} is to find a largest subset of 2-intervals that is ℛ-comparable. The 2-interval pattern problem is known to be W[1]-hard when |ℛ|=3 and NP-hard when |ℛ|=2 (except for ℛ={<,⊏}, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing that it is W[1]-hard for both ℛ={⊏,≬} and ℛ={<,≬} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette [Encyclopedia of Algorithms, 2008]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose and Saeed Mehrabi and Debajyoti Mondal 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.16 urn:nbn:de:0030-drops-122630 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode