Сокращение от Vertex Cover до LP
Я хочу свести проблему покрытия вершин к конкретной проблеме решения. Это решение проблемы заключается в следующем:
У меня есть nxn матрица A, вектор b в R^n и положительное целое число k. Существует ли в R^n вектор x, содержащий не более k ненулевых элементов, такой, что A*x больше или равно b?
Я думал, что A можно рассматривать как матрицу смежности, но я не уверен, как свести проблему покрытия вершин к этой проблеме.
Может кто-нибудь дать мне подсказку или два о том, что мне делать дальше?
РЕДАКТИРОВАТЬ ** Первоначально я думал об использовании проблемы доминирующего множества, но, немного подумав над проблемой, решил, что вместо этого я должен использовать покрытие вершин. (поэтому вопрос изначально относится к доминирующему набору)