>bumping this post for first and last time because I never got an answer
There is an intruder in your system who wishes to steal as much information as he can. Your system can be represented as an undirected graph, with each node having an information value (IV). Now, you were terribly unprepared for this. Your only option is to delete nodes. You have time enough to delete at most 2 nodes. Luckily, the algorithm of the intruder has a flaw. It cannot visit a previously visited node. It steals the information of whatever node it visits. Assuming that the algorithm always tries to maximize the IV it can get, give the maximum possible IV you can save.
Note: Formally the algorithm seeks the path of maximum weight. The sum of the weights of the unvisited nodes is what you have saved. The weights of the deleted nodes are unavailable to both you and the algorithm. When a node is deleted, all paths connected to it are also removed.
A variant: Now you are given that the algorithm starts the path with a given vertex that you cannot delete.
There are no constraints, I want the best solution. Please notify any corrections or flaws in the problem statement. It is guaranteed that the constraints allow a solution.