Algorithme de Kernighan-Lin

L'algorithme prend en entrée un graphe non-orienté G = (V, E), défini par l'ensemble de nœuds V, l'ensemble de liens E et potentiellement les coûts des liens de E. L'objectif est de réaliser une partition de l'ensemble V en deux ensembles disjoints A et B de tailles proches ou égales, de manière à minimiser la somme T des poids du sous-ensemble de liens allant de A à B. Si le graphe est non-pondéré, l'algorithme cherche à minimiser le nombre de liens allant de A à B, ce qui est équivalent à assigner un poids unitaire à tous les liens.

L'algorithme tient à jour une partition et l'améliore à chaque itération en utilisant une méthode gloutonne. Le principe est d'apparier des nœuds de A à des nœuds de B, de manière qu'intervertir les ensembles auxquels appartiennent les nœuds appariés améliore la qualité du partitionnement. Après association des nœuds, l'algorithme réalise un sous-ensemble des paires choisies pour obtenir la valeur minimum de T. Pour un graphe à n nœuds, chaque itération de l'algorithme est réalisée en O(n² log n).

Plus précisément, pour tout ${\displaystyle a\in A}$, on appelle ${\displaystyle I_{a}}$ le coût interne de a, c'est-à-dire la somme des coûts des liens entre a et les autres nœuds de A et ${\displaystyle E_{a}}$ le coût externe de a, c'est-à-dire la somme des coûts des liens entre a et les nœuds de B. On définit de manière analogue ${\displaystyle I_{b}}$ et ${\displaystyle E_{b}}$ pour tout ${\displaystyle b\in B}$. On pose

${\displaystyle D_{x}=E_{x}-I_{x}}$

la différence entre les coûts externes et internes de x. Si a et b sont intervertis, alors la réduction de coût est:

${\displaystyle T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}}$

où ${\displaystyle c_{a,b}}$ est le coût d'un potentiel lien entre a et b.

L'algorithme cherche à trouver une suite optimale d'interversions entre éléments de ${\displaystyle A}$ et de ${\displaystyle B}$ qui maximise ${\displaystyle T_{old}-T_{new}}$ puis met à jour le partitionnement du graphe en A et B en réalisant effectivement ces opérations[1].

Source[1]

fonction Kernighan-Lin(G(V, E))
    déterminer une partition initiale des nœuds équilibrée entre les ensembles A et B
    faire
        calculer les valeurs D pour tout a dans A et tout b dans B
        soient L_g, L_a, et L_b des listes vides 
        pour n := 1 à |V| faire
            trouver a dans A et b dans B tels que g = D[a] + D[b] − 2×c(a, b) est maximum
            on ne considère plus a et b dans la suite de cette itération
            ajouter g à L_g, a à L_a et b à L_b
            mettre à jour les valeurs D pour les éléments de A = A \ a et B = B \ b
        fin pour
        trouver k qui maximise g_max, la somme des L_g[1], ..., L_g[k]
        si g_max > 0 alors
            Mettre L_a[1], L_a[2], ..., L_a[k] dans B et L_b[1], L_b[2], ..., L_b[k] dans A
    jusqu'à (g_max ≤ 0)
    renvoyer A,B

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kernighan–Lin algorithm » (voir la liste des auteurs).