Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Algorithmes de couverture et d’augmentation de

graphes sous contraintes de distance

Bertrand Estellon
sous la direction de Victor Chepoi et Yann Vaxès

Université de la Méditerranée
Laboratoire d’Informatique Fondamentale de Marseille
Équipe Combinatoire et Recherche Opérationnelle
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problématique générale

Critères de qualité d’un réseau :

Performance (Délais de transmission)
Fiabilité (Résistance aux pannes)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problématique générale

Critères de qualité d’un réseau :

Performance (Délais de transmission)
Fiabilité (Résistance aux pannes)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problématique générale

Critères de qualité d’un réseau :

Performance (Délais de transmission)
Fiabilité (Résistance aux pannes)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problématique générale

Critères de qualité d’un réseau :

Performance (Délais de transmission)
Fiabilité (Résistance aux pannes)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problématique générale

Problèmes d’augmentation.

Ajouter un nombre minimum de liaisons à un réseau existant afin de

satisfaire certains critères de qualité.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problème d’augmentation sous contraintes de diamètre

Distance. Diamètre.

u
dG (u, v ) = 3

dG (u, v ) = nombre minimum diam(G ) = distance maximale qui

d’arêtes d’un chemin entre u et v . sépare deux sommets de G .

Problème ADC (Augmentation under Diameter Constraints)

Étant donné un graphe G = (V , E ) et un entier D,
trouver un ensemble d’arêtes E ′ ⊆ V 2 de cardinalité minimale tel que le
graphe augmenté G ′ = (V , E ∪ E ′ ) ait un diamètre au plus D.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problème d’augmentation sous contraintes de diamètre

Distance. Diamètre.

u
u
dG (u, v ) = 3 diam(G ) = 5

v v

dG (u, v ) = nombre minimum diam(G ) = distance maximale qui

d’arêtes d’un chemin entre u et v . sépare deux sommets de G .

Problème ADC (Augmentation under Diameter Constraints)

Étant donné un graphe G = (V , E ) et un entier D,
trouver un ensemble d’arêtes E ′ ⊆ V 2 de cardinalité minimale tel que le
graphe augmenté G ′ = (V , E ∪ E ′ ) ait un diamètre au plus D.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problème d’augmentation sous contraintes de diamètre

Distance. Diamètre.

u
u
dG (u, v ) = 3 diam(G ) = 5

v v

dG (u, v ) = nombre minimum diam(G ) = distance maximale qui

d’arêtes d’un chemin entre u et v . sépare deux sommets de G .

Problème ADC (Augmentation under Diameter Constraints)

Étant donné un graphe G = (V , E ) et un entier D,
trouver un ensemble d’arêtes E ′ ⊆ V 2 de cardinalité minimale tel que le
graphe augmenté G ′ = (V , E ∪ E ′ ) ait un diamètre au plus D.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problème d’augmentation sous contraintes de diamètre

Un exemple.

G
D =2
E′

1 2 3 4 5 6 7 8 9 10

OPT = 6
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problème d’augmentation sous contraintes de diamètre

Un exemple.

G
D =2
E′

1 2 3 4 5 6 7 8 9 10

OPT = 6
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problème d’augmentation sous contraintes de diamètre

Un exemple.

G
D =2
E′

1 2 3 4 5 6 7 8 9 10

a
3

2
4 7
OPT = 6 9 8

1 10

5 6
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Autres problèmes étudiés

Prise en compte du critère de résistance aux pannes.

Problème A2VP (Augmentation with 2 Vertex-disjoint Paths)
Ajouter un nombre minimum d’arêtes au graphe G de sorte qu’il existe
deux chemins sommets-disjoints de longueur au plus D entre chaque
paire de sommets.

Problème ADCE (Augm. with Diameter Constraints minus one Edge)

Ajouter un nombre minimum d’arêtes au graphe G de sorte que le graphe
augmenté conserve un diamètre ≤ D lorsqu’on lui supprime une arête.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Autres problèmes étudiés

Prise en compte du critère de résistance aux pannes.

Problème A2VP (Augmentation with 2 Vertex-disjoint Paths)
Ajouter un nombre minimum d’arêtes au graphe G de sorte qu’il existe
deux chemins sommets-disjoints de longueur au plus D entre chaque
paire de sommets.

≤D

≤D

Problème ADCE (Augm. with Diameter Constraints minus one Edge)

Ajouter un nombre minimum d’arêtes au graphe G de sorte que le graphe
augmenté conserve un diamètre ≤ D lorsqu’on lui supprime une arête.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Autres problèmes étudiés

Prise en compte du critère de résistance aux pannes.

Problème A2VP (Augmentation with 2 Vertex-disjoint Paths)
Ajouter un nombre minimum d’arêtes au graphe G de sorte qu’il existe
deux chemins sommets-disjoints de longueur au plus D entre chaque
paire de sommets.

≤D

≤D

Problème ADCE (Augm. with Diameter Constraints minus one Edge)

Ajouter un nombre minimum d’arêtes au graphe G de sorte que le graphe
augmenté conserve un diamètre ≤ D lorsqu’on lui supprime une arête.

≤D
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Objectifs

Objectifs :
Obtenir des algorithmes d’approximation ou des algorithmes à
performance garantie pour les problèmes d’augmentation lorsque le
graphe initial appartient à une classe de graphes donnée.

Un algorithme d’approximation avec un facteur α est un algorithme :

qui s’exécute en temps polynomial,
qui retourne des solutions dont le coût est ≤ α · OPT + C .

Classes de graphes étudiées :

Arbres
Graphes de largeur arborescente bornée
Graphes planaires et planaires extérieurs
Graphes δ-hyperboliques
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Objectifs

Objectifs :
Obtenir des algorithmes d’approximation ou des algorithmes à
performance garantie pour les problèmes d’augmentation lorsque le
graphe initial appartient à une classe de graphes donnée.

Un algorithme d’approximation avec un facteur α est un algorithme :

qui s’exécute en temps polynomial,
qui retourne des solutions dont le coût est ≤ α · OPT + C .

Classes de graphes étudiées :

Arbres
Graphes de largeur arborescente bornée
Graphes planaires et planaires extérieurs
Graphes δ-hyperboliques
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Objectifs

Objectifs :
Obtenir des algorithmes d’approximation ou des algorithmes à
performance garantie pour les problèmes d’augmentation lorsque le
graphe initial appartient à une classe de graphes donnée.

Un algorithme d’approximation avec un facteur α est un algorithme :

qui s’exécute en temps polynomial,
qui retourne des solutions dont le coût est ≤ α · OPT + C .

Classes de graphes étudiées :

Arbres
Graphes de largeur arborescente bornée
Graphes planaires et planaires extérieurs
Graphes δ-hyperboliques
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de couverture par des boules

