Couverture par sous-graphes bipartis complets

En théorie des graphes, le problème de couverture minimum par sous-graphes bipartis complets (ou problème de couverture biclique) est un problème algorithmique qui consiste, étant donné un graphe, à trouver une famille minimale de sous-graphes bipartis complets couvrant ses arêtes^[1], c'est-à-dire telle que chaque arête du graphe d'origine apparaisse dans au moins un sous-graphe de la couverture.

Exemple de couverture d'un graphe biparti par quatre graphes bipartis complets (chaque couleur représente un sous-graphes).

Le problème de décision associé au problème d'optimisation de couverture par au plus ${\displaystyle k}$ sous-graphes bipartis complets est NP-complet, et ce même si l'on se restreint à la couverture de graphes bipartis^[2].

Couverture par sous-graphes bipartis complets

Définition

Une couverture par sous-graphes bipartis complets d'un graphe ${\displaystyle G=(V,E)}$ est un ensemble ${\displaystyle \lbrace G_{k}=(V_{k},E_{k})|1\leqslant k\leqslant n,V_{k}\subseteq V,E_{k}\subseteq E\rbrace }$ de sous-graphes bipartis complets de ${\displaystyle G}$ tel que pour toute arête ${\displaystyle e}$ de ${\displaystyle G}$, il existe un entier ${\displaystyle k\in [\![1,n]\!]}$ tel que ${\displaystyle e\in E_{k}}$ (ces sous-graphes ne sont pas nécessairement deux à deux disjoints).

Propriétés combinatoires

Nombre minimal de sous-graphes couvrants

Exemples de graphes à respectivement 4 et 5 sommets où l'égalité ${\displaystyle b(n)=b(G)}$ est réalisée. Chaque couleur indique un sous-graphe biclique.
On remarque que dans le graphe de gauche, les sous-graphes ne sont pas disjoints.

Étant donné un graphe ${\displaystyle G}$, on note ${\displaystyle b(G)}$ le nombre minimum de graphes bipartis complets couvrant les arêtes de ${\displaystyle G}$ (aussi appelé dimension bipartie). Pour un entier naturel ${\displaystyle n}$, si ${\displaystyle G}$ est un graphe à ${\displaystyle n}$ sommets, on a ${\displaystyle b(G)\leqslant n-1}$^[3], car on obtient une couverture à au plus ${\displaystyle n-1}$ sous-graphes bipartis complets en prenant les sous graphes étoiles^[4] de ${\displaystyle G}$.

