最小支配集？
by zzqDeco @ 2020-08-11 20:17:59
@[Error_666](/user/91681) 明显没有多项式做法
by hellomath @ 2020-08-11 20:20:11
@[Error_666](/user/91681)
好像可以转化成集合覆盖，NPC
by ix35 @ 2020-08-11 20:24:18
@[Error_666](/user/91681) 顶点覆盖可以规约为集合覆盖，而 Clique 问题可以规约为顶点覆盖，于是这个问题 NP 完全
by hellomath @ 2020-08-11 20:29:14
~~DLX~~
by pzc2004 @ 2020-08-11 20:54:21