# Finding independent sets so that all nodes are hit frequently

I have a problem, and I appreciate it if you could share your thoughts.

Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in each iteration. Then, I will increase a counter for those vertices that are in the selected IS. Initially, the counter for all vertices of the graph are zero.

With an integer programming formulation, we can choose one independent set (provided that we know the set of all ISs) in every iteration, so that the counter of each vertex $i$ in the graph is at least $r_i$ over $k$ iterations (clearly $r_i \leq k$)? In other words, we can make a plan, with IP, so that each vertex $i$ has been selected $r_i$ times over $k$ iterations. Also, with simple modification, minimum value for $k$ can be included in IP formulation. I aim at finding the minimum $k$ by which all $r_i$'s are satisfied.

Now the main concern is that the above formulation need the set of all ISs as an input. Finding this set, however, is an NP-hard problem. So, I was wondering if there there is any way to bypass the need for having all ISs? For sure, many heuristic algorithms can be developed (one example is proposed in comments below). However, I am interested to find an algorithm for which I can say something analytically, e.g. convergence proof, optimality gap, etc.

## 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:

1. Initially all vertices are uncovered. Set $i=1$.

2. 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.

• Thanks, as you mentioned the original problem or even the problem of minimizing $k$ so that all $r_i$s are satisfied, can be posed as linear programming formulation, provided that I the set of all independent sets (ISs) is available. The main problem is that finding the set of all ISs is an NP-hard problem. So, I was wondering is there any way to bypass the need for having all ISs? For sure, many heuristic algorithms can be developed, yet I am more interested to find an algorithm for which I can say something analytically, e.g. convergence proof, optimality gap, etc. -Hossein
– Jeff
Jul 17 '14 at 9:35
• @Hossein, I think you need to read my algorithm again. My Approach 1 does solve this (via integer linear programming) without any assumption that the set of all independent sets is available. If that sounds magical, here's how it does it: determining whether a set is an independent set can also be formulated as an integer linear program.My ILP formulation takes into account both the requirement that in each iteration it must be an independent set, and how to choose an optimal sequence of them across $k$ iterations. In other words, my answer already does what you seem to be asking for.
– D.W.
Jul 18 '14 at 5:44