4
$\begingroup$

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 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.

$\endgroup$
20
  • 1
    $\begingroup$ What is the role of E? $\endgroup$
    – domotorp
    Aug 12, 2016 at 11:34
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 12, 2016 at 20:28
  • 1
    $\begingroup$ @domotorp, it is. But non-theory people care about runtimes, not about complexity classes. So, just saying "NP-complete" is unhelpful. $\endgroup$ Aug 13, 2016 at 20:17
  • 2
    $\begingroup$ It's not knapsack (which requires weight and size for each item). This problem, for k=2 and a complete graph, is apparently Partition. $\endgroup$
    – Neal Young
    Aug 13, 2016 at 21:08
  • 1
    $\begingroup$ @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.) $\endgroup$ Aug 14, 2016 at 10:43

2 Answers 2

2
$\begingroup$

The paper [Chlebikova, Approximating the maximally balanced connected partition problem in graphs, 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.

$\endgroup$
0
$\begingroup$

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+1$. Assign weight $0 $ 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.

$\endgroup$
5
  • $\begingroup$ doesn't the obvious reduction from partition work: take $G$ to be the complete graph with weights on vertices given by the partition instance? $\endgroup$ Aug 13, 2016 at 1:51
  • $\begingroup$ @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 :-) $\endgroup$
    – Saeed
    Aug 13, 2016 at 2:18
  • $\begingroup$ @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). $\endgroup$
    – Xing Zhou
    Aug 16, 2016 at 10:53
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Aug 16, 2016 at 12:02
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Aug 16, 2016 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.