
Boosting.  If G has a C-potential, it can be computed by boosting.
Initialize Phi to be zero for each node.  Then attempt to boost the nodes
in arbitrary order.  Boosting a node means increasing its potential to where
it satisfies the pullback condition.   Boosting "converges" when the
pullback condition holds for every node.  Boosting "diverges" when Phi
is positive for every node.  If boosting converges, the resulting Phi is a
C-potential.  If boosting diverges, G is not C-competitive.  When boosting,
we visit nodes in arbitrary order, but it is important that no node starves.
Convergence holds only if no node can be boosted, which can be verified
by making one complete pass of the graph, failing to boost any node.

The no-cost subgraph Z can be found by a form of boosting, also.  Assume that
an exact C-potential Phi is already given.  Initialize Z = G, then try to
delete nodes of Z in arbitrary order.  We can delete a black node x from Z
if x has at least one exact out-edge with positive weight, or if x has an
out-edge to a red node not in Z.  We can delete a red node y if every out-edge
of y either has positive weight or goes to a black node that is not in Z.
The process converges when there is no remaining node in Z that can be deleted.

A simple example.  Consider the following graph with four nodes, two black
and two red.  Let the black nodes be called x and z, and let the red nodes
be called y and w.  We have three black edges and three red edges, with
weights given by the following two tables:

       y    w               x    z

   x   1    0           y   1    #

   z   #    1           w   0    2

   black edges           red edges

where # denote that the edge does not exist, or alternatively, has infinite
cost.  Let us now let C = 2.  By boosting, we obtain an exact 2-potential
Phi where Phi(x) = 2, Phi(y) = 3, Phi(z) = 0, and Phi(w) = 2.  All edges
are exact except for (x,y).  We then construct Z by boosting.  We can
delete y because it has no out-edge of zero weight.  We can delete z
because it has an exact out-edge of positive weight.  Then, we cannot
delete w, because it has a zero edge to x, which is still in Z, and we
cannot delete x, because its only exact out-edge has zero weight and goes
to w, which is still in Z.  Thus, boosting converges, and Z = {x,w}, which
is non-empty.  We cannot conclude that the competitiveness of G is 2.

Start over again with C = 1.  By boosting, we obtain an exact 1-potential
Phi where Phi(x) = 1, Phi(y) = 2, Phi(z) = 0, and Phi(w) = 1.  All edges
are exact except (w,z).  We then compute Z.  We can delete z, since
(z,w) is an exact edge of positive weight.  We can delete y, since there
is no zero cost edge from y.  We can delete x, since (x,y) is an exact edge
of positive weight.  We can delete w because there is no out-edge from
w which goes to a node that is still in Z.  Thus, Z is empty.  We conclude
that the competitiveness of G is 1.