On peut donc noter ${\displaystyle b(n)}$ la valeur maximale des ${\displaystyle b(G)}$, où ${\displaystyle G}$ est un graphe à ${\displaystyle n}$ sommets. Les ${\displaystyle 10}$ premières valeurs de ${\displaystyle b(n)}$ sont données par le tableau suivant (on observe bien que ${\displaystyle b(n)}$ est majoré par ${\displaystyle (n-1)}$ :

n	2	3	4	5	6	7	8	9	10
b(n)	1	2	2	3	4	5	5	6	7

On peut obtenir les premières valeurs de ${\displaystyle b(n)}$ en étudiant systématiquement les graphes à ${\displaystyle n}$ sommets.
Pour ${\displaystyle n}$ plus grand, on peut utiliser les propriétés suivantes :

• ${\displaystyle b(n)\leqslant b(n+1)\leqslant b(n)+1}$
• Si ${\displaystyle G}$ est un graphe possédant deux sous-graphes de sommets disjoints ${\displaystyle G_{1}}$ et ${\displaystyle G_{2}}$, reliés par au plus une arête, alors : ${\displaystyle b(G_{1})+b(G_{2})\leqslant b(G)}$
  • Si ${\displaystyle n_{1}+n_{2}=n}$, alors ${\displaystyle b(n_{1})+b(n_{2})\leqslant b(n)}$
  • En particulier, si pour un certain ${\displaystyle n\in \mathbb {N} }$ et ${\displaystyle a>0}$, ${\displaystyle b(n)=an}$, alors pour tout entier ${\displaystyle k}$, ${\displaystyle akn\leqslant b(kn)}$, et donc ${\displaystyle a\leqslant \lim _{n\to +\infty }{\frac {b(n)}{n}}}$. Ce comportement et les premières valeurs de ${\displaystyle b(n)}$ amènent à conjecturer que ${\displaystyle \lim _{n\to +\infty }{\frac {b(n)}{n}}=1}$, ce qui est en fait vrai.

Théorème^[3] — Pour un nombre entier naturel ${\displaystyle n}$, le nombre ${\displaystyle b(n)}$ est équivalent, lorsque ${\displaystyle n}$ tend vers ${\displaystyle +\infty }$, à ${\displaystyle n}$. Soit :

${\displaystyle b(n){\underset {n\to +\infty }{\sim }}n}$

Plus précisément, il a été démontré^[5] par Zsolt Tuza que l'on avait : ${\displaystyle b(n)\leqslant n-[\log _{2}(n)]+1}$.

Nombre minimal de sommets couverts

Pour un graphe ${\displaystyle G}$, on note ${\displaystyle \beta (G)}$ la valeur minimale de ${\displaystyle \sum _{i=1}^{m}|V_{k}|}$, où ${\displaystyle G_{1}=(E_{1},V_{1}),\ldots ,G_{m}=(E_{m},V_{m})}$ est une couverture biclique de ${\displaystyle G}$. En d'autres termes, ${\displaystyle \beta (G)}$ désigne le nombre minimal de sommets d'une couverture biclique de ${\displaystyle G}$, comptés avec multiplicités. Si ${\displaystyle n}$ est un entier fixé, on note ${\displaystyle \beta (n)}$ la valeur maximale de ${\displaystyle \beta (G)}$ pour les graphes à ${\displaystyle n}$ sommets. Zsolt Tuza a donné une minoration optimale^[5] de la valeur de ${\displaystyle \beta (n)}$ :

Théorème — Il existe une constante ${\displaystyle c>0}$ telle que pour tout entier ${\displaystyle n}$ suffisamment grand :

${\displaystyle c{\frac {n^{2}}{\log(n)}}<\beta (n)}$

Et cette minoration est optimale, à la constante ${\displaystyle c}$ près.

Partition en graphes bipartis complets

Définition

Une partition par sous-graphes bipartis complets est une couverture par sous-graphes bipartis complets où l'on impose que tous les sous-graphes soient disjoints.

Propriétés combinatoires

Théorème de Graham-Pollak

Théorème de Graham-Pollak — Un graphe complet à ${\displaystyle n}$ sommets ne peut être partitionné en moins de ${\displaystyle n-1}$ graphes bipartis complets.

Nombre minimal de sommets couverts

De la même manière que pour la couverture biclique, on peut définir ${\displaystyle \alpha (G)}$ le nombre minimal de sommets d'une partition biclique d'un graphe ${\displaystyle G}$, toujours comptés avec multiplicités. Pour un entier ${\displaystyle n}$ fixé, on note ${\displaystyle \alpha (n)}$ la valeur maximale de ${\displaystyle \alpha (G)}$ pour les graphes à ${\displaystyle n}$ sommets. Un premier résultat démontré par Fan Chung, Paul Erdős et J. Spencer donne un encadrement des valeurs de ${\displaystyle \alpha (n)}$ et ${\displaystyle \beta (n)}$ :

Théorème^[1] — Pour tout réel ${\displaystyle \varepsilon >0}$ et pour tout entier ${\displaystyle n}$ suffisamment grand :

${\displaystyle (1-\varepsilon ){\frac {n^{2}}{2e\log(n)}}<\alpha (n)\leqslant \beta (n)<(1+\varepsilon ){\frac {n^{2}}{2\log(n)}}}$

Ce résultat montre en particulier que la minoration de ${\displaystyle \beta (n)}$ trouvée par Zsolt Tuza est bien optimale.
Il a ensuite été démontré par Paul Erdős et László Pyber^[6] qu'il existe une constante ${\displaystyle c}$ telle que pour tout entier ${\displaystyle n}$ suffisamment grand, tout graphe ${\displaystyle G=(V,E)}$ à ${\displaystyle n}$ sommets admet une partition biclique pour laquelle tout sommet de ${\displaystyle G}$ est contenu dans au plus ${\displaystyle c(n/\log(n))}$ sous-graphes de la partition.

Articles connexes

• Graphe biparti complet
• Théorème de Graham-Pollak
• Dimension bipartie
• Liste de problèmes NP-complets