Exploiting hidden structure in selecting dimensions that distinguish vectors. Froese, V., van Bevern, R., Niedermeier, R., & Sorge, M. Journal of Computer and System Sciences, 82(3):521–535, 2016.
Exploiting hidden structure in selecting dimensions that distinguish vectors [link]Preprint  doi  abstract   bibtex   
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