Exploiting hidden structure in selecting dimensions that distinguish vectors
Exploiting hidden structure in selecting dimensions that distinguish vectors
复制标题
DOI：
10.1016/j.jcss.2015.11.011
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Vincent Froese;René van Bevern;R. Niedermeier;Manuel Sorge
中科院分区：
文献类型：
--
作者：
Vincent Froese;René van Bevern;R. Niedermeier;Manuel Sorge
摘要NP-hard相异向量问题要求从矩阵中删除尽可能多的列，使得所得矩阵中的所有行仍然是两两相异的。我们的主要结果是，对于二元矩阵，存在基于矩阵行之间的最大（H）和最小（h）成对汉明距离的不同向量的复杂性二分法：如果H≤ 2 <$h/2 <$+ 1，则不同向量可以在多项式时间内求解，否则是NP完全的。此外，我们探讨不同的向量的连接，击中集，从而提供了几个固定参数的易处理性和棘手的结果也为一般矩阵。
Abstract The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum (H) and the minimum (h) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H≤ 2⌈ h/2⌉+ 1, and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices.