ter algorithmes parametres .pdf



Nom original: ter-algorithmes-parametres.pdf

Ce document au format PDF 1.5 a été généré par TeX / pdfTeX-1.40.17, et a été envoyé sur fichier-pdf.fr le 17/12/2017 à 01:41, depuis l'adresse IP 176.151.x.x. La présente page de téléchargement du fichier a été vue 233 fois.
Taille du document: 655 Ko (24 pages).
Confidentialité: fichier public


Aperçu du document


TER - Algorithmes paramétrés
Mathieu Blond, Damien Crechet, Matthias Foltier, Antoine Guillaume
17 décembre 2017

1

Sommaire
1 Introduction

3

2 Objectifs

4

3 Besoins fonctionnels
3.1 API Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Besoins non fonctionnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
5
5
5

4 Préliminaires

6

5 Complexité paramétrée
5.1 Algorithmes de noyaux . . . . . . . . .
5.2 Algorithmes de branchements . . . . .
5.3 Un exemple simple : Vertex Cover .
5.3.1 Algorithme de branchement . .
5.3.2 Algorithme de noyau . . . . . .
5.3.3 Règles de réduction . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

7
7
8
8
8
8
8

6 Etude du problème Cluster Editing
6.1 Définitions . . . . . . . . . . . . . . . . . . . .
6.2 Algorithme de branchement . . . . . . . . . .
6.3 Algorithme de noyau . . . . . . . . . . . . . .
6.3.1 Graphe des cliques critiques . . . . . .
6.4 Règles de réduction . . . . . . . . . . . . . . .
6.4.1 Génération pseudo-aléatoire de graphe

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

10
10
11
11
11
12
13

7 Résultats expérimentaux
7.1 Vertex Cover . . . . . . . . . .
7.1.1 Algorithme de noyau . . . .
7.1.2 Algorithme de branchement
7.2 Cluster Editing . . . . . . . . .
7.2.1 Algorithme de noyau . . . .
7.2.2 Algorithme de branchement
7.3 Conclusions . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

15
15
15
16
16
17
17
17

8 Gestion du projet
8.1 Améliorations possibles
8.2 Difficultés . . . . . . . .
8.3 Diagramme de Gantt . .
8.4 Diagramme de classe . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

18
18
18
18
23

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

Bibliographie

24

2

1

Introduction

Théorie de la complexité
La théorie de la complexité est une branche de l’informatique théorique qui sert à mesurer la difficulté
d’un problème en fonction de la taille de l’instance qui lui est associée. Les problèmes algorithmiques se
distinguent en deux parties : les problèmes d’optimisation qui consistent à obtenir la meilleure solution
possible au problème, et les problèmes de décision, demandant une réponse par oui ou par non, le plus
souvent pour savoir s’il existe ou non une solution au problème.
Un bon exemple de problème d’optimisation est le Traveling Salesman Problem (problème du
voyageur de commerce), ou TSP. Il consiste, étant donné un ensemble de villes et des distances les
séparant, à trouver le plus court chemin qui passe une et une seule fois par toutes les villes.
On peut transformer ce problème en problème de décision en demandant s’il existe un chemin qui
passe une et une seule fois par toutes les villes. Cela reste un problème difficile à résoudre, puisqu’il s’agit
en fait du problème du Chemin Hamiltonien qui est un problème NP-Complet.
Lorsque l’on s’intéresse à la complexité d’un algorithme, on peut soit regarder sa complexité en espace,
c’est-à-dire la mémoire requise par l’algorithme pour s’exécuter, soit sa complexité temporelle.
On dit d’un problème qu’il se résout de manière efficace lorsqu’il existe un algorithme le résolvant
avec un temps d’exécution polynomial en fonction de la taille de l’instance considérée.

Hiérarchie des problèmes
Au fil des années, les théoriciens se sont aperçus que certains problèmes étaient intrinsèquement plus
difficiles que d’autres. Ils ont donc commencé à les catégoriser pour les ranger dans différentes classes.
P
Un problème est dit P (Polynomial time) s’il peut être décidé en temps polynomial par une machine
de Turing déterministe.
Il s’agit de la classe des problèmes dits praticables, i.e. qu’on peut résoudre "facilement".
NP
Un problème est dit NP (Nondeterministic Polynomial time) s’il peut être décidé en temps polynomial
par une machine de Turing non-déterministe.
Il s’agit de la classe des problèmes qu’on peut vérifier "rapidement" par un algorithme P.
C-difficile
Si on peut réduire chaque problème d’une certaine classe de complexité C à un problème P (qu’il soit
ou non dans C), on dit de P qu’il est C-difficile.
Cela signifie que, considérant la réduction polynomiale, pour un problème Exemple ∈ C-difficile,
chaque problème de la classe C peut être réduit en temps polynomial au problème Exemple.
C-complet
Pour une certaine classe C, un problème est dit C-complet s’il est à la fois C et C-difficile.

3

2

Objectifs

Ce TER s’inscrit dans le cadre du Parameterized Algorithms and Computational Experiments Challenge, un concours de programmation centré sur les algorithmes paramétrés. Un des
problèmes proposés par le concours est le Minimum Fill-In qui consiste à partir d’un graphe et d’un
paramètre k, à obtenir un ensemble d’au plus k non-arêtes dont l’ajout permet d’obtenir un graphe
triangulé, c’est à dire un graphe dont tout cycle de plus de 3 sommets possède une arête reliant deux
sommets non adjacents du cycle.

