如何将这个生成树问题简化为np-完全问题？

Question

我有以下算法问题：

如果我有一个图G=(V，E)，G是否有一个恰好有k个叶子的生成树？叶子是在生成树中只有一个邻居的顶点。另外，我不是在寻找最小的生成树，而是一个生成树。

总而言之，解决算法将接受一个图G和一个数字k作为输入，并根据G是否有k个叶子的生成树返回true或false

示例:对于此图：

​

​

如果k是6，那么我的算法将输出"True“，因为：

​

​

现在我非常确定这个问题是np-complete的，所以我需要从一个已知的np-complete问题进行归约。

我只是不知道是哪一个问题，以及缩减应该是什么样子，你能帮助解决吗？

Answer 1

Hamiltonian path problem是您的问题的特例-恰好有k=2个叶子的生成树是哈密顿路径。测试一个的存在是NP-完全的。

Answer 2

不是对您的问题的真正答案，但是您可能希望在开始使用这些1.x^N算法之前尝试简化该图

简化事情(前面未测试的代码)

if (nodes.size() < K)
  return false;

删除所有只有一条边的节点，因为它们被强制为叶子。

while (nodes && nodes.front().edges.size() == 1) {
  nodes.erase(nodes.begin()); // updates one other node which could have 1 edge then.
  K--;
}

if (K < 0 || nodes.size() < K)
  return false;

删除所有有两条边的节点，如果删除其中一条边会断开图形，请连接它直接连接到的两个节点。如果存在从edge1到edge2的任何路径，则它不是网桥。O(N^2)

node = nodes.begin();
while (node->edges.size() == 2) {
  if (DisconnectingBrigde(node)) {
    edges = node->edges;
    node = nodes.erase(node); // returns next node
    nodes.addEgde(edges.front(), edges.back()); // connect the two parts
  } else
    node++; // next node
}