Vertex cover randomisé

philjourney

Bonjour,

je dois résoudre un problème et je me demandais si mon raisonnement est correct et vous sollicite ainsi pour vos retours.

Le problème est le suivant:

soit $G = (V, E)$ un graph. Afin de construire un vertex cover $S$ pour $G$, on considère l'algorithme suivant:

• On initialise $S = \emptyset$

• On itère sur chaque arête $e = \{u,v\} \in E$. Si aucun sommet dans $S$ ne couvre $e$ alors on sélectionne avec une probabilité $p= 0.5$ le sommet $u$, sinon le sommet $v$. On ajoute ce sommet à $S$.

Soit $S_i$ l'ensemble des sommets sélectionnés après la $i$-ème itération et soit $S^*$ la solution optimale. Montrer que l'inégalité

$$
\mathbb{E}[|S_i \cap S^*|] \geq \mathbb{E}[|S_i \setminus S^*|]
$$

est toujours vraie.

Voici ma solution :

Preuve par induction sur $i$:

• Case de base (BC): $i=1$ On considère une arête $\{u,v\} \in E$

Il faut montrer que $\mathbb{E}[|S_1 \cap S^*|] \geq \mathbb{E}[|S_1 \setminus S^*|]$ avec

$\mathbb{E}[|S_1 \cap S^*|] = 1 \cdot \mathbb{P}(|S_1 \cap S^*| = 1)$

Notons que $|S_1 \setminus S^*| = 1 \iff |S_1 \cap S^*| = 0$

$\mathbb{E}[|S_1 \setminus S^*|] = 1 \cdot \mathbb{P}(|S_1 \setminus S^*| = 1) = 1-\mathbb{P}(|S_1 \cap S^*| = 1)$  ​

Par définition, dans un vertex cover une arête est couverte par au minimum un de ses sommets. Ainsi:

$\mathbb{P}(\{u,v\} \subset S^*) \geq 0$ donc $\mathbb{P}(u \in S^*) \geq 0.5$ et $\mathbb{P}(v \in S^*) \geq 0.5$

Ainsi

$$
\begin{align*} \mathbb{P}(|S_1 \cap S^*| = 1) &= \mathbb{P}\underbrace{(\underbrace{\{u\in S_1, \,u\in S^*\}}_{\text{indépendance}} \sqcup \underbrace{\{v \in S_1 ,\, v \in S^*\}}_{\text{indépendance}})}_{\text{disjoints}} \\[5pt] & = \mathbb{P}(u\in S_1)\cdot \mathbb{P}(u\in S^*) + \mathbb{P}(v\in S_1)\cdot \mathbb{P}(v\in S^*)\\[5pt] & \geq 0.5 \cdot 0.5 + 0.5 \cdot 0.5 = 0.5 \end{align*}
$$

$\implies$

$$
\mathbb{E}[|S_1 \cap S^*|] = \mathbb{P}(|S_1 \cap S^*| = 1) \geq 0.5 \\[10pt] \mathbb{E}[|S_1 \setminus S^*|] = \mathbb{P}(|S_1 \setminus S^*| = 1) = 1 - \mathbb{P}(|S_1 \cap S^*| = 1) \leq 0.5
$$

• Hypothèse de l'induction (IH)

Pour tout itération $k, k \in \mathbb{N}$ l'inégalité $\mathbb{E}[|S_k \cap S^*|] \geq \mathbb{E}[|S_k \setminus S^*|]$ est vraie

• $k \leadsto k+1$

il faut montrer que $\mathbb{E}[|S_{k+1} \cap S^*|] \geq \mathbb{E}[|S_{k+1} \setminus S^*|]$

1. Cas: l'arête considérée lors de l'itération $k+1$ est déjà couverte par un sommet dans $S_{k}$

   $S_{k+1} = S_{k}$

$$
\implies \mathbb{E}[|S_{k+1} \cap S^*|] = \mathbb{E}[|S_{k} \cap S^*|] \stackrel{\text{(IH)}}{\geq}\mathbb{E}[|S_k \setminus S^*|]= \mathbb{E}[|S_{k+1} \setminus S^*|]
$$

1. Cas: l'arête considérée lors de l'itération $k+1$ n'est pas couverte

$$
\begin{align*} \mathbb{E}[|S_{k+1} \cap S^*|] &= \mathbb{E}[|S_{k} \cap S^*| + |S_{1} \cap S^*|]\\[5pt] &\stackrel{\text{lin.}}{=} \underbrace{\mathbb{E}[|S_{k} \cap S^*|]}_{\stackrel{\text{(IH)}}{\geq} \mathbb{E}[|S_{k} \setminus S^*|]} + \underbrace{\mathbb{E}[|S_{1} \cap S^*|]}_{\stackrel{\text{(BC)}}{\geq} \mathbb{E}[|S_{1} \setminus S^*|]} \\[5pt] &\geq \mathbb{E}[|S_{k}\setminus S^*| + |S_{1}\setminus S^*|] = \mathbb{E}[|S_{k+1}\setminus S^*|] \end{align*}
$$

Je me demande en particulier si la première étape $i=1$ est correcte ou s'il eut plutôt fallu faire au cas par cas avec d'abord:

• $u \in S^* \land v \notin S^*$ 
• ensuite $u \notin S^* \land v \in S^*$
• et enfin $u \in S^* \land v \in S^*$

Je vous remercie pour vos commentaires et suggestions

Heuristique

Pour $i = 0$, c'est encore plus simple car $S_0 = \varnothing$ donc les 2 espérances sont nulles.

Tu peux initialiser à 1 si tu préfères mais cela te force à faire 2 fois la preuve d'hérédité.

philjourney

Merci pour la réponse, je crois que $i$ est défini dans l'énoncé comme étant un naturel non nul. Je viens de voir que j'avais initialisé à $i=0$ et j'ai corrigé.

Merci pour la remarque.

Heuristique

Mais tu te ferais beaucoup moins suer en initialisant à $i = 0$ justement...

philjourney

Quelque chose doit m'échapper, je ne vois pas comment je pourrais utiliser l'inégalité

$$
\mathbb{E}[|S_1 \cap S^*|] \geq \mathbb{E}[|S_i \setminus S^*|]
$$
lors de l'hérédité $k \leadsto k+1$ si je ne l'ai pas auparavant montré. Or c'est justement ce que je montre en initialisant $i=1$. 

Heuristique

Ce que je dis, c'est que tu commences par montrer $H(0) \Rightarrow H(1)$ pour l'initialisation (donc l'hérédité dans le cas particulier $k= 0$) puis tu montres $\forall k, H(k) \Rightarrow H(k+1)$.

Une méthode qui te ferait gagner du temps et de la place serait de montrer $H(0)$ (qui est trivial) puis de montrer $\forall k, H(k) \Rightarrow H(k+1)$. Cela conclut également et t'évite de faire 2 fois une preuve d'hérédité.

philjourney

J'ai enfin compris! Merci bien