La boule BG (c, R) :

Une boule de rayon R centrée sur c

Problème de la R-couverture minimale

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, couvrir les sommets de S en utilisant un nombre minimum
γG (S, R) de boules de rayon R (centrées sur des sommets de G ).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de couverture par des boules

La boule BG (c, R) :

Une boule de rayon R centrée sur c

Problème de la R-couverture minimale

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, couvrir les sommets de S en utilisant un nombre minimum
γG (S, R) de boules de rayon R (centrées sur des sommets de G ).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de couverture par des boules

La boule BG (c, R) : Une 2-couverture :

1
0
00
11
00
11
00 00
11 11
c
11
00 00
1111
00
00
1 10
1
00
11 00 00
11 11
R
00 0
11 110
0
1
1
0 1
0
0
1
0 1
1 001
0
1
Une boule de rayon R centrée sur c

Problème de la R-couverture minimale

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, couvrir les sommets de S en utilisant un nombre minimum
γG (S, R) de boules de rayon R (centrées sur des sommets de G ).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de couverture par des boules

La boule BG (c, R) : Une 2-couverture :

1
0
00
11
00
11
00 00
11 11
c
11
00 00
1111
00
00
1 10
1
00
11 00 00
11 11
R
00 0
11 110
0
1
1
0 1
0
0
1
0 1
1 001
0
1
Une boule de rayon R centrée sur c

Problème de la R-couverture minimale

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, couvrir les sommets de S en utilisant un nombre minimum
γG (S, R) de boules de rayon R (centrées sur des sommets de G ).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de couverture par des boules

La boule BG (c, R) : Une 2-couverture :

1
0
00
11
00
11
00 00
11 11
c
11
00 00
1111
00
00
1 10
1
00
11 00 00
11 11
R
00 0
11 110
0
1
1
0 1
0
0
1
0 1
1 001
0
1
Une boule de rayon R centrée sur c

Problème de la R-couverture minimale

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, couvrir les sommets de S en utilisant un nombre minimum
γG (S, R) de boules de rayon R (centrées sur des sommets de G ).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Diamètre pair (D = 2R) :

Rayon R

Rayon R − 1

Diamètre impair (D = 2R + 1) :

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Diamètre pair (D = 2R) :

Rayon R

Rayon R − 1

E′

Diamètre impair (D = 2R + 1) :

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Diamètre pair (D = 2R) :

Rayon R

Rayon R − 1

E′

Diamètre impair (D = 2R + 1) :

Rayon R

Rayon R − 1

E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Admissibilité des solutions lorsque D = 2R est pair.

Longueur du chemin ≤ (R − 1) + 1 + 1 + (R − 1) = 2R = D

Contraintes supplémentaires :
Les sommets non-couverts par les boules de rayon R − 1 doivent être
deux à deux à distance au plus 2R dans le graphe initial.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Admissibilité des solutions lorsque D = 2R est pair.

Longueur du chemin ≤ (R − 1) + 1 + 1 + (R − 1) = 2R = D

Contraintes supplémentaires :
Les sommets non-couverts par les boules de rayon R − 1 doivent être
deux à deux à distance au plus 2R dans le graphe initial.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Admissibilité des solutions lorsque D = 2R est pair.

Longueur du chemin ≤ (R − 1) + 1 + R = 2R = D

Contraintes supplémentaires :
Les sommets non-couverts par les boules de rayon R − 1 doivent être
deux à deux à distance au plus 2R dans le graphe initial.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Admissibilité des solutions lorsque D = 2R est pair.

Longueur du chemin ≤ (R − 1) + (R − 1) ≤ 2R = D

Contraintes supplémentaires :
Les sommets non-couverts par les boules de rayon R − 1 doivent être
deux à deux à distance au plus 2R dans le graphe initial.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Admissibilité des solutions lorsque D = 2R est pair.

Longueur du chemin ≤ 2R = D

Contraintes supplémentaires :
Les sommets non-couverts par les boules de rayon R − 1 doivent être
deux à deux à distance au plus 2R dans le graphe initial.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Augmentations considérés pour le problème ADC

Admissibilité des solutions lorsque D = 2R est pair.

Longueur du chemin ≤ 2R = D

Contraintes supplémentaires :
Les sommets non-couverts par les boules de rayon R − 1 doivent être
deux à deux à distance au plus 2R dans le graphe initial.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Algorithme générique lorsque D = 2R est pair.

Problème PCD (Partial Covering under Diameter constraints)
Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que le sous-ensemble
des sommets non couverts soit de diamètre ≤ 2R.

On a un algorithme d’approximation avec un facteur α pour



résoudre le problème PCD.


Si :

 On peut couvrir n’importe quel sous-ensemble de sommets
de diamètre ≤ 2R avec β boules de rayon R.


Alors on obtient un algorithme avec un facteur 2αβ pour ADC.

Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Algorithme générique lorsque D = 2R est pair.

Problème PCD (Partial Covering under Diameter constraints)
Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que le sous-ensemble
des sommets non couverts soit de diamètre ≤ 2R.

On a un algorithme d’approximation avec un facteur α pour



résoudre le problème PCD.


Si :

 On peut couvrir n’importe quel sous-ensemble de sommets
de diamètre ≤ 2R avec β boules de rayon R.


Alors on obtient un algorithme avec un facteur 2αβ pour ADC.

Diamètre ≤ 2R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Algorithme générique lorsque D = 2R est pair.

Problème PCD (Partial Covering under Diameter constraints)
Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que le sous-ensemble
des sommets non couverts soit de diamètre ≤ 2R.

On a un algorithme d’approximation avec un facteur α pour



résoudre le problème PCD.


Si :

 On peut couvrir n’importe quel sous-ensemble de sommets
de diamètre ≤ 2R avec β boules de rayon R.


Alors on obtient un algorithme avec un facteur 2αβ pour ADC.

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Algorithme générique lorsque D = 2R est pair.

Problème PCD (Partial Covering under Diameter constraints)
Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que le sous-ensemble
des sommets non couverts soit de diamètre ≤ 2R.

On a un algorithme d’approximation avec un facteur α pour



résoudre le problème PCD.


Si :

 On peut couvrir n’importe quel sous-ensemble de sommets
de diamètre ≤ 2R avec β boules de rayon R.


Alors on obtient un algorithme avec un facteur 2αβ pour ADC.

Rayon R

Rayon R − 1

E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Analyse du facteur d’approximation lorsque D = 2R est pair.

Soit E ∗ une augmentation optimale pour le problème ADC

OPTPCD ≤ 2|E ∗ |
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Analyse du facteur d’approximation lorsque D = 2R est pair.

Soit E ∗ une augmentation optimale pour le problème ADC

E∗

OPTPCD ≤ 2|E ∗ |
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Analyse du facteur d’approximation lorsque D = 2R est pair.

