Union of minimum vertex covers algorithm.

UMVC.jl

using SparseArrays, Random
function UMVC(A::SparseMatrixCSC{Int64,Int64},
              ncovers::Int64=300)
  edges = 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                                                                                                                                       
    vc = zeros(Int64, size(A,1))
    for (i, j) in shuffle(edges)
      if vc[[i,j]] == [0,0]; vc[[i,j]] .= 1; end
    end
    # Reduce to a minimal cover                                                                                                                                                           
    while true
      vc_size = sum(vc)
      for c in shuffle(findall(vc .== 1))
        nbrs = findnz(A[:,c])[1]
        if sum(vc[nbrs]) == length(nbrs); vc[c] = 0; end
      end
      if sum(vc) == vc_size; break; end
    end
    umvc[findall(vc .== 1)] .= 1
  end
  degs = vec(sum(A, dims=1)) # node degrees                                                                                                                                               
  return sortperm(collect(zip(umvc, degs)), rev=true)
end