title: Family Tree Algorithm
body: <p>I'm working on putting together a problem set for an intro-level CS course and came up with a question that, on the surface, seems very simple:</p>
  
  <blockquote>
    <p>You are given a list of people with the names of their parents, their birth dates, and their death dates.  You are interested in finding out who, at some point in their lifetime, was a parent, a grandparent, a great-grandparent, etc.  Devise an algorithm to label each person with this information as an integer (0 means the person never had a child, 1 means that the person was a parent, 2 means that the person was a grandparent, etc.)</p>
  </blockquote>
  
  <p>For simplicity, you can assume that the family graph is a DAG whose undirected version is a tree.</p>
  
  <p>The interesting challenge here is that you can't just look at the shape of the tree to determine this information.  For example, I have 8 great-great-grandparents, but since none of them were alive when I was born, in their lifetimes none of them were great-great-grandparents.</p>
  
  <p>The best algorithm I can come up with for this problem runs in time O(n<sup>2</sup>), where n is the number of people.  The idea is simple - start a DFS from each person, finding the furthest descendant down in the family tree that was born before that person's death date.  However, I'm pretty sure that this is not the optimal solution to the problem.  For example, if the graph is just two parents and their n children, then the problem can be solved trivially in O(n).  What I'm hoping for is some algorithm that is either beats O(n<sup>2</sup>) or whose runtime is parameterized over the shape of the graph that makes it fast for wide graphs with a graceful degradation to O(n<sup>2</sup>) in the worst-case.</p>