Algorytm Kernighana-Lina – heurystyczny algorytm o złożoności obliczeniowej rozwiązywania problemu podziału grafu na 2 równe części. Może pracować na grafach o dodatnich, jak i ujemnych wagach krawędzi.
Opis Niech będzie grafem, gdzie to zbiór jego wierzchołków, a zbiór krawędzi. Algorytm próbuje znaleźć podział na dwa rozłączne, jednakowo liczne podzbiory i tak, by sumaryczna waga krawędzi między wierzchołkami z podzbioru i oznaczona przez była jak najmniejsza.
Niech będzie wewnętrznym kosztem , czyli sumą kosztów wszystkich krawędzi między i resztą wierzchołków z natomiast zewnętrznym kosztem czyli sumą kosztów krawędzi między i wierzchołkami z
Zdefiniujmy jako:
czyli różnicę między zewnętrznym i wewnętrznym kosztem W momencie wymiany i zysk wyraża się wyrażeniem:
gdzie jest kosztem krawędzi między i
Algorytm stara się znaleźć najkorzystniejszą sekwencję wymian wierzchołków między i przez maksymalizację funkcji celu określonej jako:
Należy pamiętać, że po wyborze optymalnych wierzchołków następuje ich zamiana, ale w kolejnej iteracji są one nie ruszane – rozpatruje się wierzchołków w każdym z podzbiorów, i tak dalej, aż nie pozostanie więcej wierzchołków do rozpatrzenia.