Figure 1 – Exemple d’un graphe triangulé
Dans un premier temps, nous allons étudier la notion de complexité paramétrée et implémenter un
algorithme de branchement pour résoudre le problème de Cluster Editing. Puis, nous implémenterons
plusieurs algorithmes de noyau en utilisant des règles de réduction pour réduire la taille de l’entrée définies
dans la section 5.3.3 et 6.4.
En effet un de nos principaux objectif est de savoir si en pratique, pour un paramètre k donné, il est
préférable de réduire légèrement mais rapidement la taille de l’instance ou au contraire prendre plus de
temps pour effectuer une meilleure réduction et ainsi garantir une meilleure vitesse de résolution. Cela
revient à savoir s’il vaut mieux implémenter le meilleur algorithme disponible, ou si une combinaison de
plusieurs algorithmes est plus efficace en pratique.

4

3
3.1

Besoins fonctionnels
API Graphes

Un des principaux besoins est celui d’une API de gestion des graphes facilement réutilisable et extensible. Opérant dans un contexte objet, l’héritage sera fortement utilisé pour définir des classes généralistes
qui pourront aider à la création de classes plus spécifiques. Pour une vue plus globale, il est conseillé de
consulter le diagramme de classe en section 8.4.

3.2

Benchmark

Afin de répondre aux attentes de ce TER une classe permettant d’évaluer les performances des
fonctions a été mise au point. Elle permettra de mesurer la complexité approximative en temps des
divers algorithmes qui seront décrits dans la suite de ce rapport.

3.3

Besoins non fonctionnels

Le choix du langage d’implémentation à été débattu entre Java, Python et C++. Les algorithmes à
implémenter étant très gourmands en mémoire, nous avons porté notre choix sur le C++ car il permet
une gestion plus fine de la mémoire, il possède un typage fort, et il compile en code natif, ce qui signifie que
nous n’aurons pas les pertes de performances liées à l’interprétation du code, ni au surplus d’utilisation
de mémoire d’une machine virtuelle telle que la JVM.

Figure 2 – Structure de donnée graphe
Le graphe est représenté par un dictionnaire (unordered map), dont les clés sont les identifiant des
sommets, et les valeurs sont des vecteurs contenant les identifiants des voisins de ces sommets. En
l’absence de set de données réelles pour tester nos algorithmes, nous avons également conçu un générateur
de graphe pseudo aléatoire paramétrable pour répondre à nos besoins.

5

4

Préliminaires

Un graphe est un ensemble de points nommés nœuds (ou sommets) reliés par des traits (ou flèches
dans le cas d’un graphe orienté) nommés arêtes (ou liens, ou arcs). On utilisera la notation G = (V, E)
avec V l’ensemble des sommets du graphe G, et E l’ensemble des arêtes.
On dit de deux arêtes d’un graphe qu’elles sont adjacentes si elles ont au moins un sommet en
commun, également, une arête e est incidente à un sommet v si v ∈ e.

Figure 3 – Exemple d’un graphe non orienté à 6 sommets
Deux sommets d’un graphe sont voisins ou adjacents s’ils ont au moins une arête incidente en commun,
on utilisera la notation NG (v) pour désigner l’ensemble des voisins d’un sommet v.
Lorsque plusieurs arêtes relient deux sommets, on les appelle des arêtes multiples, et une boucle
est une arête dont les deux extrémités sont identiques. On peut alors définir le fait qu’un graphe est
simple s’il ne contient ni boucle ni arêtes multiples, et qu’un graphe est complet si tous ses sommets sont
adjacents.

Figure 4 – Le graphe "K5", un graphe complet
Definition 1. Dans un graphe, le degré d’un sommet v, noté d(v), correspond au nombre d’arêtes
incidentes à v.
Definition 2. Le graphe G0 = (V 0 , E 0 ) est le sous-graphe de G = (V, E) induit par V 0 , si V 0 ⊂ V et
E 0 = {{u, v} ∈ E|u ∈ V 0 , v ∈ V 0 }

Figure 5 – Exemple d’un sous graphe induit
Definition 3. Une clique de G est un sous-graphe complet de G.

6

5

Complexité paramétrée

Introduite au début des années 90, la complexité paramétrée est une branche de la théorie de la
complexité qui se concentre principalement sur les problèmes NP-Complets. Ces problèmes étant difficiles
à résoudre, la question suivante s’est posée : est-il possible de faciliter la résolution d’un problème en y
ajoutant un paramètre spécifique ?
L’intuition est simple : il s’agit d’ajouter à toute instance I d’un problème L un paramètre k |I|,
dépendant du problème en question. On dit alors que L est un problème paramétré.
De là se distinguent plusieurs classes de problèmes, étant donnée une instance (I, k) d’un problème
NP-Complet L :
— XP : on peut résoudre le problème L avec une complexité de la forme O(|I|k )
— FPT : on peut résoudre le problème L avec une complexité de la forme f (k) · |I|O(1) pour une
certaine fonction calculable f .
— W [t] : la W-hiérarchie est une hiérarchie des problèmes paramétrés. On peut noter que W [0] =
F P T et W [i] ⊆ W [j] pour tout i < j. Certains problèmes NP-Complets appartiennent aux classes
W [t] avec t > 0, notamment la version paramétrée de Clique qui, malgré sa simplicité apparente,
appartient à la classe W [1].[2]
Un algorithme FPT pour un problème paramétré L est donc un algorithme résolvant une instance
(I, k) du problème avec une complexité f (k) · |I|O(1) pour une certaine fonction calculable f . On espère
ainsi que pour des petites valeurs de k, ce qui est souvent le cas en pratique, f (k) restera petit (même
s’il est exponentiel en k). Il sera alors possible de décider rapidement le problème.
En d’autres termes, l’objectif de la complexité paramétrée est de déterminer si l’explosion combinatoire pour résoudre un problème peut être confinée au paramètre k.

