Exploiting hidden structure in selecting dimensions that distinguish vectors. Froese, V., , Niedermeier, R., & Sorge, M. Journal of Computer and System Sciences, 82(3):521–535, 2016.
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.
@article{FBNS16,
title =	 {Exploiting hidden structure in selecting dimensions
that distinguish vectors},
author =	 {Vincent Froese and René van Bevern and Rolf
Niedermeier and Manuel Sorge},
url_Preprint = {http://arxiv.org/abs/1512.01150},
doi =		 {10.1016/j.jcss.2015.11.011},
issn =	 {0022-0000},
year =	 2016,
date =	 {2016-05-01},
journal =	 {Journal of Computer and System Sciences},
volume =	 82,
number =	 3,
pages =	 {521--535},
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.}
}
Downloads: 0