Memory conservative maximal independent set of vertices

Question

I want to find a memory conservative yet efficient algorithm for maximal independent vertices set in a undirected graph.

The traditional algorithms use auxiliary data structures (a copy of the original graph) to implement it. I would like to avoid such parallel structure because the memory allocations are slow for a realtime implementation on and I have some memory boundaries. I just want to mark the nodes in the MIS with a boolean label. Is it possible?

Note that I don't want the maximum independent but a maximal independent set.

P.S. I know that this problem is language independent but I'm coding in C++ and STL.

Answer 1

It's difficult to answer this kind of question without knowing exactly what your data structures are. The usual tricks for near in-place graph operations are stealing two bits that would otherwise be zero from pointers and making reversible changes to the graph structure, but I'm not sure how they apply here.

From reading what you've written, it seems that there is no way to iterate through the nodes in the graph without a traversal. How are you representing the stack for, e.g., DFS?

Answer 2

Here is a solution if you have only your boolean label(i) for each node i. It takes time O(|V|+|E|), where |V| is the number of nodes and |E| is the number of edges in your input graph.

For all nodes v
   set label(v)=false;
For all nodes v
   if (all neighbors w of v have label(w)=false)
      set label(v)=true

The nodes v with label(v)=true are a maximal independent set. They are independent, since, per construction any labeled node v cannot have a labeled neighbor. And they are a maximal set, since you are only activating labels and only leave a node v unlabeled if another already labeled neighbor w prevented it.

Optimization note: If the nodes are numbered 1...n you only need to check neighbors w=1..v-1, since any other w cannot have label(w)=true.

Answer 3

I use a scratch vector or deque<bool> used to indicate which vertices are used by elements, or edges, or facets, ...

std::deque<bool> used(vertex.size(), false);
for (size_t e = 0; e < edge.size(); ++e)
{
    used[edge[e].v1] = true;
    used[edge[e].v2] = true;
}

Now used == true indicates all the used vertices. The others could be collapsed out if you wanted.