5.1

Algorithmes de noyaux

Une des manières les plus efficaces pour construire un algorithme FPT est d’utiliser un algorithme de
noyau [4]. Un algorithme de noyau est un algorithme polynomial en |I| + k qui transforme une instance
donnée (I, k) d’un problème L en une nouvelle instance (I 0 , k 0 ) de L, vérifiant k 0 ≤ f (k). On appelle
cette nouvelle instance un noyau. L’instance originale (I, k) considérée est une instance positive si et
seulement si la nouvelle instance (I 0 , k 0 ), le noyau, en est une.

Figure 6 – Schématisation d’un algorithme de noyau
Le paramètre k permet de réduire l’instance du graphe, ce qui est nécessaire étant donné la complexité
des problèmes NP-complets. Cependant, cette complexité est inégale : certaines parties du problème
peuvent être particulièrement dures, elles en constituent ainsi le cœur, tandis que d’autres sont assez
faciles à gérer. Ainsi, avant d’exécuter un algorithme sur un problème qui peut être dur, il est préférable
de passer du temps à réduire ce problème pour ne plus avoir à considérer que son cœur.
Ce genre d’algorithme est assez proche d’un mécanisme de pre-processing, le paramètre k servant ici
à le formaliser et à fixer une borne de réduction.
Definition 1. Une règle de réduction est un algorithme qui associe à une instance (I, k) d’un problème
L une autre instance (I 0 , k 0 ), avec |I 0 | ≤ |I| et k 0 ≤ k. Autrement dit c’est un algorithme qui prend en
paramètre une instance d’un problème et le modifie pour en produire une instance réduite.
Définir l’ordre optimal d’application des règles lors de l’exécution de l’algorithme est un problème
que l’on ne sais pour l’instant pas résoudre de manière exacte car il s’agit d’un problème NP-Complet.
Il existe cependant des heuristiques qui permettent des résultats approchés.

7

5.2

Algorithmes de branchements

Par définition, un algorithme de branchement prend en entrée une instance I d’un problème L et
indique si l’instance est positive. Pour cela, l’algorithme construit un arbre qui contient des instances
possibles du problème jusqu’à atteindre la solution qui indiquera si I est ou non une instance positive.
L’arbre est parcouru en profondeur : à chaque étape, si l’instance n’est pas positive et qu’il est possible
d’y faire des changements, on branche sur chacun des changements, sinon, on backtrack. Ainsi, à chaque
nœud est associée une instance I du problème, et à chacun de ses fils, des nouvelles instances I 0 obtenues
via une fonction de mutation fm (I) = I 0 .
Cette approche est très proche du brute force, mais on peut par exemple ignorer une instance I 0 si
celle ci existe déjà dans le graphe ou utiliser la version paramétrée de l’algorithme pour limiter l’explosion
combinatoire.

5.3

Un exemple simple : Vertex Cover

Vertex Cover est un problème qui consiste, étant donné un graphe non orienté, à trouver un
ensemble minimum de sommets pour couvrir toutes les arêtes. Autrement dit, en considérant un graphe
G = (V, E) et un ensemble minimum C de sommets, chaque arête de G est incidente à au moins un
sommet de C.
Le problème d’optimisation consiste à trouver le plus petit entier k, tel qu’il existe un ensemble de
sommets de taille k couvrant toutes les arêtes. Le problème de décision consiste à dire s’il existe un tel
ensemble de taille k donnée en entrée.
Nous ne parlerons dans le suite que du problème de décision.

Figure 7 – Exemples de couvertures minimales par sommets

5.3.1

Algorithme de branchement

L’algorithme de branchement pour Vertex Cover est assez simple, il consiste à chercher une arête
(u, v) présente dans le graphe G et a brancher sur les deux possibilités suivantes :
— Ajouter u à la solution, brancher sur G − u
— Ajouter v à la solution, brancher sur G − v
L’algorithme branchera jusqu’à une profondeur k (taille maximum recherchée du Vertex Cover) où
il effectuera un backtrack. Il répondra positivement s’il ne trouve pas d’arête à une étape, négativement
s’il a backtracké jusqu’à l’instance initiale (i.e tout l’arbre a été parcouru).
La complexité de cet algorithme est de l’ordre de 2k .
5.3.2

Algorithme de noyau

L’algorithme de noyau associé utilise les règles de réduction décrite dans la section 5.3.3 pour réduire la
taille d’une l’instance, jusqu’à ce qu’elle soit vide ou qu’on ne puisse plus appliquer de règle de réduction.
5.3.3

Règles de réduction

Règle 1. Supprimer les sommet de degré 0.
Les sommets de degré 0 ne couvrant aucune arête, il est inutile de les conserver dans le graphe.
Règle 2. Pour tout sommet u de degré 1 ayant pour voisin v, supprimer u et v du graphe et ajouter v
à la solution.

8