Soit E ∗ une augmentation optimale pour le problème ADC

E∗

Rayon R − 1

OPTPCD ≤ 2|E ∗ |
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Analyse du facteur d’approximation lorsque D = 2R est pair.

Soit E ∗ une augmentation optimale pour le problème ADC

E∗

Rayon R − 1

Diamètre ≤ 2R

OPTPCD ≤ 2|E ∗ |
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Algorithme générique lorsque D = 2R + 1 est impair.

Problème de la Couverture Mixte
Étant donné un graphe G , deux entiers positifs R1 et R2 et une
fonction f , trouver une couverture de G avec n1 boules de rayon R1
et n2 boules de rayon R2 de façon à minimiser f (n1 , n2 ).

n2 (n2 −1)
Avec R1 := R − 1, R2 := R et f (n1 , n2 ) := 2 + n1

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Élaboration des solutions

Algorithme générique lorsque D = 2R + 1 est impair.

Problème de la Couverture Mixte
Étant donné un graphe G , deux entiers positifs R1 et R2 et une
fonction f , trouver une couverture de G avec n1 boules de rayon R1
et n2 boules de rayon R2 de façon à minimiser f (n1 , n2 ).

n2 (n2 −1)
Avec R1 := R − 1, R2 := R et f (n1 , n2 ) := 2 + n1

Rayon R

Rayon R − 1

E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de packing par des boules

Un sous-ensemble P ⊆ S est un
R-packing de S si dG (u, v ) > 2R
pour tous u, v ∈ P

Problème du R-packing maximum (dual du problème de la R-couverture)

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, trouver un R-packing de S de cardinalité maximale νG (S, R).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de packing par des boules

Un sous-ensemble P ⊆ S est un
R-packing de S si dG (u, v ) > 2R
pour tous u, v ∈ P

Problème du R-packing maximum (dual du problème de la R-couverture)

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, trouver un R-packing de S de cardinalité maximale νG (S, R).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de packing par des boules

> 2R

Un sous-ensemble P ⊆ S est un
R-packing de S si dG (u, v ) > 2R
pour tous u, v ∈ P

Problème du R-packing maximum (dual du problème de la R-couverture)

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, trouver un R-packing de S de cardinalité maximale νG (S, R).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de packing par des boules

> 2R

Un sous-ensemble P ⊆ S est un
R-packing de S si dG (u, v ) > 2R
pour tous u, v ∈ P

Problème du R-packing maximum (dual du problème de la R-couverture)

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, trouver un R-packing de S de cardinalité maximale νG (S, R).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de packing par des boules

Un 2-packing :

1
0
00
11
00
11
00 00
11 11
> 2R
00
1111
00
00
1 10
1
11
00
00
11 00 00
11
00 0
11 11
101
1
0 1
0 1
0
0
1
0 0
1
Un sous-ensemble P ⊆ S est un 1
R-packing de S si dG (u, v ) > 2R ⇒ solutions optimales
pour tous u, v ∈ P

Problème du R-packing maximum (dual du problème de la R-couverture)

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, trouver un R-packing de S de cardinalité maximale νG (S, R).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Problèmes de packing par des boules

Un 2-packing :

1
0
00
11
00
11
00 00
11 11
> 2R
00
1111
00
00
1 10
1
11
00
00
11 00 00
11
00 0
11 11
101
1
0 1
0 1
0
0
1
0 0
1
Un sous-ensemble P ⊆ S est un 1
R-packing de S si dG (u, v ) > 2R ⇒ solutions optimales
pour tous u, v ∈ P

Problème du R-packing maximum (dual du problème de la R-couverture)

Étant donné un graphe G = (V , E ), un sous-ensemble S ⊆ V et un
rayon R, trouver un R-packing de S de cardinalité maximale νG (S, R).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

État de l’art

Sans contrainte sur la topologie du graphe initial :

Problème de la R-couverture minimale :

Aussi difficile à approximer que SET COVER
NP-difficile à approximer avec un facteur sous-logarithmique
N. Alon, D. Moshkovitz, M. Safra (2006)

Problème ADC :
NP-difficile à approximer avec un facteur sous-logarithmique
A.A. Schoone, H.L. Bodlaender, J. van Leeuwen (1987)
Approximable avec facteur O(log2 n)
Y. Dodis, S. Khanna (1999)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

État de l’art

Sans contrainte sur la topologie du graphe initial :

Problème de la R-couverture minimale :

Aussi difficile à approximer que SET COVER
NP-difficile à approximer avec un facteur sous-logarithmique
N. Alon, D. Moshkovitz, M. Safra (2006)

Problème ADC :
NP-difficile à approximer avec un facteur sous-logarithmique
A.A. Schoone, H.L. Bodlaender, J. van Leeuwen (1987)
Approximable avec facteur O(log2 n)
Y. Dodis, S. Khanna (1999)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

État de l’art

Si le graphe initial est un arbre :

Problème de la R-couverture minimale :

Algorithme exact et linéaire
γG (S, R) = νG (S, R)
G. J. Chang (1988)

Problème ADC :
Approximable avec un facteur 2 lorsque D est pair
V. Chepoi, Y. Vaxès (2002)
Approximable avec un facteur 8 lorsque D est impair
T. Ishii, S. Yamamoto, H. Nagamochi (2003)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

État de l’art

Si le graphe initial est un arbre :

Problème de la R-couverture minimale :

Algorithme exact et linéaire
γG (S, R) = νG (S, R)
G. J. Chang (1988)

Problème ADC :
Approximable avec un facteur 2 lorsque D est pair
V. Chepoi, Y. Vaxès (2002)
Approximable avec un facteur 8 lorsque D est impair
T. Ishii, S. Yamamoto, H. Nagamochi (2003)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Résultats de la thèse

Partie I : Arbres et forêts.

Si le graphe initial est un arbre :

Couverture mixte : Algorithme polynomial exact
Problème ADC : Facteur 2 + 1/δ lorsque D est impair

Si le graphe initial est une forêt :


NP-difficile à résoudre optimalement
Problème A2VP :
Approximable avec un facteur 6

NP-difficile à résoudre optimalement
Problème ADCE :
Approximable avec un facteur 4
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Résultats de la thèse

Partie I : Arbres et forêts.

Si le graphe initial est un arbre :

Couverture mixte : Algorithme polynomial exact
Problème ADC : Facteur 2 + 1/δ lorsque D est impair

Si le graphe initial est une forêt :


NP-difficile à résoudre optimalement
Problème A2VP :
Approximable avec un facteur 6

NP-difficile à résoudre optimalement
Problème ADCE :
Approximable avec un facteur 4
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Résultats de la thèse

Partie II : Graphes généraux.

Graphes de largeur arborescente bornée :

