We present a spatial renormalization group algorithm to handle immiscible two-phase flow in heterogeneous porous media. We call this algorithm FRACTAM-R, where FRACTAM is an acronym for Fast Renormalization Algorithm for Correlated Transport in Anisotropic Media, and the R stands for relative permeability. Originally, FRACTAM was an approximate iterative process that replaces the L x L lattice of grid blocks, representing the reservoir, by a (L/2) x (L/2) one. In fact, FRACTAM replaces the original L x L lattice by a hierarchical (fractal) lattice, in such a way that finding the solution of the two-phase flow equations becomes trivial. This triviality translates in practice into computer efficiency. For N = L x L grid blocks we find that the computer time necessary to calculate fractional flow F(t) and pressure P(t) as a function of time scales as tau-N-1.7 for FRACTAM-R. This should be contrasted with the computational time of a conventional grid simulator tau similar to N-2.3. The solution we find in this way is an acurate approximation to the direct solution of the original problem.