How to solve a graph theory question similar to shortest-path?

Question

I'm looking at several problems of similar format but different difficulty. Help would be appreciated for polynomial (preferably relatively fast, but not necessarily), and even brute-force solutions of any of them.

The idea of all of the problems is that you have a weighted, undirected graph, and that an agent controls some of the nodes of the graph at the start. The agent can gain control of a node if they already control two adjacent nodes. The agent is trying to minimise the time they take to control a certain number of nodes. The problems differ on some details.

(1) You gain control of nodes in order (ie. you cannot take over multiple nodes simultaneously). The time taken to take control of a node is defined as the minimum of the edges from the two nodes used to take control of it. The goal is to take control of every single node in the graph.

(2) Again, you gain nodes in order and the goal is to take control of every single node in the graph. The time taken to take control of a node is defined as the maximum of the two nodes used to take control of it.

(3) Either (1) or (2), but with the goal of taking control of a certain number of nodes, not necessarily all of them.

(4) (3), but you can take control of multiple nodes simultaneously. Basically, say nodes 2 and 4 are being used to take over node 3 in time of 5. During that time of 5, nodes 2 and 4 cannot be used to take over a node that is not node 3. However, nodes 5 and 6 may for example be simultaneously taking over node 1.

(5) (4), but with an unweighted graph.

I started with the problem (4). I progressively made the problem easier from (4) to (3) to (2) to (1) with the hopes I could construct the solution for (4) from that. Finally, I have solved (1) but do not know how to solve any other one. My solution to (1) is this: of all candidate nodes which have two adjacent nodes that we control, simply take the one which takes the shortest amount of time. This is similar to Dijkstra's shortest path algorithm. However, this kind of solution should not solve any of the others. I believe that possibly a dynamic programming solution might work though, but I have no idea how to formulate one. I also have not found brute force solutions for any of the 4 problems. It is also possible that some of the problems are not polynomially solvable, and I would be curious to know why if that is the case.

Idea for the questions are my own, and I'm solving for my own entertainment. But I would not be surprised if it can be found elsewhere.

Answer 1

This isn't an answer to the problem. It is a demonstration that the greedy approach fails for problem 1.

Suppose that we have a graph with 7 nodes. We start by controlling A and B. The cost from A to B and B to C and C to D are all 1. Both E and F connect to A, B, and D with cost 10. G connects to A, B, C, and D with cost 100.

The greedy strategy that you describe will connect to E and F at cost 10 each, then D at cost 10, then C at cost 1, then G at cost 100 for a total cost of 131.

The best strategy is to connect to G at cost 100, then C and D at cost 1, then E and F at cost 10 for a total cost of 122 < 131.

And this example demonstrates that greedy is not always going to produce the right answer.

Answer 2

I haven't been able to come up with a reduction yet, but these problems have the flavor of NP-hard network design and maximum coverage problems, so I would be quite surprised if variants (3) through (5) were tractable.

My practical suggestion would be to apply the Biased Random-Key Genetic Algorithm framework. The linked slide deck covers the generic part (an individual is a map from nodes to numbers; at each step, we rank individuals, retain the top x% "elite" individuals as is, produce y% offspring by crossing a random elite individual with a random non-elite individual, biased toward selecting the elite chromosomes, and fill out the rest of the population with random individuals). The non-generic part is translating an individual into a solution. My recommended starting point would be to choose to explore the lowest-numbered eligible node each time.