Document Open Access Logo

Parameterized Complexity of Two-Interval Pattern Problem

Authors Prosenjit Bose, Saeed Mehrabi, Debajyoti Mondal

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.16.pdf
  • Filesize: 0.78 MB
  • 10 pages

Document Identifiers

Author Details

Prosenjit Bose
  • School of Computer Science, Carleton University, Ottawa, Canada
Saeed Mehrabi
  • School of Computer Science, Carleton University, Ottawa, Canada
Debajyoti Mondal
  • Department of Computer Science, University of Saskatchewan, Saskatoon, Canada

Funding

The work is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).

Cite As Get BibTex

Prosenjit Bose, Saeed Mehrabi, and Debajyoti Mondal. Parameterized Complexity of Two-Interval Pattern Problem. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 16:1-16:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.16

Abstract

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].

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Interval graphs
  • Two-interval pattern problem
  • Comparability
  • Multicoloured clique problem
  • Parameterized complexity
  • W[1]-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, and Irina Shapira. Scheduling split intervals. SIAM J. Comput., 36(1):1-15, 2006. Google Scholar
  2. Guillaume Blin, Guillaume Fertin, and Stéphane Vialette. New results for the 2-interval pattern problem. In proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM 2004), Istanbul,Turkey, pages 311-322, 2004. Google Scholar
  3. Erdong Chen, Linji Yang, and Hao Yuan. Improved algorithms for largest cardinality 2-interval pattern problem. J. Comb. Optim., 13(3):263-275, 2007. Google Scholar
  4. Jih-H. Chen, Shu-Yun Le, and Jacob V. Maizel. Prediction of common secondary structures of RNAs: a genetic algorithm approach. Nucleic Acids Research, 28(4):991-999, 2000. Google Scholar
  5. Maxime Crochemore, Danny Hermelin, Gad M. Landau, Dror Rawitz, and Stéphane Vialette. Approximating the 2-interval pattern problem. Theor. Comput. Sci., 395(2-3):283-297, 2008. Google Scholar
  6. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  7. Minghui Jiang. A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem. J. Comb. Optim., 13(3):217-221, 2007. Google Scholar
  8. Minghui Jiang. A PTAS for the weighted 2-interval pattern problem over the preceding-and-crossing model. In proceedings of the First International Conference on Combinatorial Optimization and Applications (COCOA 2007), Xi'an, China, pages 378-387, 2007. Google Scholar
  9. Shuai Cheng Li and Ming Li. On two open problems of 2-interval patterns. Theor. Comput. Sci., 410(24-25):2410-2423, 2009. Google Scholar
  10. Jihong Ren, Baharak Rastegari, Anne Condon, and Holger H. Hoos. HotKnots: Heuristic prediction of RNA secondary structure including pseudoknots. RNA, 11:1194-1504, 2005. Google Scholar
  11. Elena Rivas and Sean R. Eddy. A dynamic programming algorithm for rna structure prediction including pseudoknots. J. of Molecular Biology, 285(5):2053-2068, 1999. Google Scholar
  12. Jianhua Ruan, Gary D. Stormo, and Weixiong Zhang. An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots. Bioinformatics, 20(1):58-66, 2004. Google Scholar
  13. Stéphane Vialette. Combinatorial pattern matching, 13th annual symposium, CPM 2002, fukuoka, japan, july 3-5, 2002, proceedings. In Alberto Apostolico and Masayuki Takeda, editors, Combinatorial Pattern Matching, 13th Annual Symposium, CPM 2002, Fukuoka, Japan, July 3-5, 2002, Proceedings, volume 2373 of Lecture Notes in Computer Science, pages 53-63. Springer, 2002. Google Scholar
  14. Stéphane Vialette. On the computational complexity of 2-interval pattern matching problems. Theor. Comput. Sci., 312(2-3):223-249, 2004. Google Scholar
  15. Stéphane Vialette. Two-interval pattern problems. In Encyclopedia of Algorithms - 2008 Edition. Springer, 2008. Google Scholar
  16. Jizhen Zhao, Russell L. Malmberg, and Liming Cai. Rapid ab initio folding including pseudoknots via graph tree decomposition. In proceedings of the sixth International Workshop on Algorithms in Bioinformatics (WABI 2006), Zurich, Switzerland, pages 262-273, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact