查找具有最大最小度的生成树

Question

给定一个连通的无向图，发现具有最小最大度的生成树的问题已经被充分研究（M.F¨urer，B.Raghvachari，“Approximation the minimum degree spanning树在最优程度之内“，ACM-SIAM离散算法研讨会（SODA），1992）。该问题是NP难题，并且在参考文献中已经描述了近似算法。

我对以下问题感兴趣 - 给定连通无向图G =（V1，V2，E），找到所有内部节点（非叶节点）上具有最大最小度的生成树。有人可以告诉我，如果这个问题已经研究过;是NP难么还是存在多项式时间算法来解决它？另外，为了方便起见，该图可以被认为是双方的。

Answer 1

正如叶夫根Kluev的评论指出，一个（有限）树的叶子有度1（否则，周期会存在，结构不会是一棵树。）

相反，如果你的意思是找到一个从连通的无向图G上所有可能的生成树中生成一棵具有最大度的节点的生成树，然后形成一棵生成树，其根R是G中所有节点中具有最大度的G的节点M，并且所有邻居的M是R的孩子。

Answer 2

它看起来像3套精确覆盖可以减少到这个问题。用度数为4的顶点表示3集，每个顶点用3个边连接到表示其原始问题实例中元素的3个节点。附加的第4条边将所有“3组”节点连接到单个顶点V.

此图是双向的 - 每条边都位于“3组”节点和“元素”节点（或V）之间。现在这个图有一个最大最小度= 4的生成树，当且仅当原始问题有解决方案。

显然需要有足够的3组，使得节点V不会降低树的最大最小度数，但是这个限制不会改变问题的NP-硬度。