How do I find a minimal set of US states so that every state boarders one of them?

Question

I recently played this game, in which one has to type in the names of US states. For each state one gives, all of the states which border it are removed from a list. The player continues to provide the names of states until all 48 contiguous states are gone. Since a state does not border itself, the state itself is not removed. For example, if I type in Utah, the states Idaho, Wyoming, Colorado, Arizona, and Nevada are removed (notably, neither Utah nor New Mexico are removed).

I want to know how to find the minimal number of states I can name to remove all 48. This is, I think, a graph theory problem, and this is an area in which I have little knowledge. Are there any theorems or algorithms I should look at?

I have an adjacency matrix of the United States from a previous project in Mathematica, and it has helped me find a solution with fifteen states, but I haven't yet found a smaller one. If there is a smaller solution, I would like to know, but please don't give it (or give it in a mouseover box).

Answer 1

I'm currently trying to figure out why a greedy algorithm wouldn't work there.

The "greedy" algorithm is the algorithm where, at each iteration, you choose the state with the most adjacent unpicked states. I'm feeling like it doesn't give you the optimal solution but I can't figure out why.

Note that the map of the states of the US has a corresponding graph where each state is a vertex, and two vertices are linked only if the two states are adjacent. However, in graph theory, when talking about a set of vertices covering the entire graph, we consider that a picked vertex is covered "by itself". It doesn't need to have a neighbor that is picked, so the problem here is a bit different

EDIT: I found a counterexample to the greedy algorithm: take $K_8$, the complete graph on 8 vertices. Link half of these points to a separate vertex $u$. Link the other half to another separate vertex $v$. Link $u$ and $v$ too. Then, add one isolated vertex to $u$ and one to $v$. Then clearly, $u$ and $v$ cover the whole graph. However, their degree is only $4+1+1=6$ whereas any vertex of $K_8$ has degree 8. Hence, with the greedy algorithm, the first vertex picked is one of the $K_8$. However, $u$ and $v$ have to be both taken to cover the entire graph, since they are adjacent to one isolated vertex each.

A "enhanced" greedy algorithm would be to consider all pairs of adjacent states, and choose first the one that covers the most vertices. And then repeat until the US are covered.

Answer 2

Here's an algorithm you can try, though I have no idea if it would run in a reasonable time:

You have a fixed graph, and each vertex is one of three options: ON, OFF, or NEUTRAL. 'ON' means you've clicked the state, 'OFF' means you definitely won't, 'NEUTRAL' means you haven't decided. At the beginning, all vertices are NEUTRAL. Now, you run the following steps:

1) For a given vertex, if it has one NEUTRAL neighbor and the rest are OFF, change the NEUTRAL neighbor to ON.

2) For a given vertex, if it has one or zero neighbors which are not next to vertices that are ON, turn that vertex OFF. (If you turn a vertex off, loop through 1) again)

3) Pick a vertex at random, and split your decision tree into two paths: one where the state is 'ON' and another where the state is 'OFF'. Smart choices are neighbors of states with few neighbors. So for example, a good first choice might be Idaho, since if Idaho is OFF you know Oregon must be ON (due to Washington), which implies Washington is OFF (by step 2). And so on.