我试图从 算法。由S. Dasgupta,Ch Papadimitriou和UV Vazirani,第8章, ,PG281。问题8.19

一个 风筝 是均匀数量的顶点(例如$ 2N $)上的图形,其中$ n $形成一个集团,其余的$ n $顶点连接在“尾巴”中,该“尾巴”由一条路径组成,加入其中之一。集团的顶点。给定图形$ g $和目标$ g $,风筝问题要求提供一个风筝,其中包含$ 2G $节点。证明风筝是NP完整的。

有任何指针从这个问题开始吗?我完全迷失了它。

有帮助吗?

解决方案

您可以将clique($ g $具有$ k $的集团)减少到风筝:给定$ g =(v,e)$和$ k $,只需在多项式时间内构建新的图形$ g'$以这种方式:对于每个节点$ v_i $,添加$ k $新节点的尾巴。

如果$ g'$具有$ 2K $的风筝,那么$ g $的大小为$ k $(没有尾巴的风筝)。添加的节点不能在g'上引入新集团,因此$ g $包含$ g'$的完全相同的集团。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top