2020/02/12 by Koana, Tomohiro, Froese, Vincent, Niedermeier, Rolf · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2002.05068
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resulting matrix has a Hamming distance within a specified range. We obtain an almost complete picture of the complexity landscape regarding the distance constraints and the maximum number of missing entries in any row. We develop polynomial-time algorithms for maximum diameter three based on Deza's theorem [Discret. Math. 1973] from extremal set theory. We also prove NP-hardness for diameter at least four. For the number of missing entries per row, we show polynomial-time solvability when there is only one and NP-hardness when there can be at least two. In many of our algorithms, we heavily rely on Deza's theorem to identify sunflower structures. This paves the way towards polynomial-time algorithms which are based on finding graph factors and solving 2-SAT instances.