文章基本信息

标题：Parameterized Algorithms for Matrix Completion with Radius Constraints
本地全文：下载
作者：Tomohiro Koana ; Vincent Froese ; Rolf Niedermeier 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：20:1-20:14
DOI：10.4230/LIPIcs.CPM.2020.20
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：fixed-parameter tractability; consensus string problems; Closest String; Closest String with Wildcards