我想将顶点覆盖问题简化为特定的决策问题。这个决策问题如下：
我有一个 nxn 矩阵 A、一个 R^n 中的向量 b 和一个正整数 k。R^n 中是否存在最多 k 个非零条目的向量 x，使得 A*x 大于或等于 b？
我在想 A 可以被视为一个邻接矩阵，但我不确定如何将顶点覆盖问题减少到这个问题。
谁能给我一两个关于我下一步应该做什么的提示？
编辑**我最初考虑使用支配集问题，但在考虑了更多问题之后，我认为我应该使用顶点覆盖来代替。（所以问题最初是指支配集）
问问题
291 次