Union of minimum vertex covers.

UMVC.jl

function UMVC(A::SparseMatrixCSC{Int64,Int64}, ncovers=300)
  edgevec = filter(e -> e[1] < e[2],
                   collect(zip(findnz(A)[1:2]...)))
  umvc = zeros(Int64, size(A,1))
  for _ in 1:ncovers
    # Run 2-approximation with random edge ordering                                                                                                                                  
    cover = zeros(Int64, size(A,1))
    edge_queue = shuffle(edgevec)
    while length(edge_queue) > 0
      i, j = pop!(edge_queue)
      if cover[[i,j]] == [0,0]; cover[[i,j]] = [1,1]; end
    end
    # Reduce to a minimal cover                                                                                                                                                      
    while true
      reduced = false
      for c in shuffle(find(cover .== 1))
        nbrs = find(A[:,c])
        if sum(cover[nbrs]) == length(nbrs)
          cover[c] = 0
          reduced = true
        end
      end
      if !reduced; break; end
    end
    umvc[cover .== 1] = 1
  end
  d = vec(sum(A,2))  # degrees of nodes                                                                                                                                              
  return [sort(find(umvc .== 1), by=v->d[v], rev=true);
          sort(find(umvc .== 0), by=v->d[v], rev=true)]
end