Ce sujet est consacré au calcul d'un paramètre de graphe appelé couverture minimale, défini comme étant le plus petit nombre de sommets d'un ensemble couvrant. On étudiera plusieurs façon de le calculer, ce qui nous permettra de faire un tour d'horizon de quelques techniques algorithmiques modernes.

Ce sujet est constitué de 6 parties qui peuvent être traitées relativement indépendamment; cependant, les concepts introduits dans une partie peuvent être réutilisés dans des parties ultérieures.

Dans la première partie (page 3) on découvre progressivement certaines propriétés des couvertures minimales, leurs valeurs sur quelques familles de graphes simples et leurs liens avec d'autres paramètres classiques de la théorie des graphes.
Dans la deuxième partie (page 4) on développe deux algorithmes efficaces qui calculent un ensemble couvrant minimum d'un arbre.
Dans la troisième partie (page 5) on étudie deux heuristiques naturelles calculant un ensemble couvrant s'avérant loin d'être minimum, pour finalement découvrir un algorithme simple calculant une approximation de la couverture minimale.
Dans la quatrième partie (page 7) on découvre la complexité paramétrée.
Dans la cinquième partie (page 9) on continue notre exploration de la complexité paramétrée en introduisant la notion de noyau.
Dans la sixième partie (page 10) on découvre la puissance de l'optimisation linéaire, permettant une autre approximation de la couverture minimale ainsi qu'un noyau plus petit que celui de la partie V.

Notations et définitions

Un graphe (non-orienté) est la donnée d'un ensemble fini de sommets et d'un ensemble dont les éléments, appelés arêtes, sont des paires de sommets de . On notera le fait que deux sommets et sont reliés par une arête par . On dit que et sont les extrémités de l'arête et que et sont adjacents dans .
Une conséquence de cette définition est que tous les graphes considérés sont simples, c'est à dire sans boucle ( n'est pas une arête), et avec au plus une arête entre deux sommets.
Soit un sommet d'un graphe . Le voisinage de est l'ensemble des sommets adjacents à , c'est-à-dire . Le degré d est le cardinal de .
Un chemin dans un graphe est une liste de sommets deux à deux distincts tels que pour tout et sont adjacents dans .
Un ensemble couvrant d'un graphe est un ensemble de sommets tel que toute arête de a au moins une extrémité dans . Le nombre de sommets d'un ensemble couvrant minimum (c'est-à-dire, un ensemble couvrant minimisant le nombre de sommets) de est appelé couverture minimale de et noté .
Soit un graphe et un ensemble de sommets de . On dénote par le graphe sur les sommets avec comme arêtes et .
Par complexité (en temps) d'un algorithme , on entend le nombre d'opérations élémentaires nécessaires à l'exécution de dans le pire des cas.
Lorsque la complexité en temps dépend d'un ou plusieurs paramètres , on dit qu'elle est en s'il existe une constante telle que, pour toutes les valeurs de , suffisamment grandes (c'est-à-dire, plus grandes qu'un certain seuil), la complexité est au plus . La complexité est dite linéaire si .
Dans tout l'énoncé (sauf dans la partie II où on travaille sur des arbres et dans la partie III où on ne s'intéresse pas à la complexité précise des algorithmes), on fera l'hypothèse que les graphes sont encodés par leur matrice d'adjacence.

Partie I

Un graphe est complet si tous les sommets sont deux à deux adjacents. On dénote par

le graphe complet sur

sommets

Un ensemble indépendant d'un graphe est un ensemble de sommets du graphe dont les sommets sont deux à deux non-adjacents. On note

le nombre maximum de sommets d'un ensemble indépendant de

. Un couplage est un ensemble d'arêtes deux à deux disjointes, c'est à dire ne partageant aucun sommet. Le nombre maximum d'arêtes dans un couplage de

est noté

Un graphe est biparti si ses sommets peuvent être partitionnés en deux ensembles indépendants. Il est biparti complet s'il admet une partition en deux ensembles indépendants telle que chaque sommet d'une partie est adjacent à chaque sommet de l'autre partie. Étant donné deux entiers naturels

, on dénote par

le graphe biparti complet dont les parties de la partition en deux ensembles indépendants ont respectivement

sommets (disons, les sommets étant numérotés de 1 à

dans la première partie et de

dans la deuxième).

On dénote par

le graphe chemin sur

sommets, c'est-à-dire le graphe dont les sommets sont

et les arêtes

. Un graphe cycle est le graphe obtenu en ajoutant une arête entre les deux extrémités d'un graphe chemin. On dénote par

le graphe cycle sur

sommets.

Question I.1. Donner les valeurs de

pour le graphe

représenté cidessous. Justifier.

Question I.2. Donner la valeur de

