如何将此生成树问题减少到 np-completeness？

Question

我有以下算法问题：

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

总而言之，解决方案算法会将图 G 和数字 k 作为输入，return 为真或为假，具体取决于 G 是否具有 k 叶的生成树

示例：对于此图：

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

现在我很确定这个问题是 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;

删除所有有 2 条边的节点，如果删除一条边会断开图形，则直接连接它连接的两个节点。如果从 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
}

如何将此生成树问题减少到 np-completeness？

how do I reduce this spanning tree problem to np-completeness?

algorithm

np