Démonstration. Soit un graphe G = (V, E) et u ∈ V un sommet isolé (d(u) = 1) et v son voisin. Il existe
alors une solution optimale S de Vertex Cover telle que u ∈
/ S et v ∈ S.
— Si d(v) = 1, alors u et v forment une composante connexe, et uniquement l’un des deux sommets
doit être dans la solution pour qu’elle soit optimale.
— si d(v) > 1, alors sélectionner u dans la solution pourrait la rendre non optimale, car d(v) > d(u).

Figure 8 – Exemple d’application de la règle 2
Le sommet u n’étant relié qu’au sommet v, et v pouvant être de degré > 1, il ne peut pas être pire
de sélectionner v, et, dans la plupart des cas, il est même préférable de l’avoir choisi.
Règle 3. Pour tout sommet u de degré supérieur ou égal à k + 1, ajouter u à la solution et le supprimer
du graphe.
Cette règle repose sur le fait qu’un sommet dont le degré dépasse k doit être présent dans chaque
solution de taille au plus k. ( Si le degré de u dépasse k mais que u n’est pas inclus dans la solution, alors
tous les voisins de u doivent être dans la solution. La taille de la solution sera alors d’au moins k + 1.)
Règle 4. Pour tout sommet u de degré égal à 2, si ses deux voisins {v, w} sont également voisins entre
eux, supprimer u du graphe et ajouter v et w a la solution.
Démonstration. Soit un graphe G = (V, E) et u ∈ V tel que d(u) = 2. Soient v et w ses voisin tel que
(v, w) ∈ E. Il existe alors une solution optimale S telle que u ∈
/ S et {v, w} ⊆ S.
Dans cette configuration au moins deux des trois sommets (u, v et w) doivent être dans S.
— Si d(v) = d(w) = 2, u, v et w forment alors une composante connexe. Choisir uniquement u ne
couvrirait pas l’arête {v, w}.
— Si d(v) ≥ 2 et d(w) ≥ 2, en plus du cas précédent, les ensembles {u, v} et {u, w} couvrent
potentiellement moins d’arêtes que {v, w}. On ne peut donc pas prendre {u, v} ou {u, w} dans
une solution optimale.
On constate que pour 3 sommets formant un triangle, si l’un deux n’a pas d’autre voisin, alors on
peut sélectionner les deux autres sommets dans la solution, car au minimum, ils couvriront toute les
arêtes du triangle.

9

6

Etude du problème Cluster Editing

Un des principaux sujets de ce TER est problème du Cluster Editing. Pour résoudre ce problème, nous avons créé deux classes ClusterEditingBranchAlgorithm et ClusterEditingKernelAlgorithm qui correspondent aux algorithmes décrits respectivement dans les sections 6.2 et 6.3.

6.1

Définitions

Le problème NP-Difficile du Cluster Editing consiste à transformer un graphe G en une union disjointe de cliques G0 en trouvant un ensemble d’au plus k modifications d’arêtes ( insertion et suppression
d’une arête). Le graphe G0 est appelé cluster graph.
Algorithme 1 : Cluster Editing
Entrées : Graphe G=(V,E), entier k >= 0
Sorties : Le graphe G peut-il être transformé en une union disjointe de cliques avec au plus k
modifications ?

Figure 9 – Exemple de résolution de Cluster Editing
Definition 1. Une clique critique d’un graphe G est une clique K dans laquelle tous les sommets de K
ont le même ensemble de sommets voisins dans V \K. Dans cette configuration K est maximale.

Figure 10 – Un graphe avec ses cliques critiques entourées
Definition 2. Soit un graphe G = (V, E) et W l’ensemble des cliques critiques de ce graphe. On peut
alors définir le graphe des cliques critiques C = (W, Ec ) tel que
{Ki , Kj } ∈ Ec ⇐⇒ ∀u ∈ Ki , v ∈ Kj : {u, v} ∈ E
En d’autres mots, le graphe des cliques critiques a les cliques critiques comme nœuds, et deux nœuds
sont connectés si les cliques critiques correspondantes forment une plus grande clique.
Definition 3. On qualifie de P3 tout chemin de longueur 2 (composé de trois sommets) dont les extrémités ne sont pas reliées entre elles.

Figure 11 – Deux P3 respectivement entourés de rouge et de bleu
10

6.2

Algorithme de branchement

L’algorithme de branchement pour Cluster Editing consiste à chercher un P3 présent dans le
graphe en entrée et a brancher sur les trois possibilités suivantes :
— Supprimer l’arête entre le sommet u et v, brancher
— Supprimer l’arête entre le sommet v et w, brancher
— Ajouter une arête entre le sommet u et w, brancher
L’algorithme branchera jusqu’à une profondeur k (nombre maximum d’arêtes à ajouter ou supprimer)
où il effectuera un backtrack. Il répondra positivement s’il ne trouve pas de P3 à une étape, négativement
s’il a backtracké jusqu’à l’instance initiale (i.e tout l’arbre a été parcouru).
La complexité de cet algorithme est de l’ordre de 3k .

6.3

Algorithme de noyau

Cluster Editing admet un algorithme de noyau réduisant la taille de l’instance donnée en entrée.
Pour cela il utilise un paramètre k correspondant au nombre maximum de modifications possibles. Jiong
Guo montre que la nouvelle instance obtenue a au plus 6k sommets [4]. Pour effectuer la réduction de
G, il utilise le graphe des cliques critiques. En effet dans le cluster graph tous les sommets d’une clique
non affectés par une modification d’arête doivent former une clique critique dans le graphe en entrée. Il
semble donc plus simple de travailler sur les cliques critiques et le graphe de cliques critiques que sur
le graphe en entrée. Guo en déduit deux règles de réductions qui montrent que l’instance a au plus 6k
sommets. Guo montre également qu’il existe un algorithme permettant de réduire le graphe en entrée et
d’obtenir un graphe avec au plus 4k sommets, mais nous étudierons seulement le premier.
6.3.1

