Re: What complexity class is 6 Degrees of Kevin Bacon?

hey, that's perfect! One of those things that's so obvious in
retrospect, you end up wondering why you hadn't figured it out on your
own. Thanks, very much, I think I can reawaken two very useful
utilities I had given up on.

Ralph Hartley wrote:
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

.

Relevant Pages

  • Re: Randy Quaid sues Humpback Mountain producers for $10 Million
    ... Specifically where they said that "no actors" were ... listened extensively about this movie. ... Independent Films & BBM won it. ... category are a tiny fraction of all screenplays overall. ...
    (rec.arts.movies.current-films)
  • Re: You cant get there from here
    ... >So in the case below Humphery Bogart would be Order in Movie ... >Now you can build a set of queries that will return up to the top 12 actors ... >>>MovieID ActorID Character ...
    (microsoft.public.access.gettingstarted)
  • Re: Goblet of Fire : Shocker!!
    ... None of the three principle actors are good actors, ... Emma is progressing at ... I don't think he's got much personality, ... >I thought the movie "War of the Worlds" was pretty good... ...
    (alt.fan.harry-potter)
  • Re: The Screaming Skull director
    ... I would like to know more about how the movie ... Alex Nicol, an Actors Studio trainee, appeared mostly in westerns. ... The Screaming Skull was paired variously with Terror ...
    (rec.arts.tv.mst3k.misc)
  • Re: Julia Roberts: The Ugly Whigger Cunt Bombed
    ... That's what we used to do to pretty, light-skinned girls in my ... But movie success after movie success has proved the studios' target aim ... And the number of black male actors who get to carry films is a _very_ ... But Halle Berry isn't a victim of it, ...
    (rec.arts.movies.current-films)