We have the following graph:
I want to find a minimal vertex cover. I thought that the set $C^\star=\{1,2,3,7\}$ is a minimal vertx cover. Is this correct? How could we prove it?
$$$$
Then I want to find a vertex cover using the following approximation algorithm
C <- 0
while E ≠ 0 do
choose e = (u,v) ∈ E arbitrary
C <- C U {u,v}
G <- G - {u,v}
return C
I have done the following:
Suppose we start with e=(1,4) then C={1,4} and the graph is the following:
Then when we choose e=(5,7) we have C={1,4,5,7} and the graph will look as follows:
Then we can choose e=(2,3) and then we have C={1,2,3,4,5,7} and the graph will be:
Have we finished now?
Is a minimal vertex cover the set $C=\{1,2,3,4,5,7\}$ ?
Does this mean that no matter which edge we choose at each step the minimal vertex cover will contain $6$ vertices?
$$$$
After that I want to find a maximal independent set of vertices and a maximal clique. Could you give me some hints how we could find them?
No, because it does not cover all edges (in particular, none of the edges $\{4, 5\}, \{5, 6\}, \{4, 6\}$ are covered by any vertex in $C^*$).
Yes, you've correctly implemented the greedy $2$-approximation algorithm. It is not minimal though: observe that $C$ has a subset $\{1, 3, 4, 5, 7\}$, which is still a vertex cover. So this greedy algorithm is not guaranteed to be optimal.
As a general heuristic, try a modified greedy algorithm. When picking vertices, don't just pick any random one; try picking the one with the lowest (or highest) degree. Then remove it (and anything else that we know is safe to remove) from the graph and repeat.