5
$\begingroup$

Assume you have a connected, unweighted, undirected graph of $48$ nodes. Now imagine you are allowed to choose $6$ nodes and label them special. (In the general case, we select $K$ nodes to be special among the $N$ total nodes in the graph, where $K < N$.) We'll call the other $42$ nodes generic.

Once the $6$ special nodes are chosen, new edges are formed between every pair of special nodes. (To speed travel across remote locations within the graph.)

I have a few related questions:

  1. Is there a single, already-documented algorithm that is precisely designed to solve this problem? Namely, it determines the placement of the special nodes such that the average distance from any generic node to its nearest special node is minimized?
  2. Am I solving the same problem if I rephrase the question above to read "... the average distance between any two nodes in the graph (with the new special edges added) is minimized?"
  3. What types of graphs, and graph theory terms, are related to solving this type of problem? Obviously shortest-path type questions arise. But is there a concept such as "coverage"?

The goal stated in very generic terms is to be able to traverse, as quickly as possible, from any arbitrary node in the graph to any other arbitrary node.

For some more context, this graph theory question was inspired by the board game Pandemic. A few colleagues and I have tried searching the web / Wikipedia but haven't come across anything definitive yet.

$\endgroup$
1
  • 1
    $\begingroup$ I see I'm not the only person trying to figure out the optimal place to put research centers in Pandemic. $\endgroup$
    – Joshua Snider
    Dec 25, 2015 at 5:03

2 Answers 2

Reset to default
3
$\begingroup$

For questions 1 and 3: This is similar to the problem of finding a dominating set, that is, a set $S$ such that every vertex in the graph is either in $S$ or adjacent to some vertex in $S$. In particular, if there were an efficient algorithm to solve your problem, then one could also efficiently solve the problem "is there a dominating set of size at most $k$?", which is known to be NP-hard. (A dominating set of size $k$ is the only way to get average distance 1 for the remaining generic vertices.)

For question 2, I suspect that the questions are subtly different, but I don't have any proof of this.

$\endgroup$
1
  • 1
    $\begingroup$ In particular, you could find a dominating set $A$ of the graph and a dominating set $B$ of the induced subgraph on $A$. Every vertex now has a path of length at most two from some vertex of $B$. Carry on with the dominating sets if you are willing to accept longer distances. $\endgroup$
    – Austin Mohr
    Oct 30, 2015 at 15:56
2
$\begingroup$

For 2, these are not the same question in general. Consider a graph where six vertices form a complete subgraph, with each other vertex adjacent only to one of the six, evenly distributed. Then the unique best set to choose for the original question is the six vertices from the complete subgraph, since this gives every generic vertex distance $1$ from a special vertex. However, this is also the unique worst set to choose for the other question: since all the edges between special vertices were already in the graph, the average distance between a pair doesn't decrease at all.

$\endgroup$

You must log in to answer this question.

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