2
$\begingroup$

If I had a graph representing the USA with each node representing a state, and each edge linking adjoining states, is there a graph algorithm that would give me every possible unique group of 4 states that are linked (order of states is not important)?

By 'linked' I mean that all states in valid group should be reachable from every other state in the group either because they are adjoining (direct neighbours) or connected via another state in the group, eg :

One valid group is Kansas, Nebraska, Iowa, Missouri (since Nebraska, Iowa, Missouri are direct neighbours of Kansas)

But also Kansas, Colorado, Utah, Nevada is valid since Kansas is a neighbour of Colorado which is a neighbour of Utah which is a neighbour of Nevada (even though Kansas and Nevada are not direct neighbours)

It seems to make sense to me to represent this data in a graph or adjacency matrix since 'connectivity' is the key qualifier. Generating every combination of 4 states, then testing for connectivity seems wasteful and even more so if I wanted every combination of 5,6,7... states.

I don't have much knowledge in this area, but I thought this may be suited to a graph theory type problem, but cannot find anything that matches this type of problem, so I am probably looking in the wrong area.

Can anyone give any advice, areas for me to read up on ?

$\endgroup$
2
  • $\begingroup$ Please edit the question to define under what conditions you consider a group of 4 states to be linked. Do you require each pair to be adjoining? $\endgroup$ – D.W. Jun 7 '20 at 23:48
  • $\begingroup$ Sorry, I thought it was clear from my 2 examples, I will edit and try and clarify now $\endgroup$ – user1676300 Jun 7 '20 at 23:54
2
$\begingroup$

A standard brute-force method should suffice: enumerate all ${50 \choose 4}$ ways to choose 4 out of the 50 states, and for each such combination, check whether it meets your requirements. There are only about 230,000 combinations to check, so this should run in a fraction of a second on a computer.

If you wanted to optimize it, there are various methods, such as choosing a state $u$, then choosing another state $v$ that is a neighbor of $u$, then choosing another state $w$ that is a neighbor of $u$ or $v$, then finally one more state $x$ that is a neighbor of one of $u,v,w$, and then checking whether that meets your conditions. This would be faster. But why bother? It's hardly worth spending an extra hour or two programming a complicated algorithm to spend a fraction of a second of CPU time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.