Menu
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:
974
In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are (or can be) partitioned into k different independent sets. Equivalently, it is a graph that can be colored with k colors, so that no two endpoints of an edge have the same color.
Graph partitioning can be done by recursively bisecting a graph or directly partitioning it into k sets. There are two ways to partition a graph, by taking out edges, and by taking out vertices. Graph partitioning algorithms use either edge or vertex separators in their execution, depending on the particular algorithm.
(Graph Partition Problem) In Graph Partition a graph G has to be divided into two equal-size sets of vertices with and such that the number of edges that go from one set to the other is minimized. The decision variant (a.k.a. minimum-cut problem) takes an additional parameter k, and asks whether or not .
Connected graph: A graph G is called connected if every two of its vertices are connected. Disconnected graph: A graph that is not connected is called disconnected. It is easy to see that a disconnected graph consists of two or more connected graphs. Each of these connected subgraphs is called a component.
The Steiner forest problem is, given a weighted graph G = (V, E) and pairs of vertices (s1, t1), …, (sm, tm), find the lightest edge-subgraph H of G such that, for all i, vertices si and ti 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 Si = {si, ti}. 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.
123
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
