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 ?

Improve this question
$\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, 2020 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, 2020 at 23:54

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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