>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.
This problem is NP-hard. So you shouldn't expect a polynomial solution.
The NP-hardness of this problem can be shown with a reduction from the Longest Path Problem.
Let G = (V, E) be an unweighted, undirected graph whose longest path you want to find. Add two more vertices x1 and x2 and connect them to all nodes in this graph. Let us define the IV (= information value) of all nodes to be 1, except for x1 and x2, which have IV = infinity.
Obviously, the solution to your problem would involve removing x1 and x2 and then finding the longest path. But if we could solve that efficiently, then we can deduce the longest path. Hence this is NP-hard.
Oh, I see... Thank you for the explanation!