将图分割为具有必须位于同一子图中的顶点集的连接子图 [英] Partitioning a graph into connected subgraphs with sets of vertices that must be in the same subgraph

问题描述

我有一个连通的无向图G =（V，E），一个集S = {S_1，S_2，...，S_n}，其中每个S_i是V的一个子集，并且ak> 1。将V划分为k个子集，这样可以保证：对于每个i，S_i中的每个节点都位于相同的子集中 >

每个子集都代表G的一个连接子图

解决方案

Steiner森林问题给定加权图G =（V，E）和顶点对（s 1，t 1，...，s s）找到G的最小边 - 子图H，使得对于所有i，顶点s _{i 和t m / sub>属于H的相同连接组件。}

您的问题的决策版本实质上是具有单位权重的Steiner森林的决策版本。不幸的是，这种特殊情况仍然是NP-hard。

从Steiner森林的特殊情况到您的问题的减少是，由于Steiner森林的不加实例和指令确定是否存在至多c的成本解决方案，用相同的图形创建问题的实例，k = | V | - c，并且对于所有i，让S i = {s i ，t _i }。如果存在一个成本最高为c的斯坦纳森林，那么森林的连接组件就是你的子集，其数目至少为| V | - c = k。相反，如果问题的实例有解决方案，那么我们可以在每个子集中找到一棵生成树，总成本最多为| V | - k = c。

已知的最佳逼近比率是2，如果k很小，这对你没有多大帮助。您可能必须使用分支和绑定。

I have a connected, undirected graph G = (V, E), a set S = {S_1, S_2,..., S_n} where each S_i is a subset of V, and a k > 1. How can I partition V into k subsets such that it is guaranteed that:

1. for each i, every node in S_i is in the same subset
2. each subset represents a connected subgraph of G?

解决方案

The Steiner forest problem is, given a weighted graph G = (V, E) and pairs of vertices (s₁, t₁), …, (s_m, t_m), find the lightest edge-subgraph H of G such that, for all i, vertices s_i and t_i belong to the same connected component of H.

The decision version of your problem is essentially the decision version of Steiner forest with unit weights. Unfortunately, this special case is still NP-hard.

The reduction from the special case of Steiner forest to your problem is, given an unweighted instance of Steiner forest and instructions to determine whether there exists a solution of cost at most c, create an instance of your problem with the same graph, k = |V| - c, and, for all i, let S_i = {s_i, t_i}. If there exists a Steiner forest of cost at most c, then the connected components of the forest are your subsets, which number at least |V| - c = k. Conversely, if the instance of your problem has a solution, then we can find a spanning tree within each of your subsets, and the total cost is at most |V| - k = c.

The best approximation ratio known is 2, which won't help you much if k is small. You'll probably have to use branch and bound.

这篇关于将图分割为具有必须位于同一子图中的顶点集的连接子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！