Document Open Access Logo

Parameterized Algorithms for Matrix Completion with Radius Constraints

Authors Tomohiro Koana , Vincent Froese, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.CPM.2020.20.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Tomohiro Koana
  • Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany
Vincent Froese
  • Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany
Rolf Niedermeier
  • Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany

Funding

  • Koana, Tomohiro: Partially supported by the DFG project MATE (NI 369/17).

Acknowledgements

We are grateful to Christian Komusiewicz for helpful feedback on an earlier version of this work and to Stefan Szeider for pointing us to reference [Eduard Eiben et al., 2019].

Cite As Get BibTex

Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Parameterized Algorithms for Matrix Completion with Radius Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CPM.2020.20

Abstract

Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix should have limited (local) radius. In the pure radius version, this means that the goal is to fill in the entries such that there exists a "center string" which has Hamming distance to all matrix rows as small as possible. In stringology, this problem is also known as Closest String with Wildcards. In the local radius version, the requested center string must be one of the rows of the completed matrix.
Hermelin and Rozenberg [CPM 2014, TCS 2016] performed a parameterized complexity analysis for Closest String with Wildcards. We answer one of their open questions, fix a bug concerning a fixed-parameter tractability result in their work, and improve some running time upper bounds. For the local radius case, we reveal a computational complexity dichotomy. In general, our results indicate that, although being NP-hard as well, this variant often allows for faster (fixed-parameter) algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Pattern matching
Keywords
  • fixed-parameter tractability
  • consensus string problems
  • Closest String
  • Closest String with Wildcards

Metrics

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

References

  1. Amihood Amir, Jessica Ficler, Liam Roditty, and Oren Sar Shalom. On the efficiency of the Hamming c-centerstring problems. In 25th Symposium on Combinatorial Pattern Matching (CPM '14), pages 1-10. Springer, 2014. Google Scholar
  2. Christina Boucher and Bin Ma. Closest string with outliers. BMC Bioinformatics, 12(S-1):S55, 2011. Google Scholar
  3. Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems. Bulletin of the EATCS, 114, 2014. Google Scholar
  4. Zhi-Zhong Chen, Bin Ma, and Lusheng Wang. A three-string approach to the closest string problem. Journal of Computer and System Sciences, 78(1):164-178, 2012. Google Scholar
  5. Zhi-Zhong Chen, Bin Ma, and Lusheng Wang. Randomized fixed-parameter algorithms for the closest string problem. Algorithmica, 74(1):466-484, 2016. Google Scholar
  6. Zhi-Zhong Chen and Lusheng Wang. Fast exact algorithms for the closest string and substring problems with application to the planted (𝓁, d)-motif model. IEEE/ACM Transactions Computational Biology and Bioinformatics, 8(5):1400-1410, 2011. Google Scholar
  7. Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. On clustering incomplete data. CoRR, abs/1911.01465, 2019. URL: http://arxiv.org/abs/1911.01465.
  8. Moti Frances and Ami Litman. On covering problems of codes. Theory of Computing Systems, 30(2):113-119, 1997. Google Scholar
  9. Robert Ganian, Iyad A. Kanj, Sebastian Ordyniak, and Stefan Szeider. Parameterized algorithms for the matrix completion problem. In 35th International Conference on Machine Learning (ICML '18), volume 80 of Proceedings of Machine Learning Research, pages 1642-1651. PMLR, 2018. Google Scholar
  10. Jens Gramm, Jiong Guo, and Rolf Niedermeier. Parameterized intractability of distinguishing substring selection. Theory of Computing Systems, 39(4):545-560, 2006. Google Scholar
  11. Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Fixed-parameter algorithms for closest string and related problems. Algorithmica, 37(1):25-42, 2003. Google Scholar
  12. Danny Hermelin and Liat Rozenberg. Parameterized complexity analysis for the closest string with wildcards problem. Theoretical Computer Science, 600:11-18, 2015. Preliminary version appeared at CPM '14. Google Scholar
  13. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold integer programming and applications. Mathematical Programming, 2019. Google Scholar
  14. Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Complexity of combinatorial matrix completion with diameter constraints. CoRR, abs/2002.05068, 2020. URL: http://arxiv.org/abs/2002.05068.
  15. Ming Li, Bin Ma, and Lusheng Wang. Finding similar regions in many sequences. Journal of Computer and System Sciences, 65(1):73-96, 2002. Google Scholar
  16. Ming Li, Bin Ma, and Lusheng Wang. On the closest string and substring problems. Journal of the ACM, 49(2):157-171, 2002. Google Scholar
  17. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM Journal on Computing, 47(3):675-702, 2018. Google Scholar
  18. Bin Ma and Xiaoming Sun. More efficient algorithms for closest string and substring problems. SIAM Journal on Computing, 39(4):1432-1443, 2009. Google Scholar
  19. Naomi Nishimura and Narges Simjour. Enumerating neighbour and closest strings. In 7th International Symposium on Parameterized and Exact Computation (IPEC '12), pages 252-263. Springer, 2012. Google Scholar
  20. Carsten Sinz. Towards an optimal CNF encoding of boolean cardinality constraints. In 11th International Conference on Principles and Practice of Constraint Programming (CP '05), pages 827-831. Springer, 2005. Google Scholar
  21. Lusheng Wang and Binhai Zhu. Efficient algorithms for the closest string and distinguishing string selection problems. In 3rd International Frontiers in Algorithmics Workshop (FAW '09), pages 261-270. Springer, 2009. Google Scholar
  22. Shota Yuasa, Zhi-Zhong Chen, Bin Ma, and Lusheng Wang. Designing and implementing algorithms for the closest string problem. Theoretical Computer Science, 786:32-43, 2019. 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