2
$\begingroup$

We have the following graph: enter image description here

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: enter image description here Then when we choose e=(5,7) we have C={1,4,5,7} and the graph will look as follows: enter image description here Then we can choose e=(2,3) and then we have C={1,2,3,4,5,7} and the graph will be: enter image description here 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?

$\endgroup$
2
$\begingroup$

I thought that the set $C^⋆=\{1,2,3,7\}$ is a minimal vertex cover. Is this correct? How could we prove it?

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^*$).

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?

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.

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?

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.

$\endgroup$
  • $\begingroup$ So, is a minimal vertex cover the set $C^\star=\{1,3,4,5,7\}$ ? $$$$ For the maximal independent set of vertices, is it maybe $\{1,5,6\}$ ? $$$$ Is maybe the following a maximal clique? $\{1,2,3,4\}$ ? $\endgroup$ – Mary Star Aug 12 '16 at 8:41
  • 1
    $\begingroup$ Yes. No, since $\{5, 6\}$ is an edge in the graph. No, since $\{3, 4\}$ is not an edge in the graph. $\endgroup$ – Adriano Aug 12 '16 at 8:45
  • 1
    $\begingroup$ Just show that if you try to remove any single vertex from $C^*$, some edge doesn't get covered. Yes, $\{1, 5\}$ is a maximal independent set (in fact, it's also maximum). Yes, $\{4, 5, 6, 7\}$ is a maximal clique (in fact, it's also maximum). $\endgroup$ – Adriano Aug 12 '16 at 8:55
  • 1
    $\begingroup$ You used $4$ colours, so the chromatic number is at most $4$ (can you see why the chromatic number could never be $3$?). You provided a Hamiltonian cycle, but not an Eulerian circuit (for example, you did not visit the edges $\{1, 3\}$, $\{2, 5\}$, and so on). $\endgroup$ – Adriano Aug 12 '16 at 9:20
  • 1
    $\begingroup$ That's correct. $\endgroup$ – Adriano Aug 12 '16 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.