TD15 : Algorithmes d’approximation

Énoncé

I. Multiway Cut

1.

  graph {
    rankdir=TB;
    s_1 -- t_1[label="2-𝜀"];
    t_1 -- {t_2, t_3}[label="1"];
    t_2 -- s_2[label="2-𝜀", color="blue"];
    t_3 -- s_3[label="2-𝜀", color="blue"];
    t_2 -- t_3[label="1"];
  }
  • Si on prend les trois arêtes internes, on a une coupe de poids 3.

  • Si on enlève deux arêtes externes (bleues), on a un coupe de taille $4-2𝜀$

    • donc si $𝜀>1/2$, son poids est strictement inférieur à la coupe précédente.
  • Si on enlève une arête externe (bleue), on doit enlever deux arêtes internes, et le poids de la coupe est $4-𝜀$

Le première coupe est avantageuse pour $𝜀<1/2$, la deuxième est avantageuse pour $1/2 < 𝜀 < 2$

3.

$C_i$ une coupe de poids minimale qui sépare $s_i$ des autres sommets (dans l’ex précédent : $C_i = (\lbrace s_i \rbrace, V\backslash \lbrace s_i \rbrace)$, $w(C_i) = 2-𝜀$)

C = \bigcup_{i≠n} C_i

où $C_n = argmax_{C_i} (w(C_i))$

Soit $s_i, s_j$, on veut montrer que $C$ sépare $s_i$ et $s_j$.

On peut supposer que $i≠n$.

Donc $C_i$ sépare $s_i$ et $s_j$, donc $C$ sépare $s_i$ et $s_j$.


On veut montrer que l’on peut calculer $C_i$ en temps polynomial.

On regroupe tous les noeuds dans $S \backslash \lbrace s_i \rbrace$ en un noeud $v$ et pour tout $u∈V \backslash (S ∪ \lbrace s_i \rbrace)$ :

w'(u, v) = \sum\limits_{ s∈ S \backslash \lbrace s_i \rbrace} w(u,s) ⟶ \text{ graphe } G'

Calculer une $s_i - v$ coupe dans $G’$ se fait en temps polynomial.

Une $s_i - v$ coupe dans $G’$ correspond à une coupe $s_i - S \backslash \lbrace s_i \rbrace$ dans $G$ de même poids.

Si on prend une coupure minimale dans $G$ qui sépare $s_i$ et $S\backslash \lbrace s_i \rbrace$ alors cette coupure est aussi dans $G’$ de même poids (cette coupure n’inclut pas d’arête entre $s_j$ et $s_{j’}$ pour $j, j’≠i$)

4.

Soit $A⊆E$ une coupure optimale.

Pourquoi $G’ = (V, E\backslash A)$ n’a pas plus de $k$ composantes connexes ?

Car sinon, il existe une composante $C$ qui ne contient aucun $s_i$, et comme le graphe $G$ est connexe, il existe une arête $(u,v)$ avec $v∈C, u∉C$.

Mais alors $A\backslash (u,v)$ est une toujours une coupe, de poids plus petit que $A$ (comme les poids sont positifs).


Montrons que

\sum\limits_{ i=1 }^k w(A_i) = 2w(A)

Or :

A_i ≝ \underbrace{\lbrace (u, v) \mid u∈V_i \text{ et } v∉V_i \rbrace}_{≝ \, E_i}

où $V_i$ est la composante connexe contenant $s_i$

Dans

\sum\limits_{ i=1 }^k w(A_i)

on compte donc chaque arête deux fois, d’où le résultat.

5.

w(C_i)≤w(A_i)

par minimalité de $C_i$

6.

C_n ≥ C_i \\ ⟹ k C_n ≥ \sum\limits_{ i=1 }^k C_i \\ ⟹ C_n ≥ \frac 1 k \sum\limits_{ i=1 }^k C_i

7.

Le poids fourni par l’algorithme d’approximation est

w(C) ≤ \sum\limits_{ i=1 }^k w(C_i) - w(C_n) \\ ≤ (1- \frac 1 k) \bigg(\sum\limits_{ i=1 }^k w(C_i)\bigg) \\ ≤ (1- \frac 1 k) \bigg(\sum\limits_{ i=1 }^k w(A_i)\bigg) \\ ≤ 2 (1- \frac 1 k) w(A)

8.

On généralise l’exemple de la première question, où on avait $k=3$ :

  graph {
    rankdir=TB;
    s_1 -- t_1[label="2-𝜀"];
    t_1 -- {t_2, t_3}[label="1"];
    t_2 -- s_2[label="2-𝜀", color="blue"];
    t_3 -- s_3[label="2-𝜀", color="blue"];
    t_2 -- t_3[label="1"];
  }

Pour $𝜀$ très petit, la coupe optimale est de poids $k$ et la coupe obtenue par l’algo d’approximation est $(2-𝜀)(k-1)$.

Le ratio est

\frac{(2-𝜀)(k-1)}{k} \underset{𝜀⟶0}{⟶} 2\Big(1 - \frac 1 k\Big)

II. Gomory-Hu Trees

NB : La coupe minimale dans un arbre $T$ est l’arête de poids minimal dans le chemin de $s$ à $t$ dans $T$.


