Finding independent sets so that all nodes are hit frequently
Approach 1: Use ILP

If you want an algorithm that might work in practice as long as the graph is not too large, one approach is to formulate this as an integer linear problem.

That's pretty straightforward in this case.  We'll have $k|V|$ integer variables.  In particular, $x_{v,i}$ will be $1$ if the vertex $v$ is included in the independent set in the $i$th iteration and $0$ otherwise.

First, let's encode the constraint that the $x_{\cdot,i}$ have to encode an independent set in each iteration.  We get $0 \le x_{v,i} \le 1$ and

$$x_{v,i} + x_{w,i} \le 1 \quad \forall (v,w) \in E.$$

Next, note that $x_{v,1} + x_{v,2} + \dots + x_{v,k}$ counts how many times each vertex is covered across the $k$ iterations.  We want this to be at least $r_v$, so we get the constraint

$$x_{v,1} + x_{v,2} + \dots + x_{v,k} \ge r_v \quad \forall v \in V.$$

Now throw an integer linear solver at the problem, and hope that it finds a solution.  The worst-case running time is exponential, but integer linear solvers sometimes work a lot better than you'd expect, so as long as the graph is not too large, it might just work.

If you want to find the smallest $k$ such that this can be solved, use binary search or linear search on $k$.

You can also formulate a similar version that works using SAT, and then throw a SAT solver at it.  It's a little more complex because you'll need to encode the constraint $x_{v,1} + x_{v,2} + \dots + x_{v,k} \ge r_v$ in SAT, but it can be done (e.g., by building a circuit for a small adder and then translating it to SAT using the Tseitin transform).

Approach #2: A greedy heuristic

Here is an alternative approach, that might work even on larger graphs.  It won't find the optimal solution, but it might find a solution that is not too much worse than the optimal solution.

The problem reminds me of a set cover problem: in each iteration you select one set, and you want the union of the sets to cover the universe.  One natural approach to set-cover-like problems is to try to apply the greedy algorithm for set cover: in each iteration, choose an independent set that gives you as much progress as possible.

Let me start by assuming $r_v=1$ for all vertices $v$, for simplicity.  Then you could use the following algorithm:


Initially all vertices are uncovered.  Set $i=1$.
Find an independent set $I$ that covers as many of the uncovered vertices as possible.  Choose that one, and output it as the independent set $I$ as the one to use in the $i$th iteration.  Increment $i$ and go back to step 2.


You can now plug in any algorithm you like for finding independent sets, including a heuristic or approximation algorithm.  There's lots written on that subject so you might be able to re-purpose any of a number of different algorithms.

What about the general case where the $r_v$'s are arbitrary?  Well, in any given iteration, you can evaluate each candidate independent set by how much incremental coverage it adds, where now the coverage is given by the sum of the counters on all of the vertices.  So, in each iteration, choose the independent set with the largest incremental coverage that you can find.  This might give a reasonable approximation algorithm for your initial problem.