# The Complexity of Binary Matrix Completion Under Diameter Constraints

arXiv: https://arxiv.org/abs/2002.05068 · HTML: https://mlsanity.com/paper/2002.05068/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2020.

## Built on by (most cited first, 2 of 2)

- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)
- [Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity](https://mlsanity.com/paper/2512.03718/) (2025)

## Abstract (arXiv)

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.