文章基本信息

标题：Parameterized Complexity of Two-Interval Pattern Problem
本地全文：下载
作者：Prosenjit Bose ; Saeed Mehrabi ; Debajyoti Mondal 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：16:1-16:10
DOI：10.4230/LIPIcs.SWAT.2020.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 (âS) and crossing (â¬). Two 2-intervals Dâ, and Dâ,, are called R-comparable for some Râ^^{<,âS,â¬}, if either Dâ,RDâ,, or Dâ,,RDâ,. A set ð'Y of disjoint 2-intervals is â">-comparable, for some â">âS{<,âS,â¬} and â">â â^., if every pair of 2-intervals in â"> are R-comparable for some Râ^^â">. Given a set of 2-intervals and some â">âS{<,âS,â¬}, 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 â">={<,âS}, 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 â">={âS,â¬} and â">={<,â¬} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette [Encyclopedia of Algorithms, 2008].
关键词：Interval graphs; Two-interval pattern problem; Comparability; Multicoloured clique problem; Parameterized complexity; W[1]-hardness