TD14 : Approximations

Énoncé

I. Couverture de sommets

1.

Chaque sommet de $L$ est connecté à au plus un élément de $R_i$ (pour un $i$ fixé).

Comme il y a $r$ composantes $R_i$ :

  • le degré maximum d’un sommet de $L$ est $r$

  • Nombre de sommets de $R$ :

    \sum\limits_{ i=1 }^r \lfloor r/i \rfloor = r \sum\limits_{ i=1 }^r \lfloor 1/i \rfloor ≥ r \log (r+1)
  • Couverture minimale : $L$, sa taille est $r$.

2.

Si pour chaque arête $\lbrace r, l \rbrace$ ($r∈ R, l∈L$), on ajoute le sommet de $R$, alors l’algorithme naïf renvoie $R$.

Donc la solution de cette algorithme est $≥ r \log (r+1)$, et la performance de l’algo est

\frac{r\log(r+1)}{\underbrace{r}_{\text{ taille minimale}}} = 𝛺(\log r)

3.

On prend à chaque fois un élément de $R$ qui a un degré maximal et on le retire.

On peut montrer qu’à chaque itération, il existe nécessairement un sommet de $R$ qui a un degré maximal (du fait que chaque sommet de $L$ est relié à au plus un élément de chaque $R_i$).

4.

On veut montrer que le problème qui étant donné un graphe $G$ et un entier $k$ cherche à savoir s’il existe une couverture de taille $k$ est NP-dur.

3-SAT :

  • Entrée : une forme $(l^1_1 ∨ l^2_1 ∨ l^3_1) ∧ ⋯ ∧ (l^1_k ∨ l^2_k ∨ l^3_k)$ avec $l^i_j ∈ \lbrace x_1, ⋯, x_n, ¬x_1, ⋯, ¬x_n \rbrace$

  • Sortie : la formule est-elle satisfaisable ?

Pour chaque paire de variables, j’ai dans mon graphe

graph {
    rankdir=LR;
    x_i -- ¬x_i;
  }

et pour chaque clause

graph {
    rankdir=LR;
    l1_i -- {l2_i, l3_i};
    l2_i -- l3_i;
  }

Chaque $l^j_i$ est relié au sommet associé à sa valeur :

Par ex, si $l^1_i = x_1, l^2_i = ¬x_3, l^3_i = x_2$ :

graph {
    l1_i -- {l2_i, l3_i}[color=red,penwidth=3.0];
    l2_i -- l3_i[color=red,penwidth=3.0];
    l1_i -- x_1[color=blue,penwidth=2.0];
    l2_i -- ¬x_3[color=blue,penwidth=2.0];
    l3_i -- x_2[color=blue,penwidth=2.0];
    x_1 -- ¬x_1[color=green];
    x_2 -- ¬x_2[color=green];
    x_3 -- ¬x_3[color=green];
  }

On a $k$ “triangles de clauses” et $2n$ noeuds $x_i, ¬x_i$

On cherche une couverture de taille $2k+n$.

3-SAT ⟶ COVER

Si on a la valuation $v \vDash 𝜑$, alors

C ≝ \lbrace x_i \mid v(x_i) = 1 \rbrace ∪ \lbrace ¬x_i \mid v(x_i) = 0 \rbrace ∪ D

D ≝ \lbrace l^{i_1}_i, l^{i_2}_i \mid i∈⟦1, k⟧ \; ∧ \; ∀j ∈ \lbrace 1, 2, 3 \rbrace \backslash \lbrace i_1, i_2 \rbrace \; ∧ \; v(l^j_i) = 1\rbrace

pour chaque clause

l^1_i ∨ l^2_i ∨ l^3_i

COVER ⟶ 3-SAT

Il suffit de remarquer que pour tout $x_i$, on a soit $¬x_i ∈ C$ soit $x_i∈C$.

Donc on prend

v(x_i) = \begin{cases} 1 \text{ si } x_i ∈ C \\ 0 \text{ sinon} \end{cases}

Notons que comme dans chaque 3-clique, il y a forcément 2 sommets couverts, il reste $n$ sommets pour couvrir $x_i - ¬x_i$.

Donc on n’a pas $x_i$ et $¬x_i$ dans $C$.

On en déduit que pour chaque 3-clique, un littéral $l^j_i$ n’est pas couvert mais donc le noeud associé ($x_i$ ou $¬x_i$) doit être couvert.

