Exploiting hidden structure in selecting dimensions that distinguish vectors

DOI10.1016/J.JCSS.2015.11.011zbMATH Open1333.68143arXiv1512.01150OpenAlexW2191737685MaRDI QIDQ899584FDOQ899584

Authors: Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge 

Publication date: 30 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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 ceil(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.

Full work available at URL: https://arxiv.org/abs/1512.01150

Recommendations

• A double exponential lower bound for the distinct vectors problem
• A parameterized complexity analysis of combinatorial feature selection problems
• Approximability and exact resolution of the multidimensional binary vector assignment problem
• Approximability and exact resolution of the multidimensional binary vector assignment problem
• A new algorithm for finding closest pair of vectors (extended abstract)

zbMATH Keywords

dimension reductionmachine learningfixed-parameter tractabilityNP-hardnessW-hardness\(\Delta\)-systemscombinatorial feature selectioncombinatorics of binary matricesminimal reduct problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Selection of relevant features and examples in machine learning
• 10.1162/153244303322753616
• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• 10.1162/153244303322753670
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized complexity of finding regular induced subgraphs
• Parametrized complexity theory.
• Title not available (Why is that?)
• Parameterized algorithms
• Digraphs
• Title not available (Why is that?)
• Structure preserving reductions among convex optimization problems
• Kernelization lower bounds through colors and IDs
• Extremal combinatorics. With applications in computer science
• Title not available (Why is that?)
• Tight lower bounds for certain parameterized NP-hard problems
• On distance-3 matchings and induced matchings
• Towards optimal and expressive kernelization for \(d\)-hitting set
• The \(k\)-feature set problem is \(W[2]\)-complete
• Title not available (Why is that?)
• On explaining integer vectors by few homogeneous segments
• A parameterized complexity analysis of combinatorial feature selection problems

Cited In (6)

• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• The complexity of dependency detection and discovery in relational databases
• A double exponential lower bound for the distinct vectors problem
• Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
• Title not available (Why is that?)
• The complexity of binary matrix completion under diameter constraints

This page was built for publication: Exploiting hidden structure in selecting dimensions that distinguish vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899584)