Koana, Tomohiro ;
Froese, Vincent ;
Niedermeier, Rolf
Binary Matrix Completion Under Diameter Constraints
Abstract
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that the resulting matrix has a specified maximum diameter (that is, upperbounding the maximum Hamming distance between any two rows of the completed matrix) as well as a specified minimum Hamming distance between any two of the matrix rows. This scenario is closely related to consensus string problems as well as to recently studied clustering problems on incomplete data.
We obtain an almost complete picture concerning the complexity landscape (P vs NP) regarding the diameter constraints and regarding the number of missing entries per row of the incomplete matrix. We develop polynomialtime algorithms for maximum diameter three, which are based on Deza’s theorem [Discret. Math. 1973, J. Comb. Theory, Ser. B 1974] from extremal set theory. In this way, we also provide one of the rare links between sunflower techniques and stringology. On the negative side, we prove NPhardness for diameter at least four. For the number of missing entries per row, we show polynomialtime solvability when there is only one missing entry and NPhardness when there can be at least two missing entries. In general, our algorithms heavily rely on Deza’s theorem and the correspondingly identified sunflower structures pave the way towards solutions based on computing graph factors and solving 2SAT instances.
BibTeX  Entry
@InProceedings{koana_et_al:LIPIcs.STACS.2021.47,
author = {Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf},
title = {{Binary Matrix Completion Under Diameter Constraints}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {47:147:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13692},
URN = {urn:nbn:de:0030drops136925},
doi = {10.4230/LIPIcs.STACS.2021.47},
annote = {Keywords: sunflowers, binary matrices, Hamming distance, stringology, consensus problems, complexity dichotomy, combinatorial algorithms, graph factors, 2Sat, Hamming radius}
}
10.03.2021
Keywords: 

sunflowers, binary matrices, Hamming distance, stringology, consensus problems, complexity dichotomy, combinatorial algorithms, graph factors, 2Sat, Hamming radius 
Seminar: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Issue date: 

2021 
Date of publication: 

10.03.2021 