Alors

v \vDash 𝜑

4.

$G$ est une étoile :

graph {
    v_0 -- {v_1, v_2, v_3};
  }

Si on prend les poids suivants :

graph {
    "v_0 | 2" -- {"v_1 | 1", "v_2 | 1", "v_3 | 1"};
  }

L’algo va d’abord prendre les sommets périphériques, et retourner la couverture $\lbrace v_1, v_2, v_3 \rbrace$ de taille $n-1$ (alors la couverture minimale est $\lbrace v_0 \rbrace$ de taille 1).

II.

digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label="L";
      l_1, l_2, l_3;
    }
    subgraph cluster_1 {
      label="R";
      r_1, r_2, r_3;
    }
    s -> {l_1, l_2, l_3}[color=blue,penwidth=2.0, label="w(u)"];
    l_1 -> r_1[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    l_2 -> {r_1, r_2, r_3}[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    l_3 -> r_3[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    {r_1, r_2, r_3} -> t[color=blue,penwidth=2.0, label="w(v)"];
  }

$s-t$ coupe $V ≝ S \sqcup T$ telle que $s∈S, t∈T$ et son poids est

\sum\limits_{ v∈S, v∈T, (u,v)∈E'} w'(u, v)
digraph {
    rankdir=LR;
    S_1[label="S", shape="rect"];
    T_1[label="T", shape="rect", color="green"];
    S_2[label="S", shape="rect", color="green"];
    T_2[label="T", shape="rect"];

    subgraph cluster_0 {
      label="L";
      S_1, T_1;
    }

    subgraph cluster_1 {
      label="R";
      S_2, T_2;
    }

    S_1 -> S_2;
    S_1 -> T_2[color=red,penwidth=3.0, label="compte dans la s-t coupe"];
    T_1 -> S_2[color=red,penwidth=3.0, label="compte dans la s-t coupe"];
    T_1 -> T_2;
  }

en vert : la couverture minimale, si la $s-t$ coupe est minimale

$∀u∈L, v∈ R$, si $\lbrace u,v \rbrace ∈ E$ et $u ∈ S$, alors $v∈S$.

Supposons qu’il existe $v∈T$ et $u∈S$ tq $\lbrace u, v \rbrace ∈ E$. Donc $\lbrace u, v \rbrace∈E’$.

Prenons la coupe $D = (S∪ \lbrace v \rbrace, T \backslash \lbrace v \rbrace)$.

Alors le poids de $D$ est plus petit que $(S, T)$ (on a retiré $w(u, v) = 1 + \sum\limits_{ v∈R } w(v)$ et ajouté $w(v)$).

Montrons que $C = L’∪ R’$ avec $L’= L ∩ T$ et $R’= R ∩ S$ est une couverture minimale.

a). Mq $C$ est une couverture

Soit $\lbrace u, v \rbrace ∈ E$ avec $u∈L$ et $v∈R$.

Si $u∈S$, alors $v∈S$ et donc $v∈C$ (par 1)).

Si $u∉S$ alors $u∈T$ et donc $u∈C$.

⟶ $C$ est une couverture.

b). Mq $C$ est minimale

Soit $C’$ une couverture telle que