1.

Pour tous $u, v∈V$, on note $f(u,b)$ le poids de la $u-v$ coupe optimale.

Si

f(u,v)≤ f(u,w)≤f(v, w)

alors $f(u,v) = f(u,w)$

Soit $C = (A, B)$ la coupe optimale.

  • Si $w∈B$, alors $C$ est une $(u,w)$-coupe

    • donc $w(C)=f(u,v) ≥ f(u, w) ⟹ f(u,v) = f(u,w)$
  • Si $w∈A$, $f(u, v)≥f(v, w) ≥ f(u, w)$, d’où le résultat

2.

Mq dans le graphe

$G = (V, V×V\backslash \lbrace (u, u) \mid u ∈ V \rbrace)$ avec $f$ la fonction de poids.

Si on a un cycle, alors il y a deux arêtes de même poids dans ce cycle, par induction sur la taille $k$ du cycle.

  • Pour $k=3$ :

    Comme l’ordre est total, on peut supposer que

    f(u_1, u_2)≤ f(u_1, u_3)≤ f(u_2, u_3)

    Par la question 1, $f(u_1, u_2) = f(u_1, u_3)$

  • Prenons un cycle, de taille $k>3$, $(u_0 ⋯ u_k)$

    Supposons $f(u_0, u_1)≤ f(u_1, u_2)$

    • Cas 1 : si $f(u_1, u_2) ≤ f(u_0, u_2)$, alors par la question 1, $f(u_0, u_1) = f(u_1, u_2)$

    Si $f(u_1, u_2) > f(u_0, u_2)$, d’après la question 1,

    f(u_0, u_1) = f(u_0, u_2)

    Mais alors on prend le cycle $(u_0 ⋯ u_k)$ de taille $k-1$.

    Par HR, il existe deux arcs de même poids, si aucun des deux arcs n’est $(u_0, u_1)$ on a deux arcs de même poids dans $(u_0 ⋯ u_k)$

    et sinon, on a un arc de $(u_0 ⋯ u_k)$ de poids égal à $(u_0, u_2)$ qui a le même poids que $(u_0, u_1)$.

Soit $X$ un ensemble inclus dans $V×V$ tq pour tout $e, e’∈X$

f(e) ≠ f(e')

Soit $G’ = (V, X)$. Dans ce graphe, il n’y a pas de cycle.

On a donc

\vert X \vert ≤ \vert V \vert - 1 = n-1

($G’$ est un ensemble d’arbres)

3.

Par l’absurde, sinon, on aurait par la question 1 : $f(u,v) = f(u,w)$ ou $f(v,w)$.

Contradiction.

4.

Par récurrence.

5.

$K = (V, V×V\backslash \lbrace (u, u) \mid u ∈ V \rbrace)$ avec $f$ la fonction de poids.

Soit $T$ un arbre couvrant de $K$.

Montrons que si $M$ est une $u,v$-coupe optimale dans $G$, et $M’$ est une $u,v$-coupe optimale dans $T$, alors

w(M) = w(M')

L’arête $e’$ de poids minimal dans le chemin $u-v$ vérifie

w'(e') = w(M')

Si $w’(e’) < f(u, v)$, alors on peut construire $T’$ couvrant de poids strictement plus grand que $T$ (en supprimant $e’$ et en reliant $u$ et $v$ par l’arête étiquetée par $f(u,w)$)

Donc

f(u, v) ≤ w(e')

Mais on a aussi

f(u,v) ≥ \min \lbrace f(u, w_1), f(w_1, w_2), ⋯ , f(w_r, v) \rbrace = w(e')

le long du chemin $u-v$.

Donc

f(u, v) = w(e')

6.

Montrons que si $(X, Y)$ est une coupe optimale dans $G$ :

  • soit $(X∩V_1, Y ∪ V_2)$ est une coupe optimale dans $G$

  • soit $(X∪V_2, Y ∩ V_1)$ est une coupe optimale dans $G$

Dans la suite, si $C_1 = (X_1, Y_1)$ et $C_2 = (X_2, Y_2)$, on notera $w(C_1)$ par $w(X_1)$ ou $w(Y_1)$ et $w(C_2)$ par $w(X_2)$ ou $w(Y_2)$

Remarquons que

w(X_1)+w(X_2) ≥ w(X_1∪ X_2) + w(X_1 ∩ X_2)

(faire un dessin)

Soit $X, Y$ une coupe optimale pour $x-y$.

Si $t∈Y$, mq $(X∩V_1, Y ∪ V_2)$ est une $x-y$ coupe.

w(X) + w(V_1)≥ w(X∩V_1) + w(X∪V_1)

mais $(X∪V_1, Y ∩ V_2)$ est une $s,t$ coupe.

w(X∪V_1)≥w(V_1) \\ ⟹ w(X∩V_1)≤ w(X)

Mais $(X ∩ V_1, Y ∪ V_2)$ est une $x, y$ coupe donc

w(X∩V_1)≥ w(X)\\ ⟹ w(X ∩ V_1) = w(X)

Si $t∉Y$, on peut montrer que

(X∪ V_2, Y ∩ V_1)

est une $x,y$ coupe optimale.

Leave a comment