# Maximisation of graphs weight

I have a graph related problem. Let $G$ be an undirected weighted graph of $N$ nodes. I want to find $p$ independent (they have no edge linking them) sub-graphs of $m$ nodes in a way that the total weight is maximized.

For example, let $G$ be a graph of $16$ nodes, I want to find $4$ sub-graphs of $4$ nodes with $w_1, w_2, w_3, w_4$ as their weights (sum of the weights on the subgraph's edges) I want to determine the $4$ subgraphs that will maximize $w_1+w_2+w_3+w_4$.

Is this a classic graph problem? Is there already an algorithm for this? I am not very experienced with graphs and my research on the net was only confusing. Any ideas on how to approach this?

It is definitely not a classic graph problem such as the shortest path, maximum-flow, or graph coloring problem. But your problem, in its general form, seems to solve the Independent set problem, which is $NP$-complete.
Assume that you have a polynomial time algorithm $A(G,m,p)$ solving this problem. Then take $m=1$ and call $A(G,1,p)$ for $p=N,N-1,...,2,1$ (at most $N$ times) until you find a solution. When $m=1$, each subgraph has only one node and so its weight is 0, which is maximum for a single node graph. Furthermore, these nodes are not connected by an edge, and so they are not adjacent, i.e. they are independent.
If this procedure finds a solution for the maximum $p$ less than $N$, then this means we have a maximal independent set, since we have exactly $n$ nodes (subgraphs) with no edges between them, i.e. independent.
Once your problem is $NP$-complete, you could try any approximation algorithm including Linear or Integer programming.
• Fixing only $m$ does not affect NP-completeness of the problem. Even when we fix $m$ to $1$, we can solve the Independent set. – fade2black Sep 8 '17 at 21:45
• Decision version of problem is trivially in $\mathsf{NP}$. – rus9384 Sep 8 '17 at 22:35