w(C') < w (C)

On prend la $s-t$ coupe $(S’, T’)$ tq

  • $S’ = R ∩ C ∪ \lbrace u ∈ L \mid (u, v)∈ E’ \text{ et } v∈R∩C \rbrace$

  • $T’ = V’ \backslash S’$

digraph {
    rankdir=LR;
    S_1[label="S", shape="rect", style=dashed];
    T_1[label="T", shape="rect", color="green"];
    S_2[label="S", shape="rect", color="green", style=dashed];
    T_2[label="T", shape="rect"];

    subgraph cluster_1 {
      label="L";
      S_1, T_1;
    }

    subgraph cluster_2 {
      label="R";
      S_2, T_2;
    }


    S_1 -> S_2;
    S_1 -> T_2[color=red,penwidth=3.0, label="compte dans la s-t coupe"];
    T_1 -> S_2[color=red,penwidth=3.0, label="compte dans la s-t coupe"];
    T_1 -> T_2;
  }

en pointillés : $S’$

On obtient une $s-t$ coupe de poids $w(C’)$.

Mais $w(C)$ était le poids d’une $s-t$ coupe minimale ⟶ contradiction.

Algorithme

digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label = S;
      color = green;
      s;
    subgraph cluster_1 {
      label="L";
      l_1, l_2, l_3;
    }
    subgraph cluster_2 {
      label="R";
      r_1, r_2, r_3;
    }}

    subgraph cluster_3 {
      label = "T";
      color = purple;
      t;
    }
    s -> {l_1, l_2, l_3}[color=blue,penwidth=2.0, label="w(u)"];
    l_1 -> r_1[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    l_2 -> {r_1, r_2, r_3}[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    l_3 -> r_3[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    {r_1, r_2, r_3} -> t[color=blue,penwidth=2.0, label="w(v)"];
  }

Si $w(r_1) > w(l_1) + w(l_2)$

digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label = S;
      color = green;
      s;
    subgraph cluster_1 {
      label="L";
       l_3;
    }
    subgraph cluster_2 {
      label="R";
      r_2, r_3;
    }}

    subgraph cluster_3 {
      label = "T";
      color = purple;
      l_1, l_2, t, r_1;
    }
    s -> {l_1, l_2, l_3}[color=blue,penwidth=2.0, label="w(u)"];
    l_1 -> r_1[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    l_2 -> {r_1, r_2, r_3}[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    l_3 -> r_3[color=red,penwidth=3.0, label="1 + ∑_v∈R w(v)"];
    {r_1, r_2, r_3} -> t[color=blue,penwidth=2.0, label="w(v)"];
  }
S = V' - {t}
Pour chaque noeud v∈R :
  Si w(v)≥∑_{u∈L, (u,v)∈E'} w(u) :
    S = S - {u∈L | (u,v)∈E'}

III. Double couvertures

Double couverture de $V$ :

multi-ensemble $C$ tel que $∀ \lbrace u, v \rbrace ∈ E, C(u) + C(v) ≥ 2$

Poids de la double couverture :
\sum\limits_{ u∈V } w(u) \cdot C(u) = w(C)

8.

Soit $C$ une double couverture de poids minimal.

Mq pour tout $v∈V$,

C(v) ≤ 2

Si $C(u)>2$, alors la couverture $C’$ telle que $C’(v) = C(v)$ pour $v≠u$ et $C’(u)=2$ est une double couverture de poids plus petit donc $C$ n’est pas minimale.

9.

Soit $(u,v)∈E$, donc $C(u)+C(s)≥2$ donc $C(u)>0$ ou $C(v)>0$, d’où

\lbrace u, v \rbrace ∩ Supp(C) ≠ ∅

10.

La couverture $c’’= 2C’$ est une double couverture de poids $2p’$.

Donc

p ≤ 2p'

11.

$G$ :

graph {
    rankdir=LR;
    a -- {b, c};
    b -- c;
  }

$G’$

graph {
    rankdir=RL;
    subgraph cluster_0
    {
      label="L";
      a_L, b_L, c_L;
    }
    subgraph cluster_1
    {
      label="R";
      a_R, b_R, c_R;
    }
    a_L -- {b_R, c_R};
    a_R -- {b_L, c_L};
    b_R -- c_L;
    c_R -- b_L;
  }

Si c’est une couverture de $G’$, on prend $C$ tq

C(u) = C(u_R) + C(u_L)

Soit $(u, v)∈E$.

On a

C(u) + C(v) = \underbrace{C(u_R) + C(v_R)}_{≥1} + \underbrace{C(u_L) + + C(v_L)}_{≥1} ≥ 2

Si $C$ et une double couverture de $G$.

Si $C(u)=2$ alors on prend

C'(u_R) = C'(u_L) = 1

Si $C(u) = 1$, alors on prend $C’(u_L)=1$


Soit $(u_R, v_L)∈E’$.

Alors $(u, v)∈E$.

C(u)+C(v)≥ 2
  • Si $C(u)=2$, alors $C’(u_R)=1$ : ok
  • Si $C(u)=1$, alors $C’(v)≥1$ et $Cv_L)≥1$ : ok
  • Si $C(u)=0$, alors $C(v)≥2$ et $C(v_L)≥1$ : ok

13.

On calcule une couverture de poids minimal dans $G’$ (biparti), ça nous donne une double couverture $C$ dans $G$ et par la question 9, $Supp(C)$ est une couverture.

Par la question 10, la garantie de la performance est 2 (on peut avoir $Supp(C)=C$).

Leave a comment