Graphe des cliques critiques

Il existe un algorithme qui extrait les cliques critiques d’un graphe non-orienté [5]. Il est composé de
trois phases décrites ci-dessous.
Dans la première phase, la liste d’adjacence de chaque sommet est modifiée de cette façon : ADJ(v) =
[v, |N [v]|, v1, v2, ...vk].
Algorithme 2 : Preprocessing phase
Entrées : Graphe G=(V,E)
Sorties : max
Début
pour tous les sommets v de V faire
Ajouter v à la liste d’adjacence de v;
Trier la liste d’adjacence de v;
l = Taille de la liste d’adjacence de v;
Insérer l puis v au début de la liste d’adjacence de v ;
max = Taille de la plus grande liste d’adjacence de G;
Algorithme 3 : Sorting phase
Entrées : Graphe G=(V,E), max
Sorties : L
Début
L = [];
pour tous les sommet v de V faire
Ajouter la liste d’adjacence de v à L;
i = 1;
tant que i < max faire
RadixSort(L,i);
i = i + 1;

11

Algorithme 4 : Merging phase
Entrées : L
Sorties : CC
Début
CC = ;
T =;
lu = L[1];
u = Premier élément de lu;
T = T ∪ u;
pour i = 2 à |V| faire
lv = L[i];
v = Premier élément de lv;
si lu = lv du deuxième élément au dernier alors
T = T ∪ v;
sinon
CC = CC ∪ T ;
T = v;
lu = lv;
CC = CC ∪ T ;

Preuve Montrons que deux sommets u et v appartenant à la même clique critique seront groupés
ensemble avec l’algorithme. La preuve se fait par contradiction. Supposons que u et v ne sont pas groupés
dans la même clique critique. u et v ont le même voisinage proche dans leur liste d’adjacence. A la fin
de la sorting phase la liste d’adjacence de u apparaît avant celle de v. Soit elles sont consécutives, soit
d’autres listes d’adjacence de sommets ayant le même voisinage sont entre les deux. Un sommet n’ayant
pas le même voisinage ne peut pas être entre u et v car le tri ne serait alors pas bon. Dans la merging
phase, les listes d’adjacence de u à v sont groupées ensembles dans une clique critique. Cela contredit la
supposition initiale où u et v ne sont pas dans la même clique critique. La propriété maximale des cliques
critiques formées est ainsi garantie car deux sommets dans une même clique critique seront toujours
groupés ensemble.
Complexité La complexité de la première phase est O(|E| + |V |). La sorting phase a une complexité
de O(|E| + |V |). Il faut ajouter la complexité du parcours de la liste dans chaque itération du RadixSort.
Il y a max itérations, ce qui donne O(max.|V |). On note que max est lié au degré maximum d de G.
La complexité totale de la sorting phase est donc O(d.|V | + |E|). La complexité de la merging phase est
O(|E| + |V |). La complexité de l’algorithme est O(d.|V | + |E|).

6.4

Règles de réduction

On considère un graphe G et son graphe des cliques critiques C. On note V (K) les sommets d’une
2

clique critique K. On note Nc [K] les voisins de K et N c (K) les voisins à une distance 2 de K.
Règle 1. Supprimer toutes les cliques critiques isolées K de C et supprimer V (K) de G.
S
S
Règle 2. Si, pour un nœud K de C, |V (K)| > | K 0 ∈Nc (K) V (K 0 )|+|
V (K 0 )|, alors supprimer
2
K 0 ∈N c(K)
S
K et ses voisins de C et supprimer K 0 ∈Nc [K] V (K 0 ) de G. Soustraire à k la somme du nombre d’arêtes
S
nécessaires pour modifier [ K 0 ∈Nc (K) V (K 0 )] en un graphe complet et du nombre d’arêtes dans G entre
S
S
0
V (K 0 ). Si k < 0, alors l’instance n’a pas de solution.
2
K 0 ∈Nc (K) V (K ) et
0
K ∈N c(K)

Comme la clique critique K possède plus de sommets que ses voisins et ses voisins à distance deux,
on la supprime avec ses voisins direct car il est moins cher de l’isoler que d’ajouter ou de supprimer des
arêtes pour obtenir une clique disjointe.

12

Exemple : Application de la règle 2 À gauche un graphe G et à droite son graphe des cliques
critiques C. En bas le graphe G modifié. La clique critique 1 contient quatre sommets (1, 2,3 et 4) et
ses voisins en contiennent deux (5 et 6) et la clique critique 7 à une distance deux contient un sommet.
On peut donc appliquer la règle 2 pour la clique critique 1. Tous les nœuds sont supprimés de C. Les
sommets des cliques critiques 1, 4 et 5 sont supprimés de G. Il faut rajouter une arête entre les sommets
5 et 6 de G pour obtenir un sous-graphe complet et il y a une arête entre les sommets 6 et 7 de G. Le
paramètre k sera donc réduit de 1 + 1 = 2.

Figure 12 – Exemple d’application de la règle 2.
6.4.1

Génération pseudo-aléatoire de graphe

