1
$\begingroup$

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?

Thank you for your help

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for answering. What if my m is not a variable of the algorithm and it is a fixed value since the beginning. would this affect the NP-completeness of the prob? $\endgroup$
    – user76838
    Commented Sep 8, 2017 at 11:25
  • $\begingroup$ Fixing only $m$ does not affect NP-completeness of the problem. Even when we fix $m$ to $1$, we can solve the Independent set. $\endgroup$
    – fade2black
    Commented Sep 8, 2017 at 21:45
  • $\begingroup$ Decision version of problem is trivially in $\mathsf{NP}$. $\endgroup$
    – rus9384
    Commented Sep 8, 2017 at 22:35

Your Answer

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