Sie sind hier

# Algorithmic and Structural Aspects of Matrix Completion Problems

Tomohiro Koana (TU Berlin)

We study combinatorial matrix completion problems, following the work of Eiben et al. [arXiv 2019] and Ganian et al. [ICMl 2018]. As input, we are given an incomplete matrix with n rows and l columns, in which values for some entries are unknown. The goal is to complete the missing entries so that the matrix fulfills some desired property. We consider the objective of minimizing radius (maximum distance to some vector),local radius (maximum distance to some vector in the matrix), or diameter (maximum pairwise distance) of the entire matrix. We call these problems Minimum Radius/Local Radius/Diameter Matrix Completion (MinRMC/MinLRMC/MinDMC). We examine the computational complexity of these matrix completion problems via a multivariate approach.

First, we tackle MinRMC and MinLRMC. The matrix completion problem is NP-hard even if the (local) radius d of the sought matrix is two [TCS 2016]. We provide polynomial-time algorithms for the case of d = 1, answering an open question of Hermelin and Rosenberg [TCS 2016]. Although MinRMC is NP-hard even if the matrix is complete, we show fixed-parameter tractability with respect to d + k, where k is such that each row vector contains at most k missing entries. Meanwhile, we show that MinLRMC is fixed-parameter tractable with respect to k alone.

Then, we study MinDMC. We obtain a complete dichotomy between tractable and intractable cases in terms of d and k for binary matrices. We develop polynomial-time algorithms for the case d ≤ 3, based on Deza's theorem from extremal set theory. On the negative side we prove the NP-hardness for the case d ≥ 4. For the parameter k, we show that MinDMC is polynomial-time solvable when k = 1 and NP-hard when k ≥ 2.


Date
Speaker
Location
Language
27.02.2020
16:00
Tomohiro Koana
TEL 512
English

Back to the research colloquium site.

To top