L’API dispose d’un moyen de générer des unions disjointes de cliques en fonction d’un nombre de
sommet |V | et d’une taille de clique maximale C.
Pour générer des graphes pseudo aléatoire, on introduit du bruit dans cette construction. C’est à
dire qu’on ajoute ou supprime des arêtes en fonction d’un pourcentage relatif a |V |, on peut également
garantir que le graphe final sois connexe au prix d’arêtes supplémentaire.
On garantit également le pourcentage de bruit en n’ajoutant que des arêtes n’appartenant pas à
l’union disjointe de clique, et en supprimant uniquement des arêtes y appartenant.
Pour générer des nombres aléatoires, on utilise l’algorithme Mersenne Twister développé par Makoto
Matsumoto et Takuji Nishimura en 1997. Cette procédure se base sur un type particulier de registre à
décalage à rétroaction, et elle utilise lors de la génération le nombre premier de Mersenne (219937 − 1). Il
a pour période 219937 − 1, il est distribué selon une loi uniforme et est aléatoire quel que soit le poids du
bit considéré.

13

Algorithme 5 : Génération de graphe pseudo-aléatoire
Entrées : Nombre de sommet N, Taille de clique maximale C, Bruit(float), connexité(booleen)
Sorties : Un graphe pseudo-aléatoire
Début
Créer une liste d’identifiant IdList de 0 a N;
Mélanger IdList;
tant que IdList 6= ∅ faire
Générer un entier aléatoire x entre 1 et C mod |IdList|;
Créer une clique avec les x premiers identifiants de IdList;
Retirer les x premiers identifiants de IdList;
aAjouter = ∅;
aSupprimer = ∅;
aBruiter = N × Bruit;
tant que aBruiter 6= 0 faire
Sélectionner un sommet aléatoire i;
Sélectionner un sommet aléatoire w 6= i;
si w est un voisin de i ET {w, i} ∈
/ aSupprimer alors
ajouter {w, i} à aSupprimer;
aBruiter–;
sinon si w n’est pas un voisin de i ET {w, i} ∈
/ aAjouter alors
ajouter {w, i} à aAjouter;
aBruiter–;
Ajouter les éléments de aAjouter au graphe;
Supprimer les éléments de aSupprimer du graphe;
si connexité alors
pour i de 0 à N − 1 faire
si il n’existe pas d’arête entre i et i+1 alors ajouter {i, i + 1} au graphe ;

14

7

Résultats expérimentaux

Dans cette section, nous partagerons les résultats et les performances des algorithmes de noyau et
de branchement détaillés dans les sections précédentes. Ces résultats prendront en compte le temps
d’exécution moyen en fonction d’une taille n d’un graphe G fourni en entrée.
Chaque temps d’exécution donné ici est issu d’une moyenne d’un grand nombre itération du code
concerné sur des instances de graphe aléatoire différentes.
Il est important de comprendre que les valeurs indiquées seront différentes entre chaque système ou
mesure et qu’il s’agit ici de valeurs indicatives.
Le système utilisé pour ces simulations est équipé d’un processeur quatre cœur cadencé à 3.5GHz et
16Go de mémoire vive DDR3 1600MHz. L’utilisation moyenne du processeur était de 25% à 30%.

7.1

Vertex Cover

Nous utiliserons dans cette section des graphes générés aléatoirement par l’algorithme décrit dans la
section 6.4.1, avec comme paramètre un bruit de 70%, une taille maximale de clique de N/10 et aucune
garantie de connexité.

On se basera sur des valeurs raisonnables du paramètre k, à savoir log(n), ln(n) et n. Le but étant
de montrer l’explosion combinatoire lorsque k > log(n) pour les algorithmes de branchement. En théorie
à partir de cette borne, le temps d’exécution n’est plus polynomial en la taille de l’entrée.
7.1.1

Algorithme de noyau

15

7.1.2

7.2

Algorithme de branchement

Cluster Editing

Nous utiliserons dans cette section des graphes générés aléatoirement, avec comme paramètre un
bruit égal au paramètre k, c’est a dire une nombre d’arêtes mal placées égal à k. Une taille maximale de
clique de N/10 et aucune garantie de connexité. La taille des graphes a du être revue à la baisse à cause
d’une plus grande complexité en temps.

16

7.2.1

Algorithme de noyau

7.2.2

Algorithme de branchement

7.3

Conclusions

On constate que pour les algorithmes de branchement, l’explosion combinatoire se produit pour
k > log(n), ce qui est un comportement normal. Les algorithmes de noyaux suivent plus ou moins
le même comportement, mais avec une borne légèrement supérieure à log(n) pour Vertex Cover.
Cependant il apparaît que l’algorithme de noyau de Cluster Editing a un comportement qui n’est pas
17

naturel. Cela est sûrement dû a une erreur d’implémentation, même si les tests unitaires sur des petits
exemples montrent un comportement correct.

8

Gestion du projet

Nous détaillerons ici tout les éléments en rapport avec la conduite de ce TER, la répartition des
tâches, les améliorations à apporter, ainsi que les difficultés rencontrés par l’équipe.

8.1

Améliorations possibles

