Exploiting hidden structure in selecting dimensions that distinguish vectors

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.

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

{"_id":"tX6Cugn7iaJ56LC2o","bibbaseid":"froese-vanbevern-niedermeier-sorge-exploitinghiddenstructureinselectingdimensionsthatdistinguishvectors-2016","downloads":0,"creationDate":"2016-03-07T11:48:39.118Z","title":"Exploiting hidden structure in selecting dimensions that distinguish vectors","author_short":["Froese, V.","van Bevern, R.","Niedermeier, R.","Sorge, M."],"year":2016,"bibtype":"article","biburl":"http://rvb.su/rvb.bib","bibdata":{"bibtype":"article","type":"article","title":"Exploiting hidden structure in selecting dimensions that distinguish vectors","author":[{"firstnames":["Vincent"],"propositions":[],"lastnames":["Froese"],"suffixes":[]},{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]},{"firstnames":["Manuel"],"propositions":[],"lastnames":["Sorge"],"suffixes":[]}],"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.","bibtex":"@article{FBNS16,\n title =\t {Exploiting hidden structure in selecting dimensions\n that distinguish vectors},\n author =\t {Vincent Froese and René van Bevern and Rolf\n Niedermeier and Manuel Sorge},\n url_Preprint = {http://arxiv.org/abs/1512.01150},\n doi =\t\t {10.1016/j.jcss.2015.11.011},\n issn =\t {0022-0000},\n year =\t 2016,\n date =\t {2016-05-01},\n journal =\t {Journal of Computer and System Sciences},\n volume =\t 82,\n number =\t 3,\n pages =\t {521--535},\n abstract =\t {The NP-hard Distinct Vectors problem asks to delete\n as many columns as possible from a matrix such that\n all rows in the resulting matrix are still pairwise\n distinct. Our main result is that, for binary\n matrices, there is a complexity dichotomy for\n Distinct Vectors based on the maximum (H) and the\n minimum (h) pairwise Hamming distance between matrix\n rows: Distinct Vectors can be solved in polynomial\n time if H≤2⌈h/2⌉+1, and is NP-complete\n otherwise. Moreover, we explore connections of\n Distinct Vectors to hitting sets, thereby providing\n several fixed-parameter tractability and\n intractability results also for general matrices.}\n}\n\n","author_short":["Froese, V.","van Bevern, R.","Niedermeier, R.","Sorge, M."],"key":"FBNS16","id":"FBNS16","bibbaseid":"froese-vanbevern-niedermeier-sorge-exploitinghiddenstructureinselectingdimensionsthatdistinguishvectors-2016","role":"author","urls":{" preprint":"http://arxiv.org/abs/1512.01150"},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}}},"search_terms":["exploiting","hidden","structure","selecting","dimensions","distinguish","vectors","froese","van bevern","niedermeier","sorge"],"keywords":[],"authorIDs":["2fwXJtKDCNhaSNr5s","56dd6a97e8d527c5470000fa"],"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}