pour tous entiers naturels non nuls

. Justifier soigneusement les réponses.

Question I.3. Montrer que pour tout graphe

Question I.4. Montrer que pour tout graphe

Aucun algorithme polynomial n'est connu pour calculer un ensemble couvrant minimum d'un graphe. Dans la question suivante, on demande un algorithme exponentiel.

Question I.5. Donner une description à haut niveau (sans détailler les lignes de pseudocode) d'un algorithme calculant un ensemble couvrant minimum d'un graphe

en temps

Partie II

Un arbre est un graphe connexe sans cycle. Un sommet de degré

d'un arbre est appelé une feuille. Dans cette partie, on va développer deux algorithmes efficaces pour calculer un ensemble couvrant minimum d'un arbre.

Dans cette partie, contrairement au reste du sujet, les arbres ne sont pas représentés par leur matrice d'adjacence mais par un tableau

dont les éléments sont des ensembles de sommets : pour chaque sommet

(où

est le nombre de sommets de l'arbre),

est une représentation de l'ensemble des sommets adjacents à

. On supposera que la structure de données utilisée pour représenter l'ensemble

permet en temps

les opérations suivantes : renvoyer le nombre d'éléments de l'ensemble; rechercher si un élément donné appartient à l'ensemble; ajouter un nouvel élément à l'ensemble ; retirer un élément existant de l'ensemble. Par exemple, voici un arbre sur les sommets

et sa représentation sous forme de tableau dont les éléments sont les ensembles de sommets adjacents :

Question II.1. Soient

un arbre et

une arête de

telle que

est une feuille de

. Montrer qu'il existe un ensemble couvrant minimum de

qui contient le sommet

, mais pas

Question II.2. En utilisant la question précédente, proposer un algorithme (en pseudo-code) qui reçoit un arbre

en entrée, et renvoie un ensemble couvrant minimum de

, en enlevant progressivement des arêtes à l'arbre. La complexité de cet algorithme doit être linéaire en le nombre

de sommets de l'arbre. Justifier de la complexité de l'algorithme.

Question II.3. Proposer un autre algorithme (en pseudo-code) qui renvoie le nombre de sommets d'un ensemble couvrant minimum d'un arbre, cette fois basé sur la programmation dynamique. On pourra commencer par enraciner l'arbre, c'est-à-dire choisir un sommet arbitraire qui jouera le rôle de racine de l'arbre. Pour chaque sommet

, on note

le sous-arbre de

enraciné en

; pour calculer le résultat final, l'algorithme devra d'abord calculer en programmation dynamique pour chaque

les trois valeurs suivantes :

nombre de sommets d'un ensemble couvrant minimum de contenant ;
nombre de sommets d'un ensemble couvrant minimum de ne contenant pas ;
nombre de sommets d'un ensemble couvrant minimum de .

On ne demande pas la preuve de la correction, mais il faut donner et prouver sa complexité en fonction du nombre

de sommets de l'arbre.

Partie III

Dans cette partie, plutôt que d'essayer de calculer un ensemble couvrant minimum, on va chercher à en calculer un dont le cardinal est proche du minimum.

Formalisons cette idée. Soit

un algorithme prenant un graphe en entrée et renvoyant un ensemble couvrant (pas forcément minimum). On note

le nombre de sommets de l'ensemble couvrant renvoyé par

appliqué à

. On note

le nombre de sommets d'un ensemble couvrant minimum de

. On dit que

est une

-approximation (pour un nombre réel

) si pour tout graphe

, on a :

Noter que les algorithmes que nous allons considérer n'ont pas une façon unique de s'exécuter sur un graphe donné. Typiquement, à la ligne 3 de l'algorithme Heuristique ci-dessous, il peut y avoir beaucoup de façon différentes de choisir le sommet

. Dans ce cas, on considère que

est le résultat de la pire exécution possible, c'est à dire celle renvoyant le plus grand ensemble couvrant parmi tous les ensembles couvrants qu'elle peut potentiellement renvoyer.

On considère un premier algorithme calculant un ensemble couvrant :

Algorithme 1 Heuristique( $G$ )
    $S \leftarrow \varnothing$
    while $G$ a des arêtes do
        Choisir un sommet $v$ de $G$ tel que $\mathrm{d}(v) \geqslant 1$
        $S \leftarrow S \cup\{v\}$
        $G \leftarrow G-\{v\}$
    return $S$

Question III.1. Montrer que l'ensemble

calculé par Heuristique est bien un ensemble couvrant.

Question III.2. Montrer que, pour tout entier

, il existe un graphe

sommets tel que

L'heuristique ci-dessus pouvant donner des résultats catastrophiques, on propose de l'améliorer en choisissant le sommet de degré maximum, donc celui couvrant le plus d'arêtes.

Algorithme 2 Glouton( $G$ )
    $S \leftarrow \varnothing$
    while $G$ a des arêtes do
        Choisir un sommet $v$ de degré maximum dans $G$
        $S \leftarrow S \cup\{v\}$
        $G \leftarrow G-\{v\}$
    return $S$

Glouton renvoie un ensemble couvrant pour les mêmes raisons que Heuristique.
On va définir une série de graphes bipartis

avec bipartition

comme suit.

est un ensemble de

sommets.

est partitionné en

sous-ensembles

ayant les propriétés suivantes pour

:
(i)

,
(ii) chaque sommet de

a exactement

voisins dans

,
(iii) deux sommets de

n'ont pas de voisins communs dans

Question III.3. Dessiner (une réalisation possible de)

et donner les valeurs de OPT(

) et de Glouton

. On ne demande pas de justifier.

Question III.4. En utilisant la construction ci-dessus, montrer que pour toute constante

, Glouton n'est pas une

-approximation.

Ainsi, Glouton ne donne pas non plus une bonne approximation. On va maintenant considérer l'algorithme suivant.

Algorithme 3 Approx $(G)$
    $S \leftarrow \varnothing$
    while $G$ a des arêtes do
        Choisir une arête $\{u, v\}$ de $G$
        $S \leftarrow(S \cup\{u\}) \cup\{v\}$
        $G \leftarrow(G-\{u\})-\{v\}$
    return $S$

Question III.5. Montrer que Approx renvoie un ensemble couvrant, en s'appuyant sur la question I.3.

Question III.6. Montrer que Approx est une 2-approximation.

Question III.7. Donner une suite infinie de graphes justifiant que, pour tout

, Approx n'est pas une

-approximation.

Partie IV

Dans cette partie, on cherche à répondre à la question suivante : Étant donné un graphe

et un entier

, est-ce que

? On rappelle que

est représenté par sa matrice d'adjacence.

Let but est de trouver un algorithme qui, étant donné un graphe

et un entier

, décide si

en temps

où

est une fonction (arbitraire, potentiellement exponentielle en son argument) et

une constante. Un algorithme avec une telle complexité est dit FPT pour fixed-parameter tractable ou tractable à paramètre fixé.

On va commencer modestement. Noter que l'algorithme demandé à la question ci-dessous n'est pas FPT.

Question IV.1. Donner une description à haut niveau (sans détailler les lignes de pseudocode) d'un algorithme qui, étant donné un graphe

et un entier

, décide si

en temps

Le reste de cette partie est dédié à la conception de notre premier algorithme FPT.

Question IV.2. Soit

un graphe et

. Montrer l'équivalence suivante :

Question IV.3. En s'aidant de la question précédente, donner un algorithme récursif (en pseudo-code) qui, étant donné un graphe

et un entier

, décide si

en temps

. Justifier la correction et la complexité de l'algorithme. On rappelle qu'avec la représentation en matrice d'adjacence, il est possible de supprimer l'ensemble des arêtes dont un sommet

est une extrémité en

On va maintenant légèrement modifier l'algorithme de la question précédente pour améliorer sa complexité.

Question IV.4. Donner une description précise des graphes de degré maximum 2. En déduire une description à haut niveau (sans détailler les lignes de pseudo-code) d'un algorithme en

pour décider si un graphe de degré maximum 2 a un ensemble couvrant avec au plus

sommets.

On rappelle que, étant donné un sommet

est l'ensemble des voisins de

et on définit

, le voisinage fermé de

Question IV.5. Soit

. Montrer que si

, alors

Question IV.6. En s'aidant de la question précédente, donner un algorithme récursif (en pseudo-code) qui décide si

en temps

. Justifier la correction et la complexité de l'algorithme. On utilisera le fait que la fonction

définie récursivement comme suit :

satisfait

Partic V

Comme dans la partie précédente, on cherche à répondre à la question suivante : Étant donné un graphe

et un entier

, est-ce que

On va s'intéresser à la notion de noyau. On dit que le problème de l'ensemble couvrant a un noyau de taille

(pour une certaine fonction croissante

) s'il existe un algorithme qui étant donné une instance (

) renvoie en temps polynomial (en

) une instance (

) tel que :
(i)

