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.