Bron-Kerbosch's Algorithm to find maximal clique in undirected graph

user_6423160 0
Viewed 300

I'm trying to understand Bron-Kerbosch's algorithm (with pivoting) to find maximal cliques in an undirected graph. I have some questions:

  1. Is there any criteria for picking a pivot vertex? I have seen some implementations that picked the vertex with the most neighbours for optimization while others simply picked the first vertex in prospective vertices as pivot vertex. How does picking the vertex with the most neighbours help in optimization?

  2. By picking a pivot vertex, it helps to narrow down the list of prospective vertices to check during the search for cliques, thereby reducing the number of recursive calls made. The algorithm without pivoting checks for all vertices to determine whether it forms a clique while the one with pivoting only checks P \ N(u) for vertices that must be included to form a maximal clique. This way, if a non-maximal clique is found, algorithm can backtrack immediately instead of performing recursion unnecessarily on vertices that will never form a maximal clique. Is my understanding correct?

Pseudocode from Wikipedia:

*Without Pivoting
algorithm BronKerbosch1(R, P, X) is
    if P and X are both empty then
        report R as a maximal clique
    for each vertex v in P do
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

*With Pivoting
algorithm BronKerbosch2(R, P, X) is
    if P and X are both empty then
        report R as a maximal clique
    choose a pivot vertex u in P ⋃ X
    for each vertex v in P \ N(u) do
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}
graph algorithm python
1 Answers

  1. There's a trade-off between how long you spend choosing the pivot and how long you spend exploring the resulting tree. Hypothetically we could build an oracle to give us the very best pivot choices, but it probably would take more execution time than Bron--Kerbosch itself. Conversely, choosing the first vertex is very fast but may result in a much larger tree than necessary.

    Good branching strategies are a perennial topic of academic interest given the impossibility of attaining perfection. One of the first strategies discovered is choosing the pivot to minimize the number of branches. This tends to work better than all simpler strategies. Here that means minimizing the size of P ∖ N(u), for which maximizing the size of N(u) seems like a decent proxy.

  2. Essentially, yes. Without pivoting, even if we choose a vertex in N(u), we can still find a maximal clique at the end. The idea is that every maximal clique includes either u or a vertex that is neither u nor one of u's neighbors, so we commit to the identity of that vertex early (in line with the philosophy of moving forced decisions toward the root of search tree).

user_21446690
Related