<p>The paper [Chlebikova, <a href="http://dx.doi.org/10.1016/S0020-0190(96)00175-5" rel="nofollow">Approximating the maximally balanced connected partition problem in graphs</a>, 1996] studies a related problem: They have $k=2$, and they maximize $\min(|V_1|,|V_2|)$. It should be a good place to start searching for related results, by following the citation graph.</p>

CC BY-SA 3.0
2016-08-16T13:30:50.000Z
2016-08-16T13:30:50.000Z
Radu GRIGore
<p>If I understand corectly, it seems that the problem is NPC even if we want to devide it into two parts.</p>

<p>Here is a reduction from partition problem. (I didn't check it carefully hope it works).</p>

<p>Let say $w_1,\ldots,w_n $ form an instance of the partition problem. Take a graph with $2n$ nodes $v_1,\ldots,v_{2n}$.</p>

<p>Assign weight $w_i $ to $v_i $ for $i &lt;n+1$.
Assign weight $0 $ to $v_i $ for $i &gt;n$.</p>

<p>Connect $v_i$ to $v_{i+1}$ For $i =1,...,n-1$.</p>

<p>Connect $v_i$ to $v_{i+1}$ For $i =n+1,...,2n-1$.</p>

<p>Connect $v_i$ to $v_{i+n}$ For $i =1,...,n$.</p>

<p>Connect $v_i$ to $v_{i+n+1}$ For $i =1,...,n-1$.</p>

<p>Connect $v_{i+n}$ to $v_{i+1}$ For $i =1,...,n-1$.</p>

<p>If there is a solution to the partition problem then we can find two vertex disjoint paths in the graph corresponding to those partitions. On the other hand clearly if we can devide the graph into two connected sets of same size then we have a solution for partition.</p>

<p>Edit1: As Sasho mentioned in comments if the input graph is complete graph then thete is a straightforward reduction from partition problem. I leave previous reduction as it uses sparse graph.</p>

<p>Edit2: As asked in comments about other graphs except the complete graph I undeleted this answer, because even though it's easy, it's maybe non trivial.</p>

CC BY-SA 3.0
2016-08-13T01:51:10.367Z
doesn't the obvious reduction from partition work: take $G$ to be the complete graph with weights on vertices given by the partition instance?
Sasho Nikolov
CC BY-SA 3.0
2016-08-13T02:18:36.390Z
@Sasho that's true :-))) I tried to do it for sparse graph (I thought if graph is dense is harder) and I totally missed same thing simply works for complete graph without taking care of connections :-)
Saeed
CC BY-SA 3.0
2016-08-16T10:53:32.807Z
@Saeed I had a deep feeling that this problem is NPC time long ago. I am interested how people call this problem (I think this problem might be commonly seen in many situation).
Xing Zhou
CC BY-SA 3.0
2016-08-16T12:02:35.150Z
@XingZhou, I don't know what is the name of the problem or how people call it. By the way above reduction is from 2-partition, if you want the strong np-hardness proof, trivial reduction from 3-partition in complete graph works. On the other hand if you are looking for search term maybe, connected weighted clustering or combination close to that would help.
Saeed
CC BY-SA 3.0
2016-08-16T12:06:06.870Z
@XingZhou, Also I undeleted my answer because in the comments to the question you wrote what if the graph is not complete graph and asked about how to make the connections there. The easiest way i think to make the connections as "simple paths" as I provided in the answer.
Saeed
CC BY-SA 3.0
2016-08-13T00:47:40.473Z
2016-08-14T13:50:22.970Z
2016-08-14T13:50:22.970Z
Saeed
<p>Consider the following problem:</p>

<blockquote>
  <p>Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
  partition of $V$ into $V_1,\ldots,V_k$ such that each subgraph induced by $V_i$ is connected, and such that $\max_i w(V_i)$ is
  minimized, where $w(V_i)$ is the total weight of the vertices in
  $V_i$.</p>
</blockquote>

<p>It can be easily seen that this problem is NP-complete. For hardness, note that we can solve <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow">Partition</a> by using a complete graph.</p>

<p><strong>Questions:</strong> Does this problem have a standard name? Are there any papers that study this problem, or maybe slight variations of it? Is the problem still hard for sparse graphs? I am particularly interested in references that <em>could</em> lead to an implementation with good performance in practice.</p>

CC BY-SA 3.0
2016-08-12T11:23:33.783Z
I could be wrong here... But isn't that basically the knapsack problem ?
julian
CC BY-SA 3.0
2016-08-12T11:34:31.923Z
What is the role of E?
domotorp
CC BY-SA 3.0
2016-08-12T12:18:15.347Z
what is the weight of a component? the total weight of the edges in the induced graph?
Sasho Nikolov
CC BY-SA 3.0
2016-08-12T13:31:57.623Z
It is if the graph is complete, but the requirement (admittedly only stated in the title) that the subsets are connected makes a difference otherwise.
Klaus Draeger
CC BY-SA 3.0
2016-08-12T19:56:54.837Z
@Sasho the weights are on the vertices.
domotorp
CC BY-SA 3.0
2016-08-12T20:28:41.580Z
Thanks @domotorp, I did not notice that at first. So is the problem: partition $V$ into disjoint subsets $V_1, \ldots, V_k$, so that the induced subgraph on each $V_i$ is connected and the weights of the heaviest $V_i$ (=sum of weights of elements of $V_i$) is minimized?
Sasho Nikolov
CC BY-SA 3.0
2016-08-13T13:11:44.177Z
@julian how to map to a knapsack problem? be careful that vertices consist the same part should be connected.
Xing Zhou
CC BY-SA 3.0
2016-08-13T13:14:47.177Z
@SashoNikolov Your comprehension is nearly right, be careful that any Vi and Vj have no common vertex.
Xing Zhou
CC BY-SA 3.0
2016-08-13T13:16:10.950Z
@domotorp The role of E is only for indicating connectivity of vertices.
Xing Zhou
CC BY-SA 3.0
2016-08-13T13:51:01.140Z
@XingZhou that's what "disjoint" means in my comment.
Sasho Nikolov
CC BY-SA 3.0
2016-08-13T19:20:57.253Z
I'm sorry, but I still cannot understand the problem. If anyone can, please rewrite the question!
domotorp
CC BY-SA 3.0
2016-08-13T19:44:54.967Z
@domotorp, I *think* that the problem is what Sasha Nikolov says above, in comments.
Radu GRIGore
CC BY-SA 3.0
2016-08-13T20:08:47.313Z
@Radu Then why isn't it equivalent to the knapsack problem for complete graphs, as julian said?
domotorp
CC BY-SA 3.0
2016-08-13T20:17:18.123Z
@domotorp, it is. But non-theory people care about runtimes, not about complexity classes. So, just saying "NP-complete" is unhelpful.
Radu GRIGore
CC BY-SA 3.0
2016-08-13T21:08:36.180Z
It's not knapsack (which requires weight and size for each item).  This problem, for k=2 and a complete graph, is apparently [Partition](https://en.wikipedia.org/wiki/Partition_problem).
Neal Young
CC BY-SA 3.0
2016-08-14T01:54:19.303Z
@domotorp By deleting some edges of a vertex-weighted connected graph, one can get several connected subgraphs. Our objective is to make the number of subgraphs is k and that the sums of vertices for each subgraph are  nearly same (or the heaviest subgraph be quite light).
Xing Zhou
CC BY-SA 3.0
2016-08-14T01:57:47.457Z
@NealYoung  
It is number partitioning problem when the graph is complete. But how about incomplete graph? I can't see how to add extra edges satisfying the original problem.
Xing Zhou
CC BY-SA 3.0
2016-08-14T10:43:55.490Z
@XingZhou: The problem is NP-hard because the special case with the complete graph is NP-hard. The problem is in NP because one can obviously check in polynomial time if a candidate solution is good. Therefore, the problem is NP-complete. Once you know the problem is NP-complete, you go and ask people who work in *Optimization*. (Here, you might get answers to questions like, (a) "Is there a FPTAS for this?", (b) "What (interesting) special cases are in P? (c) What would be a simple reduction to ILP (so I can try an ILP solver)?" and so on. In general, it helps if you ask a precise question.)
Radu GRIGore
CC BY-SA 3.0
2016-08-16T10:51:00.023Z
@RaduGRIGore I want to know the formal name of this problem in literature because I want to see how people use genetic algorithms to tackle it. I know the problem is NPC.
Xing Zhou
CC BY-SA 3.0
2016-08-17T23:11:56.517Z
Rather than asking "What is the name of this problem?", it's usually better to ask a more specific question: e.g., is there an approximation algorithm?  is there an effective heuristic?  and so on.  Figure out what you really want to accomplish, and ask about that.  That way there are two ways to win: either (a) someone tells you how to achieve your actual goal, or (b) someone tells you a "name" for the problem and you can research it.  If you only ask for its "name", there's only one to win (namely, (b)), and the problem might not actually have a "name".
D.W.
<graph-theory><graph-algorithms><co.combinatorics><np-hardness><optimization>
Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?
Xing Zhou
# Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?

(Asked by: username_0 on 2016-08-12)

Consider the following problem:

> Given an integer $k$ and a vertex-weighted graph $G=(V,E)$, find a
> partition of $V$ into $V\_1,\ldots,V\_k$ such that each subgraph induced by $V\_i$ is connected, and such that $\max\_i w(V\_i)$ is
> minimized, where $w(V\_i)$ is the total weight of the vertices in
> $V\_i$.

It can be easily seen that this problem is NP-complete. For hardness, note that we can solve [Partition](https://en.wikipedia.org/wiki/Partition_problem) by using a complete graph.

**Questions:** Does this problem have a standard name? Are there any papers that study this problem, or maybe slight variations of it? Is the problem still hard for sparse graphs? I am particularly interested in references that *could* lead to an implementation with good performance in practice.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, np-hardness, optimization

> **Comments:**
> **username_1**: I could be wrong here... But isn't that basically the knapsack problem ?  
> **username_2**: What is the role of E?  
> **username_3**: what is the weight of a component? the total weight of the edges in the induced graph?  
> **username_4**: It is if the graph is complete, but the requirement (admittedly only stated in the title) that the subsets are connected makes a difference otherwise.  
> **username_2**: @Sasho the weights are on the vertices.  
> **username_3**: Thanks @username_2, I did not notice that at first. So is the problem: partition $V$ into disjoint subsets $V_1, \ldots, V_k$, so that the induced subgraph on each $V_i$ is connected and the weights of the heaviest $V_i$ (=sum of weights of elements of $V_i$) is minimized?  
> **username_0**: @username_1 how to map to a knapsack problem? be careful that vertices consist the same part should be connected.  
> **username_0**: @SashoNikolov Your comprehension is nearly right, be careful that any Vi and Vj have no common vertex.  
> **username_0**: @username_2 The role of E is only for indicating connectivity of vertices.  
> **username_3**: @XingZhou that's what "disjoint" means in my comment.  
> **username_2**: I'm sorry, but I still cannot understand the problem. If anyone can, please rewrite the question!  
> **username_5**: @username_2, I *think* that the problem is what Sasha Nikolov says above, in comments.  
> **username_2**: @Radu Then why isn't it equivalent to the knapsack problem for complete graphs, as username_1 said?  
> **username_5**: @username_2, it is. But non-theory people care about runtimes, not about complexity classes. So, just saying "NP-complete" is unhelpful.  
> **username_6**: It's not knapsack (which requires weight and size for each item).  This problem, for k=2 and a complete graph, is apparently [Partition](https://en.wikipedia.org/wiki/Partition_problem).  
> **username_0**: @username_2 By deleting some edges of a vertex-weighted connected graph, one can get several connected subgraphs. Our objective is to make the number of subgraphs is k and that the sums of vertices for each subgraph are  nearly same (or the heaviest subgraph be quite light).  
> **username_0**: @NealYoung   It is number partitioning problem when the graph is complete. But how about incomplete graph? I can't see how to add extra edges satisfying the original problem.  
> **username_5**: @XingZhou: The problem is NP-hard because the special case with the complete graph is NP-hard. The problem is in NP because one can obviously check in polynomial time if a candidate solution is good. Therefore, the problem is NP-complete. Once you know the problem is NP-complete, you go and ask people who work in *Optimization*. (Here, you might get answers to questions like, (a) "Is there a FPTAS for this?", (b) "What (interesting) special cases are in P? (c) What would be a simple reduction to ILP (so I can try an ILP solver)?" and so on. In general, it helps if you ask a precise question.)  
> **username_0**: @RaduGRIGore I want to know the formal name of this problem in literature because I want to see how people use genetic algorithms to tackle it. I know the problem is NPC.  
> **username_7**: Rather than asking "What is the name of this problem?", it's usually better to ask a more specific question: e.g., is there an approximation algorithm?  is there an effective heuristic?  and so on.  Figure out what you really want to accomplish, and ask about that.  That way there are two ways to win: either (a) someone tells you how to achieve your actual goal, or (b) someone tells you a "name" for the problem and you can research it.  If you only ask for its "name", there's only one to win (namely, (b)), and the problem might not actually have a "name".  

---

## 2 answers

### Answer by username_5 on 2016-08-16. Score: 2

The paper [Chlebikova, [Approximating the maximally balanced connected partition problem in graphs](http://dx.doi.org/10.1016/S0020-0190(96)00175-5), 1996] studies a related problem: They have $k=2$, and they maximize $\min(|V\_1|,|V\_2|)$. It should be a good place to start searching for related results, by following the citation graph.


---

### Answer by username_8 on 2016-08-13. Score: 0

If I understand corectly, it seems that the problem is NPC even if we want to devide it into two parts.

Here is a reduction from partition problem. (I didn't check it carefully hope it works).

Let say $w\_1,\ldots,w\_n $ form an instance of the partition problem. Take a graph with $2n$ nodes $v\_1,\ldots,v\_{2n}$.

Assign weight $w\_i $ to $v\_i $ for $i n$.

Connect $v\_i$ to $v\_{i+1}$ For $i =1,...,n-1$.

Connect $v\_i$ to $v\_{i+1}$ For $i =n+1,...,2n-1$.

Connect $v\_i$ to $v\_{i+n}$ For $i =1,...,n$.

Connect $v\_i$ to $v\_{i+n+1}$ For $i =1,...,n-1$.

Connect $v\_{i+n}$ to $v\_{i+1}$ For $i =1,...,n-1$.

If there is a solution to the partition problem then we can find two vertex disjoint paths in the graph corresponding to those partitions. On the other hand clearly if we can devide the graph into two connected sets of same size then we have a solution for partition.

Edit1: As Sasho mentioned in comments if the input graph is complete graph then thete is a straightforward reduction from partition problem. I leave previous reduction as it uses sparse graph.

Edit2: As asked in comments about other graphs except the complete graph I undeleted this answer, because even though it's easy, it's maybe non trivial.

> **Comments:**
> **username_3**: doesn't the obvious reduction from partition work: take $G$ to be the complete graph with weights on vertices given by the partition instance?  
> **username_8**: @Sasho that's true :-))) I tried to do it for sparse graph (I thought if graph is dense is harder) and I totally missed same thing simply works for complete graph without taking care of connections :-)  
> **username_0**: @username_8 I had a deep feeling that this problem is NPC time long ago. I am interested how people call this problem (I think this problem might be commonly seen in many situation).  
> **username_8**: @XingZhou, I don't know what is the name of the problem or how people call it. By the way above reduction is from 2-partition, if you want the strong np-hardness proof, trivial reduction from 3-partition in complete graph works. On the other hand if you are looking for search term maybe, connected weighted clustering or combination close to that would help.  
> **username_8**: @XingZhou, Also I undeleted my answer because in the comments to the question you wrote what if the graph is not complete graph and asked about how to make the connections there. The easiest way i think to make the connections as "simple paths" as I provided in the answer.  

---

