我有一个很难开始的家庭作业问题。我们正在研究 Karp（单次调用）减少以显示难处理性。对于这个任务，这个问题是故意模糊的。我希望这里的某个人可能知道它或者可以提供一个解决方案示例来帮助我入门。
该问题仅在他们提供的代码中进行了描述。它具有以下组件：
B = (G, T, k) 其中 B 是“Blah”问题的一个实例，G = (V,E) 是图（未加权，无向），T 是 V 中的顶点子集，k 是整数。B 的证书返回 G 的子图 S = (V', E')。还提供了 yes 实例的验证器：
一个是的例子如果
forall [t in T], there exists some edge [e in E'] s.t. t is an endpoint of e
and, the number of edges of S is at most k (|E'| <= k)
and, S is a connected graph
我看到这个问题与独立集或顶点覆盖问题之间有一些相似之处。我觉得这些是很好的候选者，可以减少以显示难以处理，但对问题的理解还不够好。如果在某处讨论这个问题，或者任何人都可以提供一些例子，我将不胜感激。谢谢！