— Étant donnée la nature de certains graphes, on pourrait envisager l’utilisation d’ensembles (unordered set) plutôt que de vecteurs pour représenter les voisins d’un sommet. En effet dans le cas où
le graphe ne comporte pas d’arête multiple nous n’avons pas besoin de représenter plusieurs fois le
même voisin. Les sets sont dans ce cas plus adaptés : ils éliminent le besoin d’un test d’existence
lors de l’ajout et proposent des fonctions pour vérifier la présence d’un élément, ce qu’un vecteur
ne propose pas en C++ standard.
— Des optimisations plus générales, par exemple l’utilisation d’itérateurs constants par référence sur
les boucles où cela est possible, ou encore réduire l’utilisation de variables pour optimiser l’espace
en mémoire.
— Rechercher et implémenter des algorithmes de noyau et de branchement plus efficaces
— Utiliser des heuristiques pour déterminer un ordre efficace d’application des règles de réduction
dans les algorithmes de noyau, afin d’obtenir des noyaux plus petits sans changer le temps d’exécution.

8.2

Difficultés

Une des principales difficultés fut de comprendre la complexité paramétrée et les types d’algorithmes
associés (notamment les algorithmes de branchement et de noyau). La lecture des articles de recherche
correspondant et leur compréhension pris également un peu de temps.
L’implémentation a du être revue à plusieurs reprise au fur et à mesure que les problèmes dont nous
n’avions pas conscience sont apparus, une étape de réflexion préliminaire plus approfondie aurait été
profitable.

8.3

Diagramme de Gantt

18

TER
Tâches

18 mai 2017
2

Nom
Réunions TER
Réunion 1
Réunion 2
Réunion 3
Réunion 4
Réunion 5
Réunion 6

Date de début
15/02/17
15/02/17
02/03/17
23/03/17
04/05/17
16/05/17
19/05/17

Date de fin
18/05/17
15/02/17
02/03/17
23/03/17
04/05/17
16/05/17
19/05/17

Etude des ressources / Travail théorique
Création d'une structure graphe basique

15/02/17
23/02/17

07/03/17
07/03/17

Rédaction du rapport intermédiaire
Rapport intermédiare
Debut de rédaction

08/03/17
17/03/17
08/03/17

16/03/17
17/03/17
08/03/17

Rédaction du rapport final
Git Flow
Création structure Git
cmake, build options
Algorithme de noyau Vertex Cover, c++ 11 iterators
cmake pour c++11, adoption des conventions
Refactorisation graphes et algorithmes, structure de l'API
Fonction de manipulation de graphes, création de graphe aléatoire naive
Révision de l'algorithme de noyaux Vertex Cover, nettoyage du code
Gestion des cliques critiques, du graphes des cliques critiques
Regle de reduction 1 pour Cluster Editing
Mise à jour de la regle de reduction 1 pour Cluster Editing
Génération paramétrable de cluster graphe, corrections diverse
Regle de reduction 2 pour Cluster Editing

14/05/17
23/03/17
23/03/17
23/03/17
31/03/17
03/04/17
04/04/17
05/04/17
06/04/17
12/04/17
13/04/17
19/04/17
22/04/17
22/04/17

19/05/17
17/05/17
23/03/17
23/03/17
31/03/17
03/04/17
04/04/17
05/04/17
06/04/17
12/04/17
13/04/17
19/04/17
22/04/17
22/04/17

TER
Tâches
Nom
Mise à jour de la génération de graphe avec les méthodes de l'API, correction
de bugs
Algorithme de noyau de Cluster Editing
Ajout des classes correspondant aux différents type de graphes
Refactorisations, nettoyage du code
Algorithme de branchement Cluster Editing
Suppression des customs types
Amélioration de l'algortihme de génération de graphes des cliques critiques
légères optimisations, nettoyage et corrections
Ajout d'algorithmes classiques BFS, DFS
Création de l'outil de benchmark, gestions de confilts
Correction des règles de reduction ClusterEditing
Correction de l'algorithme de branchement ClusterEditing
Refactorisation générale, création d'une classe de test
Patching des fuites mémoires

18 mai 2017
3

Date de début
25/04/17

Date de fin
25/04/17

26/04/17
27/04/17
03/05/17
03/05/17
09/05/17
11/05/17
11/05/17
14/05/17
14/05/17
18/05/17
18/05/17
18/05/17
18/05/17

26/04/17
27/04/17
03/05/17
03/05/17
09/05/17
11/05/17
11/05/17
14/05/17
14/05/17
18/05/17
18/05/17
18/05/17
18/05/17

TER
Diagramme de Gantt

18 mai 2017
5
2017

Réunion 1

Nom

Date de début

Date de fin

Réunions TER

15/02/17

18/05/17

Etude des ressources / Travail théorique

15/02/17

07/03/17

Création d'une structure graphe basique

23/02/17

07/03/17

Rédaction du rapport intermédiaire

08/03/17

16/03/17

Rédaction du rapport final

14/05/17

19/05/17

Git Flow

23/03/17

17/05/17

Création structure Git

23/03/17

23/03/17

cmake, build options

23/03/17

23/03/17

Algorithme de noyau Vertex Cover, c++ 11 iterators

31/03/17

31/03/17

cmake pour c++11, adoption des conventions

03/04/17

03/04/17

Refactorisation graphes et algorithmes, structure de l'API

04/04/17

04/04/17

Fonction de manipulation de graphes, création de graphe aléat... 05/04/17

05/04/17

Révision de l'algorithme de noyaux Vertex Cover, nettoyage du ... 06/04/17

06/04/17

Gestion des cliques critiques, du graphes des cliques critiques

12/04/17

12/04/17

Regle de reduction 1 pour Cluster Editing

13/04/17

13/04/17