si et seulement si

,
(ii) si

, alors

et
(iii)

Question V.1. Montrer que si le problème de l'ensemble couvrant a un noyau de taille

, alors il existe un polynôme

tel qu'on peut décider si

en temps

Le reste de la partie est dédié à la conception d'un algorithme montrant que le problème de l'ensemble couvrant a un noyau de taille

Question V.2. Montrer que si un sommet

a degré 0 , alors

si et seulement si

Question V.3. Montrer que si un sommet

a degré au moins

, alors

si et seulement si

On considère maintenant l'algorithme qui, étant donné (

), applique les deux règles suivantes (dans n'importe quel ordre) tant que c'est possible. On note (

) le couple obtenu.

Règle 1 : si un sommet

a degré 0 , supprimer

.
Règle 2 : si un sommet

a degré au moins

, supprimer

, et diminuer

de 1 .
On remarque à l'aide des deux questions précédentes que

si et seulement si

Question V.4. Donner la complexité de cet algorithme en fonction de

(on rappelle que

est représenté par sa matrice d'adjacence).

Question V.5. Montrer que pour tout sommet

, on a dans

. En déduire que si

, alors

Question V.6. Conclure que le problème de l'ensemble couvrant a un noyau de taille

Partie VI

Soit

un graphe avec

. Un ensemble de sommets

peut être représenté par un vecteur

tel que, pour

On introduit une variable

pour chaque sommet de

. Observer que les ensembles couvrant de

correspondent précisément aux solutions du système d'équations suivant :

Ainsi, une solution minimisant

correspond à un ensemble couvrant minimum. Pour un graphe

donné, on nomme

(pour optimisation linéaire en nombre entier pour ensemble couvrant) le système d'équations (1) associé à

Question VI.1. Écrire le système d'équations OLNEEC(

) pour le graphe ci-dessous.

En relaxant la contrainte

par

, on obtient le système d'équations suivant nommé

(pour optimisation linéaire pour ensemble couvrant) :

On peut considérer que

(par exemple) correspond à mettre

du sommet

dans la solution. Une solution à ce système d'équations s'appelle un ensemble couvrant fractionnaire de

et sa taille vaut

. Une solution minimisant

est un ensemble couvrant fractionnaire minimum de

, et sa taille est noté

. Il est clair que pour tout graphe

Question VI.2. Parmi les vecteurs (

) suivants, dites lesquels sont des ensembles couvrants fractionnaires du graphe de la question VI. 1 et lesquels ne le sont pas. Donner leur taille quand ils le sont, et expliquer précisément la raison quand ils ne le sont pas.

Question VI.3. Montrer que pour tout graphe

, on a

. En déduire qu'il n'existe pas de constante

telle que

pour tout graphe

Soit

un graphe. Soit

un ensemble couvrant fractionnaire minimum de

. On partitionne les sommets de

de la façon suivante :

Question VI.4. Montrer que

est un ensemble indépendant (c'est à dire qu'aucune arête n'a ses deux extrémités dans

), et qu'il n'y a pas d'arête ayant une extrémité dans

et l'autre dans

Question VI.5. Montrer que

est un ensemble couvrant de

et que

. On admettra qu'il existe un algorithme en temps polynomial permettant de trouver un ensemble couvrant fractionnaire minimum. En déduire un algorithme polynomial qui donne une 2approximation pour le problème de l'ensemble couvrant minimum.

Le but des 3 prochaines questions est de montrer qu'il existe un ensemble couvrant minimum inclus dans

. Soit

un ensemble couvrant minimum de

, et soit

Question VI.6. Montrer que

est un ensemble couvrant de

.
On va perturber la solution

comme suit. On pose

et pour tout

, on définit :

Question VI.7. Montrer que

est un ensemble couvrant fractionnaire de

Question VI.8. Montrer que

est un ensemble couvrant minimum de

.
On va maintenant étudier l'algorithme suivant pour déterminer, étant donné un graphe

et un entier

, si

Algorithme 4 OLNoyau $(G, k)$
    Calculer un ensemble couvrant fractionnaire minimum $\left(x_{v}\right)_{v \in \mathrm{~V}(G)}$ à l'aide d'un algorithme
    en temps polynomial.
    Définir les ensembles $V_{0}, V_{\frac{1}{2}}$ et $V_{1}$ comme précédemment.
    if $\sum_{v \in \mathrm{~V}(G)} x_{v}>k$ then return NON
    if $\left|V_{\frac{1}{2}}\right|>2 k$ then return NON
    Résoudre l'instance ( $G-V_{0}-V_{1}, k-\left|V_{1}\right|$ ) en utilisant un algorithme par force brute.

Question VI.9. Montrer que si l'algorithme renvoie NON aux lignes 3 ou 4 , alors

Question VI.10. Montrer que

si et seulement si

. Conclure que le problème de l'ensemble couvrant a un noyau de taille

ENS Informatique Fondamentale (Maths Info) MP MPI 2024

ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2024

Couverture minimale d'un graphe

Le sujet comporte 12 pages, numérotées de 1 à 12.

Début de l'épreuve.

Notations et définitions

Partie I

Partie II

Partie III

Partie IV

Partic V

Partie VI

Fin du sujet.