3
$\begingroup$

I'm primarily looking for some help for a graph theory question. What I'd like is a reference that deals with this particular question, or background knowledge if this question is already well-known and if the quantities involved have names. I have already looked in Newman's Networks textbook, section 6.12.1 on maximum flows / minimum cut seemed to get close, but it's not quite what I needed, and I couldn't find anything else like this in the book.

Here's the statement of the problem I have:

Let $G$ be a connected undirected graph. Let $\mathcal{N} = \{n_{1},\cdots{},n_{N}\}$ be the set of $N$ nodes and assume there is some nonnegative value associated with each node, $v_{i}$.

Let a subset of the nodes be called "big" if removing that subset causes the collection of remaining nodes to have zero edges. (I don't know if this property has a more common name).

So if $N=18$ and $\{n_{1}, n_{3}, n_{17}\}$ is a "big" subset, then it means the remaining collection $\mathcal{N} - \{n_{1}, n_{3}, n_{17}\} = \{n_{2}, n_{4}, \cdots, n_{16}, n_{18}\}$ has zero edges.

Let $\mathcal{B}$ be the set of all "big" subsets, and for each big subset $B\in{\mathcal{B}}$ let $$\mu(B) = \sum_{i: \textrm{ }n_{i}\in\mathcal{N}-B}v_{i}$$ be a function giving the sum of the node values among the nodes that remain after removing $B$.

The problem I have is to find:

$$\mathop{\arg\,\max}\limits_{B\in\mathcal{B}}\mu(B)$$

In words: find the set of nodes to remove from the graph such that the remaining graph has no edges and has maximum summed node values among all such graphs.

Again, I'm just looking to see what's already known about this problem or do more background reading. I have an ad hoc algorithm to find this set and it's very slow, so I'm curious if faster methods are known.

$\endgroup$

1 Answer 1

2
$\begingroup$

It is more natural to consider the complement of what you call big subsets. These are called independent sets or stable sets. What you are trying to solve is the maximum weight independent set problem, and this is a hard problem. Indeed, in the special case that all node weights are $1$, then we just want to find a maximum size independent set and the problem is still NP-complete. Googling the words in parenthesis will tell you more.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .