  Considering matrices with missing entries, we study NP-hard matrix completion
problems where the resulting completed matrix shall 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 parameterized complexity
studies 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 upper running time 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.
