# LightGraphs for Luby's algorithm

I am trying to use the LightGraphs and associated packages to implement Maximal-Independent-Set algorithms: Luby, Blelloch

Both algorithms work by iterating over vertices and based on a relation between a vertex and its neighbors, add the vertex to the MIS (maximal independent set) and mark that vertex and its neighbors as “inactive” (ignoring them in the following iterations of the algorithm)

I tried to create a copy of the graph (`squash` / `copy`) in the beginning of the function, and remove inactive vertices making the graph gradually smaller (focusing on a sequential implementation of these algorithms)

However, removing vertices from the graph (`rem_vertex!`, `rem_vertices!`) relabels the vertices of the graph, thus the algorithms fails

My “solution” was to convert the copy of the graph to a `MetaGraph` and add an `:active` property (initially `true`).
This works, but it is not elegant, and worse it is very inefficient since as the algorithm progresses it has to iterate over all vertices skipping the ones marked as inactive

Is there a way to remove vertices from a graph while maintaining the original vertex numbers?

If you are willing to use a different graph theory package, I can offer this solution:

``````using SimpleGraphs

"""
`maximal_indep_set(G)` returns a maximal independent set
of vertices of `G`.
"""
function maximal_indep_set(G::SimpleGraph{T}) where T
S = Set{T}()           # place to hold the answer
GG = deepcopy(G)       # copy of G to destroy
while NV(GG)>0
v = first(GG.V)    # get a vertex
Nv = GG[v]         # and its neighbors
push!(S,v)         # add v to the set S
delete!(GG,v)      # remove v and its neighbors
for w in Nv
delete!(GG,w)
end
end
return S
end
``````

Note that a maximal independent set is not necessarily a maximum independent set. For example:

``````julia> G = Cycle(12)
Cycle (n=12, m=12)

julia> maximal_indep_set(G)
Set{Int64} with 5 elements:
7
9
4
2
11
``````

For a maximum independent set, try this:

``````julia> using SimpleGraphAlgorithms

julia> max_indep_set(G)

# verbose output from Cbc omitted

Set{Int64} with 6 elements:
4
10
2
8
6
12
``````
2 Likes