Re: What complexity class is 6 Degrees of Kevin Bacon?
- From: Ralph Hartley <hartley@xxxxxxxxxxxxxxxx>
- Date: Tue, 08 Aug 2006 11:30:45 -0400
D. C. wrote:
Bear with me, but I noticed the 6 Degrees of Kevin Bacon game bears a....
/little/ resemblance to the Traveling Salesman Problem.
Suppose I download everything off IMDB and use it to create a list of
actors, and for each actor's entry in the list, I store a list of
references to other actors that that actor has been in a movie with.
My Kevin Bacon Solver's goal is: given the record of any actor, find a
path to Kevin Bacon in 6 steps or less (or tell me if no such path
exists).
Does this sound to anybody like it could be reduced to SAT or TSP? Or
does it maybe belong to some other complexity class? (Or is this just
an elementary complexity question and what I really need is a reference
to a good book?)
I'm afraid it is the latter, but I haven't kept up to date enough to suggest one.
The relevant question for NP completeness is if SAT or TSP can be reduced to your problem, not the other way around.
Your problem is a classic.
Algorithm:
Label KB with the number 0, and place him on a queue.
While the queue is not empty do
Let A be the actor at the head of the queue.
Remove A from the queue.
for each actor B that has been in a movie with A do
if B has no label
set B's label to A's label + 1
add B to the queue.
fi
od
od
All actors end up labeled with their Kevin Bacon number. Actors with no Kevin Bacon number, (e.g. whose only movie was a one man show) will remain unlabeled.
Time and space are linear in the size of the database of actors and movies, since no actor gets added to the queue more than once (exercise: prove this).
You can't do better than that because the path between two actors could pass trough every other actor. (only if each actor was only in two movies, but the length of the path can be proportional to the number of actors even if that isn't true.)
If someone makes a new movie, updating all the numbers could also take time proportional to the size of the database, since that is the only bound on how many labels need to change.
The average time for an update depends on the joint distribution of movies and actors. I don't know if there are any bounds on it (but haven't thought about it).
Ralph Hartley
.
- Follow-Ups:
- References:
- Prev by Date: Re: What complexity class is 6 Degrees of Kevin Bacon?
- Next by Date: Re: What complexity class is 6 Degrees of Kevin Bacon?
- Previous by thread: Re: What complexity class is 6 Degrees of Kevin Bacon?
- Next by thread: Re: What complexity class is 6 Degrees of Kevin Bacon?
- Index(es):
Relevant Pages
|
