论文标题
直径约束下二进制矩阵完成的复杂性
The Complexity of Binary Matrix Completion Under Diameter Constraints
论文作者
论文摘要
我们彻底研究了一个新颖但基本的组合矩阵完成问题：鉴于二进制不完整的矩阵，填写缺失的条目，以使所得矩阵中的每一行都具有指定范围内的锤子距离。我们几乎完整地了解了有关距离约束和任何行中缺失条目的最大数量的复杂性格局。我们根据Deza定理[DISTEVET开发最大直径三的多项式算法。数学。 [1973]来自极端集理论。我们还证明直径至少四个。对于每行缺失的条目的数量，我们在至少有两个时只有一个和np硬度时显示多项式时间的求解性。在许多算法中，我们在很大程度上依赖Deza定理来识别向日葵结构。这为多项式时间算法铺平了道路，该算法基于查找图形因素和求解2个SAT实例。
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.
