Lecture 10 - Maximum independent set

A set of variables $U \subseteq V$ is independent in an undirected graph if ${u,v} \notin E$ for all $u,v \in U$. This is different from a maximal independent set

Left is maximal and right is maximum.

image-20210304170820835

There is no polynomial time algorithm to find a maximum independent set. The black vertices form independent sets in the graph.

Implementation for MIS

Let $G = (V,E)$ be an undirected graph. $\alpha(G) = 0$ if and only if $V = \empty$. $\forall v \in V$ we have $\alpha(G) = \max(\alpha(G-v), 1 + \alpha(G - N[v]))$

Pseudocode

image-20210304171526686

The worst case is if the vertex $v$ has no neighbors, which would give it a running time of $\deg(v) \ge 1$ which is the same running time of the Fibonacci sequence

A vertex is isolated if $N(v) = \empty$

Pendant vertex

A vertex $v$ is pendant if $\deg(v) = 1$. For every pendant vertex there is an MIS containing it

I am no longer paying attention