Mise à jour de la regle de reduction 1 pour Cluster Editing

19/04/17

19/04/17

Génération paramétrable de cluster graphe, corrections diverse

22/04/17

22/04/17

Regle de reduction 2 pour Cluster Editing

22/04/17

22/04/17

Mise à jour de la génération de graphe avec les méthodes de l'... 25/04/17

25/04/17

Algorithme de noyau de Cluster Editing

26/04/17

26/04/17

Ajout des classes correspondant aux différents type de graphes

27/04/17

27/04/17

Refactorisations, nettoyage du code

03/05/17

03/05/17

Algorithme de branchement Cluster Editing

03/05/17

03/05/17

Suppression des customs types

09/05/17

09/05/17

Amélioration de l'algortihme de génération de graphes des cliq... 11/05/17

11/05/17

légères optimisations, nettoyage et corrections

11/05/17

11/05/17

Ajout d'algorithmes classiques BFS, DFS

14/05/17

14/05/17

Création de l'outil de benchmark, gestions de confilts

14/05/17

14/05/17

Correction des règles de reduction ClusterEditing

18/05/17

18/05/17

Correction de l'algorithme de branchement ClusterEditing

18/05/17

18/05/17

Refactorisation générale, création d'une classe de test

18/05/17

18/05/17

Patching des fuites mémoires

18/05/17

18/05/17

Réunion 2 Debut de rédaction
Rapport intermédiare
cmake, build
Création
Réunion
3
structure
options
#64 Git
#68
#74
#77
#79

#84
Regle de reduction
#90 Regle
#921 pour
#98
de
Algorithme
#104
reduction
Cluster Editing
de
2Refactorisations,
Algorithme
pour
Réunion
noyau
Cluster
deSuppression
4de
Cluster
#114
#116
Editing
branchement
nettoyage
Editing
#121
Ajout
Réunion
des
d'algorithmes
#130
#128
#126
Patching
du
customs
Cluster
Réunion
code
5 Editing
des
types
6 classiques
fuites mémoires
BFS, DFS

Semaine 7

Semaine 8

Semaine 9

Semaine 10 Semaine 11 Semaine 12 Semaine 13 Semaine 14 Semaine 15 Semaine 16 Semaine 17 Semaine 18 Semaine 19 Semaine 20 Semaine 21 Semaine 22 Semaine 2

13/02/17

20/02/17

27/02/17

06/03/17

13/03/17

20/03/17

27/03/17

03/04/17

10/04/17

17/04/17

24/04/17

01/05/17

08/05/17

15/05/17

22/05/17

29/05/17

05/06/17

TER
Diagramme des Ressources

18 mai 2017
6
2017

Réunion 1

Nom
Antoine Guillaume
Damien Crechet
Mathieu Blond
Matthias Foltier

Rôle par défaut
Non
Non
Non
Non

défini
défini
défini
défini

Réunion 2 Debut de rédaction
Rapport intermédiare
cmake, build
Création
Réunion
3
structure
options
#64 Git
#68
#74
#77
#79

#84
Regle de reduction
#90 Regle
#921 pour
#98
de
Algorithme
#104
reduction
Cluster Editing
de
2Refactorisations,
Algorithme
pour
Réunion
noyau
Cluster
deSuppression
4de
Cluster
#114
#116
Editing
branchement
nettoyage
Editing
#121
Ajout
Réunion
des
d'algorithmes
#130
#128
#126
Patching
du
customs
Cluster
Réunion
code
5 Editing
des
types
6 classiques
fuites mémoires
BFS, DFS

Semaine 7

Semaine 8

Semaine 9

Semaine 10 Semaine 11 Semaine 12 Semaine 13 Semaine 14 Semaine 15 Semaine 16 Semaine 17 Semaine 18 Semaine 19 Semaine 20 Semaine 21 Semaine 22 Semaine

13/02/17

20/02/17

27/02/17

06/03/17

13/03/17

20/03/17

27/03/17

03/04/17

10/04/17

17/04/17

24/04/17

01/05/17

08/05/17

15/05/17

150%

200%

125%

200%

125%

200%

22/05/17

29/05/17

05/06/17

8.4

Diagramme de classe

Figure 13 – Hiérarchie des classes Algorithm

Figure 14 – Hiérarchie des classes Graph

23

Bibliographie
[1] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes : A survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics,
Philadelphia, PA, 1999.
[2] Downey, Fellows, and Regan. Parameterized circuit complexity and the W hierarchy. TCS : Theoretical Computer Science, 191, 1998.
[3] M. R. Garey and D. S. Johnson. Computers and intractability ; a guide to the theory of NPcompleteness. W.H. Freeman, 1979.
[4] J. Guo. A more effective linear kernelization for cluster editing. Theoretical Computer Science,
410(8-10) :718–726, 2009.
[5] Nikhil Pandey. Critical cliques and their application to influence maximisation in online social networks. pages 7–20, 2012.

24


ter-algorithmes-parametres.pdf - page 1/24
 
ter-algorithmes-parametres.pdf - page 2/24
ter-algorithmes-parametres.pdf - page 3/24
ter-algorithmes-parametres.pdf - page 4/24
ter-algorithmes-parametres.pdf - page 5/24
ter-algorithmes-parametres.pdf - page 6/24
 




Télécharger le fichier (PDF)


ter-algorithmes-parametres.pdf (PDF, 655 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


ter algorithmes parametres
thgraphes
poly algo
serie02 gra
tp8
mqg 1