R-couverture : γG (S, R) ≤ (tw (G ) + 1) · νG (S, R)
Problème PCD : Facteur 2(tw(G)+1)
Couverture mixte : Algorithme polynomial exact
Facteur 4(tw (G ) + 1)2 lorsque D est pair

Problème ADC :
Facteur 2 + (tw (G ) + 1)2 + 1/δ lorsque D est impair

Graphes δ-hyperboliques :
R-couverture : γG (S, R + δ) ≤ νG (S, R)
Algorithme polynomial qui construit une solution
(
Problème ADC : pour D := 2R +2δ avec un nombre d’arêtes inférieur
à 2 fois celui d’une solution optimale pour D := 2R.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Résultats de la thèse

Partie II : Graphes généraux.

Graphes de largeur arborescente bornée :

R-couverture : γG (S, R) ≤ (tw (G ) + 1) · νG (S, R)
Problème PCD : Facteur 2(tw(G)+1)
Couverture mixte : Algorithme polynomial exact
Facteur 4(tw (G ) + 1)2 lorsque D est pair

Problème ADC :
Facteur 2 + (tw (G ) + 1)2 + 1/δ lorsque D est impair

Graphes δ-hyperboliques :
R-couverture : γG (S, R + δ) ≤ νG (S, R)
Algorithme polynomial qui construit une solution
(
Problème ADC : pour D := 2R +2δ avec un nombre d’arêtes inférieur
à 2 fois celui d’une solution optimale pour D := 2R.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Résultats de la thèse

Partie II : Graphes généraux.

Graphes planaires :
R-couverture :
Tout graphe planaire de diamètre ≤ 2R peut être couvert par un
nombre constant de boules de rayon R (réponse à une question de
Gavoille, Peleg, Raspaud et Sopéna)
Plus généralement, νG (S, R) ≤ k implique γG (S, R) ≤ c(k)

Problème ADC : Facteur O(log |V |) lorsque D est pair

Graphes planaires extérieurs :

R-couverture : γG (S, R) ≤ 2 · νG (S, R)
Problème PCD : Algorithme polynomial avec une erreur additive de 7
Couverture mixte : Algorithme polynomial exact

Facteur 2 lorsque D est pair
Problème ADC :
Facteur 6 + 1/δ lorsque D est impair
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Résultats de la thèse

Partie II : Graphes généraux.

Graphes planaires :
R-couverture :
Tout graphe planaire de diamètre ≤ 2R peut être couvert par un
nombre constant de boules de rayon R (réponse à une question de
Gavoille, Peleg, Raspaud et Sopéna)
Plus généralement, νG (S, R) ≤ k implique γG (S, R) ≤ c(k)

Problème ADC : Facteur O(log |V |) lorsque D est pair

Graphes planaires extérieurs :

R-couverture : γG (S, R) ≤ 2 · νG (S, R)
Problème PCD : Algorithme polynomial avec une erreur additive de 7
Couverture mixte : Algorithme polynomial exact

Facteur 2 lorsque D est pair
Problème ADC :
Facteur 6 + 1/δ lorsque D est impair
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Définitions

Définition de la largeur arborescente d’un graphe.

N. Robertson et P.D. Seymour (1986)
a b f

c g

d e h

Une décomposition arborescente de G = (V , E ) est valide si :

1 Chaque sommet de G est dans un nœud de l’arbre de décomposition.
2 Pour chaque arête e ∈ E , un nœud de l’arbre de décomposition
contient les deux extrémités de e.
3 Pour chaque sommet x ∈ V , les nœuds qui contiennent x induisent
un sous-arbre (connexe) de l’arbre de décomposition.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Définitions

Définition de la largeur arborescente d’un graphe.

N. Robertson et P.D. Seymour (1986)
a b f

c g

d e h

Une décomposition arborescente de G = (V , E ) est valide si :

1 Chaque sommet de G est dans un nœud de l’arbre de décomposition.
2 Pour chaque arête e ∈ E , un nœud de l’arbre de décomposition
contient les deux extrémités de e.
3 Pour chaque sommet x ∈ V , les nœuds qui contiennent x induisent
un sous-arbre (connexe) de l’arbre de décomposition.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Définitions

Définition de la largeur arborescente d’un graphe.

N. Robertson et P.D. Seymour (1986)
a b f
a bf
b g
c

c g cb bg
e e

ce g
e
d h
d e h

Une décomposition arborescente de G = (V , E ) est valide si :

1 Chaque sommet de G est dans un nœud de l’arbre de décomposition.
2 Pour chaque arête e ∈ E , un nœud de l’arbre de décomposition
contient les deux extrémités de e.
3 Pour chaque sommet x ∈ V , les nœuds qui contiennent x induisent
un sous-arbre (connexe) de l’arbre de décomposition.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Définitions

Définition de la largeur arborescente d’un graphe.

N. Robertson et P.D. Seymour (1986)
a b f
a bf
b g
c

c g cb bg
e e

ce g
e
d h
d e h

Une décomposition arborescente de G = (V , E ) est valide si :

1 Chaque sommet de G est dans un nœud de l’arbre de décomposition.
2 Pour chaque arête e ∈ E , un nœud de l’arbre de décomposition
contient les deux extrémités de e.
3 Pour chaque sommet x ∈ V , les nœuds qui contiennent x induisent
un sous-arbre (connexe) de l’arbre de décomposition.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Définitions

Définition de la largeur arborescente d’un graphe.

N. Robertson et P.D. Seymour (1986)
a b f
a bf
b g
c

c g cb bg
e e

ce g
e
d h
d e h

Une décomposition arborescente de G = (V , E ) est valide si :

1 Chaque sommet de G est dans un nœud de l’arbre de décomposition.
2 Pour chaque arête e ∈ E , un nœud de l’arbre de décomposition
contient les deux extrémités de e.
3 Pour chaque sommet x ∈ V , les nœuds qui contiennent x induisent
un sous-arbre (connexe) de l’arbre de décomposition.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Définitions

Définition de la largeur arborescente d’un graphe.

N. Robertson et P.D. Seymour (1986)
a b f
a bf
b g
c

c g cb bg
e e

ce g
e
d h
d e h

La largeur d’une décomposition arborescente est égale au plus grand

nombre de sommets présents dans un nœud de l’arbre moins un.

La largeur arborescente tw (G ) d’un graphe G est égale à la largeur

minimale que l’on peut obtenir en considérant toutes les décompositions
arborescentes valides de G .
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Résultats connus

Il existe un algorithme linéaire pour trouver une décomposition

arborescente optimale d’un graphe de largeur arborescente bornée.
H.L. Bodlaender (1996)

Les sommets d’un graphe G de diamètre ≤ 2R peuvent être couverts

par tw (G ) + 1 boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Le problème de la R-couverture minimale se résout en temps polynomial

dans un graphe de largeur arborescente bornée.
E.D. Demaine, F.V. Fomin, M. Hajiaghayi et D.M. Thilikos (2003)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Résultats connus

Il existe un algorithme linéaire pour trouver une décomposition

arborescente optimale d’un graphe de largeur arborescente bornée.
H.L. Bodlaender (1996)

Les sommets d’un graphe G de diamètre ≤ 2R peuvent être couverts

par tw (G ) + 1 boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Le problème de la R-couverture minimale se résout en temps polynomial

dans un graphe de largeur arborescente bornée.
E.D. Demaine, F.V. Fomin, M. Hajiaghayi et D.M. Thilikos (2003)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Résultats connus

Il existe un algorithme linéaire pour trouver une décomposition

arborescente optimale d’un graphe de largeur arborescente bornée.
H.L. Bodlaender (1996)

Les sommets d’un graphe G de diamètre ≤ 2R peuvent être couverts

par tw (G ) + 1 boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Le problème de la R-couverture minimale se résout en temps polynomial

dans un graphe de largeur arborescente bornée.
E.D. Demaine, F.V. Fomin, M. Hajiaghayi et D.M. Thilikos (2003)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Problème PCD (Partial Covering under Diameter constraints)

Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que l’ensemble des
sommets non couverts soit de diamètre ≤ 2R.

Dans un graphe de largeur arborescente bornée, le problème PCD peut

être approximé avec un facteur 2(tw (G ) + 1).

Principe de l’algorithme :
1 On formule le problème PCD sous la forme d’un PLNE
2 On calcule une solution optimale fractionnaire
3 On détermine l’ensemble S des sommets à couvrir
4 On couvre les sommets de S en utilisant le résultat suivant :

Dans un graphe G = (V , E ) de largeur arborescente bornée, on peut

construire en temps polynomial une R-couverture B et un R-packing P
de S tels que
|B| ≤ (tw (G ) + 1)|P|.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Problème PCD (Partial Covering under Diameter constraints)

Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que l’ensemble des
sommets non couverts soit de diamètre ≤ 2R.

Dans un graphe de largeur arborescente bornée, le problème PCD peut

être approximé avec un facteur 2(tw (G ) + 1).

Principe de l’algorithme :
1 On formule le problème PCD sous la forme d’un PLNE
2 On calcule une solution optimale fractionnaire
3 On détermine l’ensemble S des sommets à couvrir
4 On couvre les sommets de S en utilisant le résultat suivant :

Dans un graphe G = (V , E ) de largeur arborescente bornée, on peut

construire en temps polynomial une R-couverture B et un R-packing P
de S tels que
|B| ≤ (tw (G ) + 1)|P|.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Problème PCD (Partial Covering under Diameter constraints)

Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que l’ensemble des
sommets non couverts soit de diamètre ≤ 2R.

Dans un graphe de largeur arborescente bornée, le problème PCD peut

être approximé avec un facteur 2(tw (G ) + 1).

Principe de l’algorithme :
1 On formule le problème PCD sous la forme d’un PLNE
2 On calcule une solution optimale fractionnaire
3 On détermine l’ensemble S des sommets à couvrir
4 On couvre les sommets de S en utilisant le résultat suivant :

Dans un graphe G = (V , E ) de largeur arborescente bornée, on peut

construire en temps polynomial une R-couverture B et un R-packing P
de S tels que
|B| ≤ (tw (G ) + 1)|P|.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Problème PCD (Partial Covering under Diameter constraints)

Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que l’ensemble des
sommets non couverts soit de diamètre ≤ 2R.

Dans un graphe de largeur arborescente bornée, le problème PCD peut

être approximé avec un facteur 2(tw (G ) + 1).

Principe de l’algorithme :
1 On formule le problème PCD sous la forme d’un PLNE
2 On calcule une solution optimale fractionnaire
3 On détermine l’ensemble S des sommets à couvrir
4 On couvre les sommets de S en utilisant le résultat suivant :

Dans un graphe G = (V , E ) de largeur arborescente bornée, on peut

construire en temps polynomial une R-couverture B et un R-packing P
de S tels que
|B| ≤ (tw (G ) + 1)|P|.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Problème PCD (Partial Covering under Diameter constraints)

Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que l’ensemble des
sommets non couverts soit de diamètre ≤ 2R.

Dans un graphe de largeur arborescente bornée, le problème PCD peut

être approximé avec un facteur 2(tw (G ) + 1).

Principe de l’algorithme :
1 On formule le problème PCD sous la forme d’un PLNE
2 On calcule une solution optimale fractionnaire
3 On détermine l’ensemble S des sommets à couvrir
4 On couvre les sommets de S en utilisant le résultat suivant :

Dans un graphe G = (V , E ) de largeur arborescente bornée, on peut

construire en temps polynomial une R-couverture B et un R-packing P
de S tels que
|B| ≤ (tw (G ) + 1)|P|.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Problème PCD (Partial Covering under Diameter constraints)

Étant donné un graphe G et un rayon R, couvrir partiellement G avec un
nombre minimum de boules de rayon R − 1 de sorte que l’ensemble des
sommets non couverts soit de diamètre ≤ 2R.

Dans un graphe de largeur arborescente bornée, le problème PCD peut

être approximé avec un facteur 2(tw (G ) + 1).

Principe de l’algorithme :
1 On formule le problème PCD sous la forme d’un PLNE
2 On calcule une solution optimale fractionnaire
3 On détermine l’ensemble S des sommets à couvrir
4 On couvre les sommets de S en utilisant le résultat suivant :

Dans un graphe G = (V , E ) de largeur arborescente bornée, on peut

construire en temps polynomial une R-couverture B et un R-packing P
de S tels que
|B| ≤ (tw (G ) + 1)|P|.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Facteur 4(tw (G ) + 1)2 pour le problème ADC

1 calculer une couverture admissible B du problème PCD avec
l’algorithme facteur 2(tw (G ) + 1).
2 ajouter tw (G ) + 1 boules de rayon R à la couverture B afin de
couvrir tous les sommets de G .
3 construire une augmentation admissible E ′ à partir de B.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Facteur 4(tw (G ) + 1)2 pour le problème ADC

1 calculer une couverture admissible B du problème PCD avec
l’algorithme facteur 2(tw (G ) + 1).
2 ajouter tw (G ) + 1 boules de rayon R à la couverture B afin de
couvrir tous les sommets de G .
3 construire une augmentation admissible E ′ à partir de B.

Diamètre ≤ 2R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Facteur 4(tw (G ) + 1)2 pour le problème ADC

1 calculer une couverture admissible B du problème PCD avec
l’algorithme facteur 2(tw (G ) + 1).
2 ajouter tw (G ) + 1 boules de rayon R à la couverture B afin de
couvrir tous les sommets de G .
3 construire une augmentation admissible E ′ à partir de B.

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre pair (D = 2R)

Facteur 4(tw (G ) + 1)2 pour le problème ADC

1 calculer une couverture admissible B du problème PCD avec
l’algorithme facteur 2(tw (G ) + 1).
2 ajouter tw (G ) + 1 boules de rayon R à la couverture B afin de
couvrir tous les sommets de G .
3 construire une augmentation admissible E ′ à partir de B.

Rayon R

Rayon R − 1

E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre impair (D = 2R + 1)

Dans les graphes de largeur arborescente bornée :

Le problème de la couverture mixte est polynomial.
γG (S, R) ≤ (tw (G ) + 1)νG (S, R).

Facteur 2 + (tw (G ) + 1)2 + 1/δ pour le problème ADC

1 Construire une couverture mixte optimale B de G pour R1 := R,
R2 := R − 1 et f (n1 , n2 ) := n2 (n2 − 1)/2 + n1 .
2 Construire une augmentation admissible E ′ à partir de B.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre impair (D = 2R + 1)

Dans les graphes de largeur arborescente bornée :

Le problème de la couverture mixte est polynomial.
γG (S, R) ≤ (tw (G ) + 1)νG (S, R).

Facteur 2 + (tw (G ) + 1)2 + 1/δ pour le problème ADC

1 Construire une couverture mixte optimale B de G pour R1 := R,
R2 := R − 1 et f (n1 , n2 ) := n2 (n2 − 1)/2 + n1 .
2 Construire une augmentation admissible E ′ à partir de B.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre impair (D = 2R + 1)

Dans les graphes de largeur arborescente bornée :

Le problème de la couverture mixte est polynomial.
γG (S, R) ≤ (tw (G ) + 1)νG (S, R).

Facteur 2 + (tw (G ) + 1)2 + 1/δ pour le problème ADC

1 Construire une couverture mixte optimale B de G pour R1 := R,
R2 := R − 1 et f (n1 , n2 ) := n2 (n2 − 1)/2 + n1 .
2 Construire une augmentation admissible E ′ à partir de B.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre impair (D = 2R + 1)

Dans les graphes de largeur arborescente bornée :

Le problème de la couverture mixte est polynomial.
γG (S, R) ≤ (tw (G ) + 1)νG (S, R).

Facteur 2 + (tw (G ) + 1)2 + 1/δ pour le problème ADC

1 Construire une couverture mixte optimale B de G pour R1 := R,
R2 := R − 1 et f (n1 , n2 ) := n2 (n2 − 1)/2 + n1 .
2 Construire une augmentation admissible E ′ à partir de B.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre impair (D = 2R + 1)

Dans les graphes de largeur arborescente bornée :

Le problème de la couverture mixte est polynomial.
γG (S, R) ≤ (tw (G ) + 1)νG (S, R).

Facteur 2 + (tw (G ) + 1)2 + 1/δ pour le problème ADC

1 Construire une couverture mixte optimale B de G pour R1 := R,
R2 := R − 1 et f (n1 , n2 ) := n2 (n2 − 1)/2 + n1 .
2 Construire une augmentation admissible E ′ à partir de B.

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes de largeur arborescente bornée ⊲ Diamètre impair (D = 2R + 1)

Dans les graphes de largeur arborescente bornée :

Le problème de la couverture mixte est polynomial.
γG (S, R) ≤ (tw (G ) + 1)νG (S, R).

Facteur 2 + (tw (G ) + 1)2 + 1/δ pour le problème ADC

1 Construire une couverture mixte optimale B de G pour R1 := R,
R2 := R − 1 et f (n1 , n2 ) := n2 (n2 − 1)/2 + n1 .
2 Construire une augmentation admissible E ′ à partir de B.

Rayon R

Rayon R − 1

E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Conjecture de Gavoille, Peleg, Raspaud et Sopena. Il existe une

constante (universelle) c telle que tout graphe planaire de diamètre 2R
peut être couvert par c boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Théorème. Il existe une constante c telle que, dans tout graphe

planaire, tout sous-ensemble de sommets S de diamètre ≤ 2R peut être
couvert par c boules de rayon R.

Résultat utilisé :
La taille d’un transversal minimum d’une famille F est borné par un
entier qui ne dépend que de p et de q si les deux conditions suivantes
sont vérifiées :
la dimension VC duale de F est au plus q − 1,
la famille F vérifie la propriété (p, q) de Hadwiger-Debrunner.
J. Matoušek (2004)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Conjecture de Gavoille, Peleg, Raspaud et Sopena. Il existe une

constante (universelle) c telle que tout graphe planaire de diamètre 2R
peut être couvert par c boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Théorème. Il existe une constante c telle que, dans tout graphe

planaire, tout sous-ensemble de sommets S de diamètre ≤ 2R peut être
couvert par c boules de rayon R.

Résultat utilisé :
La taille d’un transversal minimum d’une famille F est borné par un
entier qui ne dépend que de p et de q si les deux conditions suivantes
sont vérifiées :
la dimension VC duale de F est au plus q − 1,
la famille F vérifie la propriété (p, q) de Hadwiger-Debrunner.
J. Matoušek (2004)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Conjecture de Gavoille, Peleg, Raspaud et Sopena. Il existe une

constante (universelle) c telle que tout graphe planaire de diamètre 2R
peut être couvert par c boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Théorème. Il existe une constante c telle que, dans tout graphe

planaire, tout sous-ensemble de sommets S de diamètre ≤ 2R peut être
couvert par c boules de rayon R.

Résultat utilisé :
La taille d’un transversal minimum d’une famille F est borné par un
entier qui ne dépend que de p et de q si les deux conditions suivantes
sont vérifiées :
la dimension VC duale de F est au plus q − 1,
la famille F vérifie la propriété (p, q) de Hadwiger-Debrunner.
J. Matoušek (2004)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Conjecture de Gavoille, Peleg, Raspaud et Sopena. Il existe une

constante (universelle) c telle que tout graphe planaire de diamètre 2R
peut être couvert par c boules de rayon R.
C. Gavoille, D. Peleg, A. Raspaud et E. Sopena (2001)

Théorème. Il existe une constante c telle que, dans tout graphe

planaire, tout sous-ensemble de sommets S de diamètre ≤ 2R peut être
couvert par c boules de rayon R.

Résultat utilisé avec B := {BG (s, R) : s ∈ S} :

La taille d’un transversal minimum d’une famille B est borné par un
entier qui ne dépend que de p et de q si les deux conditions suivantes
sont vérifiées :
la dimension VC duale de B est au plus 5 − 1 = 4,
la famille B vérifie la propriété (p, 5) de Hadwiger-Debrunner.
J. Matoušek (2004)
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Dimension de Vapnik-Chervonenkis (VC) :

Un ensemble X est pulvérisé par une famille F si {X ∩ F : F ∈ F } = 2X .

La dimension VC de F = max{|X | : X est pulvérisé par F }.

Dans un graphe planaire, une famille B de boules de rayon R a une

dimension VC au plus 4.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Dimension de Vapnik-Chervonenkis (VC) :

Un ensemble X est pulvérisé par une famille F si {X ∩ F : F ∈ F } = 2X .

La dimension VC de F = max{|X | : X est pulvérisé par F }.

Dans un graphe planaire, une famille B de boules de rayon R a une

dimension VC au plus 4.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Dimension de Vapnik-Chervonenkis (VC) :

Un ensemble X est pulvérisé par une famille F si {X ∩ F : F ∈ F } = 2X .

La dimension VC de F = max{|X | : X est pulvérisé par F }.

Dans un graphe planaire, une famille B de boules de rayon R a une

dimension VC au plus 4.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Dimension de Vapnik-Chervonenkis (VC) :

Un ensemble X est pulvérisé par une famille F si {X ∩ F : F ∈ F } = 2X .

La dimension VC de F = max{|X | : X est pulvérisé par F }.

Dans un graphe planaire, une famille B de boules de rayon R a une

dimension VC au plus 4.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Dimension de Vapnik-Chervonenkis (VC) :

Un ensemble X est pulvérisé par une famille F si {X ∩ F : F ∈ F } = 2X .

La dimension VC de F = max{|X | : X est pulvérisé par F }.

Dans un graphe planaire, une famille B de boules de rayon R a une

dimension VC au plus 4.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Propriété (p, q) de Hadwiger-Debrunner :

Une famille F vérifie la propriété (p, q) si, dans chaque sous-famille de

F composée de p ensembles, q ensembles partagent un élément.

Dans un graphe planaire, une famille B de boules de rayon R qui

s’intersectent deux à deux vérifie la propriété (p, 5) pour un p > 5.

Agarwal et al. (1997), Pach et al. (1996)

Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Propriété (p, q) de Hadwiger-Debrunner :

Une famille F vérifie la propriété (p, q) si, dans chaque sous-famille de

F composée de p ensembles, q ensembles partagent un élément.

Dans un graphe planaire, une famille B de boules de rayon R qui

s’intersectent deux à deux vérifie la propriété (p, 5) pour un p > 5.

Agarwal et al. (1997), Pach et al. (1996)

Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Propriété (p, q) de Hadwiger-Debrunner :

Une famille F vérifie la propriété (p, q) si, dans chaque sous-famille de

F composée de p ensembles, q ensembles partagent un élément.

Dans un graphe planaire, une famille B de boules de rayon R qui

s’intersectent deux à deux vérifie la propriété (p, 5) pour un p > 5.

Les centres de p boules

Agarwal et al. (1997), Pach et al. (1996)

Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Couverture d’un ensemble de sommets de diamètre ≤ 2R

Propriété (p, q) de Hadwiger-Debrunner :

Une famille F vérifie la propriété (p, q) si, dans chaque sous-famille de

F composée de p ensembles, q ensembles partagent un élément.

Dans un graphe planaire, une famille B de boules de rayon R qui

s’intersectent deux à deux vérifie la propriété (p, 5) pour un p > 5.

avec
p suffisamment
grand

Les centres de p boules 10 paires d’arêtes

qui se croisent deux à deux

Agarwal et al. (1997), Pach et al. (1996)

Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Facteur logarithme pour le problème ADC

Conséquence sur le problème ADC lorsque D = 2R est pair.



 un algorithme d’approximation avec un facteur



 O(log |V |) pour résoudre le problème PCD
 (réduction à SET COVER).
On a :


 une borne du nombre de boules de rayon R nécessaires


 pour couvrir un sous-ensemble de sommets de diamètre
≤ 2R.


Donc, on obtient un algorithme avec un facteur O(log |V |).

Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Facteur logarithme pour le problème ADC

Conséquence sur le problème ADC lorsque D = 2R est pair.



 un algorithme d’approximation avec un facteur



 O(log |V |) pour résoudre le problème PCD
 (réduction à SET COVER).
On a :


 une borne du nombre de boules de rayon R nécessaires


 pour couvrir un sous-ensemble de sommets de diamètre
≤ 2R.


Donc, on obtient un algorithme avec un facteur O(log |V |).

Diamètre ≤ 2R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Facteur logarithme pour le problème ADC

Conséquence sur le problème ADC lorsque D = 2R est pair.



 un algorithme d’approximation avec un facteur



 O(log |V |) pour résoudre le problème PCD
 (réduction à SET COVER).
On a :


 une borne du nombre de boules de rayon R nécessaires


 pour couvrir un sous-ensemble de sommets de diamètre
≤ 2R.


Donc, on obtient un algorithme avec un facteur O(log |V |).

Rayon R

Rayon R − 1
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes planaires ⊲ Facteur logarithme pour le problème ADC

Conséquence sur le problème ADC lorsque D = 2R est pair.



 un algorithme d’approximation avec un facteur



 O(log |V |) pour résoudre le problème PCD
 (réduction à SET COVER).
On a :


 une borne du nombre de boules de rayon R nécessaires


 pour couvrir un sous-ensemble de sommets de diamètre
≤ 2R.


Donc, on obtient un algorithme avec un facteur O(log |V |).

Rayon R

Rayon R − 1

E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

≤δ

≤δ ≤δ

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des espaces δ-hyperboliques. M. Gromov (1987)

≤δ

≤δ ≤δ

Un triangle est δ-fin si la distance entre les deux préimages de n’importe

quel point du tripode est inférieure ou égale à δ.

Un espace métrique géodésique est δ-hyperbolique si tous ses triangles

(obtenus à partir de trois géodésiques entre trois points) sont δ-fins.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Définitions

Définition des graphes δ-hyperboliques.

Tout graphe connexe G = (V , E ) peut être transformé en un espace
géodésique (X , d) en remplaçant chaque arête e = (u, v ) ∈ E par un
segment [u, v ] de longueur 1.

Le graphe G est δ-hyperbolique si l’espace métrique (X , d) obtenu à

partir de G est δ-hyperbolique.

Les arbres et les graphes blocs

sont 0-hyperboliques.

Les graphes triangulés

sont 2-hyperboliques.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Étant donné un graphe δ-hyperbolique G = (V , E ), un sous-ensemble

S ⊆ V et un rayon R > 0, on peut construire en temps polynomial une
(R + δ)-couverture B et un R-packing P de S de même cardinalité.

Sommets de S
(R + δ)-couverture
R-packing

Dans un graphe δ-hyperbolique, un sous-ensemble de sommets de

diamètre 2R peut être couvert par une boule de rayon R + δ.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Étant donné un graphe δ-hyperbolique G = (V , E ), un sous-ensemble

S ⊆ V et un rayon R > 0, on peut construire en temps polynomial une
(R + δ)-couverture B et un R-packing P de S de même cardinalité.

Sommets de S
(R + δ)-couverture
R-packing

Dans un graphe δ-hyperbolique, un sous-ensemble de sommets de

diamètre 2R peut être couvert par une boule de rayon R + δ.
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Dans un graphe δ-hyperbolique G = (V , E ), pour n’importe quel

sous-ensemble S ⊆ V , il existe une boule B de rayon 2R centrée sur un
sommet de S telle que les sommets de B ∩ S peuvent être couverts par
une boule de rayon R + δ.

2R

R +δ
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Construction du R-packing et de la (R + δ)-couverture de S.

Commencer avec un R-packing et une (R + δ)-couverture vide.

Tant que S 6= ∅
1 Trouver x et c de sorte que BG (x, 2R) ∩ S⊆ BG (c, R + δ).
2 Ajouter x au packing et BG (c, R + δ) à la couverture.
3 Retirer de S tous les sommets présents dans BG (c, R + δ).

Sommets de S
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Construction du R-packing et de la (R + δ)-couverture de S.

Commencer avec un R-packing et une (R + δ)-couverture vide.

Tant que S 6= ∅
1 Trouver x et c de sorte que BG (x, 2R) ∩ S⊆ BG (c, R + δ).
2 Ajouter x au packing et BG (c, R + δ) à la couverture.
3 Retirer de S tous les sommets présents dans BG (c, R + δ).

Sommets de S
Rayon 2R
Rayon R + δ
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Construction du R-packing et de la (R + δ)-couverture de S.

Commencer avec un R-packing et une (R + δ)-couverture vide.

Tant que S 6= ∅
1 Trouver x et c de sorte que BG (x, 2R) ∩ S⊆ BG (c, R + δ).
2 Ajouter x au packing et BG (c, R + δ) à la couverture.
3 Retirer de S tous les sommets présents dans BG (c, R + δ).

Sommets de S
Rayon 2R
Rayon R + δ
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Construction du R-packing et de la (R + δ)-couverture de S.

Commencer avec un R-packing et une (R + δ)-couverture vide.

Tant que S 6= ∅
1 Trouver x et c de sorte que BG (x, 2R) ∩ S⊆ BG (c, R + δ).
2 Ajouter x au packing et BG (c, R + δ) à la couverture.
3 Retirer de S tous les sommets présents dans BG (c, R + δ).

Sommets de S
Rayon 2R
Rayon R + δ
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème de la R-couverture minimale

Construction du R-packing et de la (R + δ)-couverture de S.

Commencer avec un R-packing et une (R + δ)-couverture vide.

Tant que S 6= ∅
1 Trouver x et c de sorte que BG (x, 2R) ∩ S⊆ BG (c, R + δ).
2 Ajouter x au packing et BG (c, R + δ) à la couverture.
3 Retirer de S tous les sommets présents dans BG (c, R + δ).

Sommets de S
Rayon R
Rayon R + δ
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Graphes δ-hyperboliques ⊲ Algorithme pour le problème ADC

Conséquence sur le problème ADC.

Étant donné un graphe δ-hyperbolique G = (V , E ) et un entier R ≥ 1,

on peut construire en temps polynomial une augmentation admissible E ′
du problème ADC pour D := 2R + 2δ avec un nombre d’arêtes inférieur
ou égal à 2 fois celui d’une solution optimale pour D := 2R.

Rayon R + δ Rayon R − 1 + δ E′
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Plan de l’exposé

1 Méthode
2 État de l’art
3 Résultats
4 Graphe de largeur arborescente bornée
Définitions
Résultats connus
Diamètre pair
Diamètre impair
5 Graphes planaires
Couverture d’un ensemble de sommets de diamètre ≤ 2R
Facteur logarithme pour le problème ADC
6 Graphes δ-hyperboliques
Définitions
Algorithme pour le problème de la R-couverture minimale
Algorithme pour le problème ADC
7 Perspectives
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Perspectives

Lorsque le graphe est planaire :

- Déterminer la constante universelle c.
- Peut-on proposer des algorithmes avec des facteurs constants pour
le problème de la R-couverture minimale et le problème ADC ?
- Montrer l’existence d’une boule de rayon 2R pouvant être couverte
par un nombre constant de boules de rayon R.
- Commencer par considérer les grilles partielles sans trou.

Sans contrainte sur le graphe initial :

- Peut-on approximer le problème ADC avec un facteur O(log |V |).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Perspectives

Lorsque le graphe est planaire :

- Déterminer la constante universelle c.
- Peut-on proposer des algorithmes avec des facteurs constants pour
le problème de la R-couverture minimale et le problème ADC ?
- Montrer l’existence d’une boule de rayon 2R pouvant être couverte
par un nombre constant de boules de rayon R.
- Commencer par considérer les grilles partielles sans trou.

Sans contrainte sur le graphe initial :

- Peut-on approximer le problème ADC avec un facteur O(log |V |).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Perspectives

Lorsque le graphe est planaire :

- Déterminer la constante universelle c.
- Peut-on proposer des algorithmes avec des facteurs constants pour
le problème de la R-couverture minimale et le problème ADC ?
- Montrer l’existence d’une boule de rayon 2R pouvant être couverte
par un nombre constant de boules de rayon R.
- Commencer par considérer les grilles partielles sans trou.

Sans contrainte sur le graphe initial :

- Peut-on approximer le problème ADC avec un facteur O(log |V |).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Perspectives

Lorsque le graphe est planaire :

- Déterminer la constante universelle c.
- Peut-on proposer des algorithmes avec des facteurs constants pour
le problème de la R-couverture minimale et le problème ADC ?
- Montrer l’existence d’une boule de rayon 2R pouvant être couverte
par un nombre constant de boules de rayon R.
- Commencer par considérer les grilles partielles sans trou.

Sans contrainte sur le graphe initial :

- Peut-on approximer le problème ADC avec un facteur O(log |V |).
Problématique Méthode État de l’art Résultats Largeur arborescente Graphes planaires δ-hyperbolicité Perspectives

Perspectives

Lorsque le graphe est planaire :

- Déterminer la constante universelle c.
- Peut-on proposer des algorithmes avec des facteurs constants pour
le problème de la R-couverture minimale et le problème ADC ?
- Montrer l’existence d’une boule de rayon 2R pouvant être couverte
par un nombre constant de boules de rayon R.
- Commencer par considérer les grilles partielles sans trou.

Sans contrainte sur le graphe initial :

- Peut-on approximer le problème ADC avec un facteur O(log |V |).