Calculating Vertex Covers in Clojure

Description of the problem

Today, I am going to write a clojure function that solves vertex cover problem for a given undirected graph.

Given a graph \(G = (V,E)\) a vertex cover is a subset \(C\subseteq V\) such that when we add all edges incident to every vertex in \(C\) we get all vertices of \(G\). For example, any vertex \(v\) in the complete graph \(K_n\) would form a cover by itself since every other vertex is connected to \(v\). On the other hand, any graph on \(n\) vertices with no edges is on the opposite end since one would need all of \(V\) to get a cover.

An algorithm

Algorithm Cover
Input: A graph G as a list of neighbors for each vertex.
       A subset S of vertices.
Output: A subset C of vertices covering G.
Begin
  If G is empty then
     Return S
  End If
  Take a vertex v with the largest degree.
  If deg(v) = 0 then
     Return S
  End If
  Let H be G from which all edges incident to v are removed.
  Return Cover( H , S ∪ {v} )
End

An implementation

As I described above, a graph is a map of subsets of neighbors.

(def G {0 #{1 2 3}, 1 #{0 2}, 2 #{0 1 3 4}, 3 #{0 2}, 4 #{2}}) 

#'covering/G

Next, a function that finds a vertex with the largest degree.

(defn largest-degree [G]
  (->> (into [] G)
       (map (fn [[x y]] [x (count y)]))
       (sort #(> (last %1) (last %2)))
       first
       first))

#'covering/largest-degree

Let us test:

(G (largest-degree G))

#{0 1 4 3}

Now, a function that removes a vertex and every edge incident to it.

(defn remove-vertex [v G]
   (->> (dissoc G v)
        (map (fn [x] {(key x) (->> (val x)
                                   (remove #{v})
                                   (into #{}))}))
        (into {})))   

#'covering/remove-vertex

Let us test:

(remove-vertex 2 G)

{0 #{1 3}, 1 #{0}, 3 #{0}, 4 #{}}

As for the function, I’ll write

(defn cover 
  ([G] (cover G []))
  ([G S] (let* [v (largest-degree G)
                H (remove-vertex v G)]
            (if (or (empty? G)
                    (empty? (G v)))
                S
                (recur H (conj S v))))))

#'covering/cover

Let us test.

(cover G)

[2 0]

How do we know that we get the correct answer? Well, if we remove all of the vertices in the cover, what remains has to be an independent subset. Let us see if this works.

(loop [S (cover G)
       H G]
   (if (empty? S)
       H
       (recur (rest S) (remove-vertex (first S) H))))

{1 #{}, 3 #{}, 4 #{}}

Let us construct a random tree and test our code on it:

(defn random-tree [n]
   (->> (range 1 (* 2 n))
        (map (fn [x] {(rand-int x) #{x}}))
        (reduce  #(merge-with union %1 %2))
        (into {})))

(let [tree (random-tree 100)]
   (loop [S (cover tree)
          H tree]
      (if (empty? S)
          H
          (recur (rest S) (remove-vertex (first S) H)))))

#'covering/random-tree
{119 #{}, 31 #{}, 40 #{}, 56 #{}, 61 #{}, 111 #{}, 134 #{}, 35 #{}, 76 #{}, 16 #{}, 98 #{}, 73 #{}, 10 #{}}