## Vincent Froese, René van Bevern, Rolf Niedermeier, and Manuel Sorge.
Exploiting hidden structure in selecting dimensions that distinguish
vectors.
*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.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*