0

I have networks (large&small) which I need to prune until only isolates are left. I would like to maximize the number of isolates. Is there an algorithm to do this? also if its more complex ? (e.g. on the bottom there may be connected nodes as well)

consider this simple example:

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (2,4), (3,5), (3,6), (4,7), (4,8),
 (1,2+9), (2+9,3+9), (2+9,4+9), (3+9,5+9), (3+9,6+9), (4+9,7+9), (4+9,8+9) ])

Here, the optimal solution is deleting node 1,3,4,11 and 12.

example

Community
  • 1
  • 1
tafelplankje
  • 563
  • 1
  • 7
  • 21

1 Answers1

1

This sounds like you want to calculate the Maximum Independent Set (which is NP-hard for general graphs). (Wikipedia also mentions the name vertex packing).

Networkx has an approximation algorithm.

Maybe an approximation is not enough for you (and i think there is no prebuild alternative).

According to the wikipedia-link above, there is an exact algorithm available in igraph.

Also keep in mind, that this approximation-algorithm is for general graphs, so it might be very much possible, that there are better approaches for trees.

Edit: (Without checking) This SO-answer presents an algorithm for trees (and the question is a possible duplicate).

sascha
  • 32,238
  • 6
  • 68
  • 110