Skip to content

Latest commit

 

History

History
70 lines (47 loc) · 3.1 KB

kernighan_lin_alg.md

File metadata and controls

70 lines (47 loc) · 3.1 KB

Kernighan Lin Algorithm

General

Kernighan Lin is a heuristic algorithm for finding partitions of graphs, which is mainly used for bipartite a graph

kernighan_lin_alg_sample

Algorithm basic

kernighan_lin_vertex_switch

For given graph be divided into two sets of vertex v1 and v2, we want to find 2 vertex belonging to different set, by switch them we could optimize cut result.

Let's say vertex a belonging to V1 and vertex b belonging to V2. For current division, cut size is 5, by moving a to V2 and b to V1, we got worse cut size 6 which could not help to gain better cut.

Basic algorithm

kernighan_lin_basic

Step1: calculate a sequence of gains

kernighan_lin_step1

Step2: accumulate gains

kernighan_lin_step2

Key points

  1. Comments about implementation
        min_id = -1
        self.swaps = []
        while self.get_nominal_cut_size() < nominal_cut_size:
            nominal_cut_size = self.get_nominal_cut_size()
            min_cost = float("Inf")
            for i in range(cut_size):
                # Signle swap will calculate max gain for each combination from group_a_unchosen and group_b_unchosen
                self.single_swaps()
                cost = self.get_nominal_cut_size()
                if cost < min_cost:
                    min_cost = cost
                    min_id = i
            
            # Undo swaps done after the minimum was reached
            for i in range(min_id+1, cut_size):
                vertice_b, vertice_a = self.swaps[i]
                self.do_swap((vertice_a, vertice_b))

            # Reset unchosen group based on adjust items.
            # When there is any gain, this algorithm won't stop, so need huristic to speed up(inside single_swap)
            self.group_a_unchosen, self.group_b_unchosen = \
            self.graph.get_groups()

For more context could go to code here

The major issue for kernighan_lin is the cost of the algorithm is too high, which takes O(V^2*n)

  1. Kernighan Lin alg is sensitive to initial partition's result, with good initial result could convergent �quickly. But in real case its hard to estimate that.

Reference