将图形划分为连接的子图,其中的顶点集必须位于同一子图中

Question

我有一个连通的,无向图G =(V,E),一个集S = {S_1,S_2,...,S_n},其中每个S_i是V的子集,ak> 1.如何将V划分为k子集,以保证:

1. 对于每个i,S_i中的每个节点都在同一子集中
2. 每个子集代表G的连通子图？

Answer 1

施密纳森林问题,给定加权图G =(V,E)和顶点对(s ₁,t ₁),...,(s _m,t _m),找到G的最轻边 - 子图H,使得,对于所有i,顶点s _i和t _i属于H的相同连通分量.

您的问题的决策版本本质上是具有单位权重的Steiner林的决策版本.不幸的是,这个特殊情况仍然是NP难的.

从Steiner林的特殊情况到您的问题的减少是,给定Steiner森林的未加权实例以及确定是否存在最多成本c的解决方案的指令,使用相同的图形创建问题的实例,k = | V | - c,对于所有我,让S _i = {s _i,t _i }.如果存在最多成本的Steiner林c,则林的连通组件是您的子集,其数量至少为| V | - c = k.相反,如果您的问题实例有解决方案,那么我们可以在您的每个子集中找到生成树,总成本最多为| V | - k = c.

已知的最佳近似比为2,如果k很小,这对你没有多大帮助.你可能不得不使用分支和绑定.