PO1 M INIMUM R EGISTER S UFFICIENCY

     
• I NSTANCE : Directed acyclic graph .
• S OLUTION : Computation for G that uses k registers, i.e., an ordering of the vertices in V and a sequence of subsets of V , each satisfying , such that is empty, contains all vertices with in-degree 0 in G , and, for , , , and contains all vertices u for which .
• M EASURE : Number of registers, i.e., k .

• Good News: Approximable within [ 232 ].
• Garey and Johnson: PO1