Assume we have a simple graph \(G=(V,E)\). An independent set of vertices \(U\) is a subset \(U\subseteq V\) such that any pair of elements \(u\neq v\) in \(U\) do not form an edge, i.e. \(\{u,v\}\not\in E\). A maximal independent set is a maximal (with respect to inclusion) set in the collection of independent subsets.
Our problem today is to calculate the size of any maximal independent subset in a given graph \(G\). This number is called the independence number of \(G\), and is usually denoted by \(\alpha(G)\).
There is a recursive formula that give us the independence number. \[ \alpha(G) = \max( \alpha(G-v), 1+\alpha(G-v-N(v)) ) \] where
\(G-v\) is the graph obtained from \(G\) by removing \(v\) and all edges incident to \(v\)
\(G-v-N(v)\) is the graph obtained from \(G\) by removing \(v\) and the set of neighbors \(N(v)\) of \(v\).
The formula comes from the following simple idea: fix a vertex \(v\). Given a maximal independent subset \(U\) there are two cases. Either \(v\in U\), or \(v\not\in U\). In the first case no neighbors of \(v\) is in \(U\). In that case \(U\setminus\{v\}\) is an independent set in \(G-v-N(V)\). If \(v\not\in U\) then \(U\) is an independent set in \(G-v\).
I will use list of edges to represent graphs. However, to accomodate graphs without edges, I will need loops.
(defparameter G
'((0 1) (1 2) (2 3) (2 4)
(0 0) (1 1) (2 2) (3 3) (4 4)))GBefore I present my implementation, I will need some helper functions. First, a function that returns the set of vertices of a graph:
(defun vertices (G)
(if G (remove-duplicates (reduce #'union G))))
(vertices G)VERTICES
(3 1 0 2 4)A function that returns the set of neighbors of a vertex in a graph:
(defun neighbors (G v)
(vertices
(remove-if-not (lambda (edge) (member v edge)) G)))
(neighbors G 2)NEIGHBORS
(4 1 3 2)A function that deletes a subset of vertices
(defun delete-vertices (G vs)
(if (or (null vs) (null G))
G
(delete-vertices
(remove-if (lambda (edge) (member (car vs) edge)) G)
(cdr vs))))
(delete-vertices G (neighbors G 0))DELETE-VERTICES
((2 3) (2 4) (2 2) (3 3) (4 4))And finally an implementation:
(defun independence (G)
(if (null G)
0
(let* ((vs (vertices G))
(v (car vs))
(ns (neighbors G v)))
(max (independence (delete-vertices G (list v)))
(1+ (independence (delete-vertices G ns)))))))INDEPENDENCEand let us test on \(G\) we defined at the beginning:
(independence G)3First, let me write some functions that return a standard list of graphs: The discrete graph (vertices without any edges) on \(n\) vertices:
(defun discrete (n)
(loop for i from 0 below n
collect
(list i i)))
(discrete 5)DISCRETE
((0 0) (1 1) (2 2) (3 3) (4 4))The star graph on \(n\) vertices:
(defun star (n)
(union
(discrete n)
(loop for i from 1 below n
collect
(list 0 i))))
(star 5)STAR
((4 4) (3 3) (2 2) (1 1) (0 0) (0 1) (0 2) (0 3) (0 4))The line graph on \(n\) vertices:
(defun line (n)
(union
(discrete n)
(loop for i from 0 below (1- n)
collect
(list i (1+ i)))))
(line 4)LINE
((3 3) (2 2) (1 1) (0 0) (0 1) (1 2) (2 3))The complete graph on \(n\) vertices:
(defun complete (n)
(union
(discrete n)
(loop for i from 0 below (1- n)
append
(loop for j from (1+ i) below n
collect
(list i j)))))
(complete 4)COMPLETE
((2 3) (1 3) (1 2) (0 3) (0 2) (0 1) (0 0) (1 1) (2 2) (3 3))The graph on \(n\) vertices on a cycle:
(defun cycle (n)
(union
(line n)
(list (list 0 (1- n)))))
(cycle 4)CYCLE
((2 3) (1 2) (0 1) (0 0) (1 1) (2 2) (3 3) (0 3))And the wheel graph on \(n\) vertices
(defun wheel (n)
(union
(cycle n)
(star n)))
(wheel 4)WHEEL
((0 3) (3 3) (2 2) (1 1) (0 0) (0 1) (1 2) (2 3) (3 3) (2 2) (1 1) (0 0) (0 1)
(0 2) (0 3))So, here are some tests. First, discrete graphs
(loop for i from 1 to 20 collect (independence (discrete i)))(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)Next, line graphs:
(loop for i from 2 to 20 collect (independence (line i)))(1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10)Next, cycle graphs:
(loop for i from 3 to 20 collect (independence (cycle i)))(1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10)Now, wheel graphs:
(loop for i from 4 to 20 collect (independence (wheel i)))(2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10)And finally complete graphs:
(loop for i from 3 to 20 collect (independence (complete i)))(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)