surajkvm007's blog

finding all the cliques in a graph

By surajkvm007, history, 8 years ago, In English

can anyone please provide me with a hint to solve this problem

basically we need to find all the cliques in the graph but in short time.

Update : I tried Bron-Kerbosch algorithm but it takes exponential time and the time limit for the problem is 1 sec with maximum of 128 vertices.

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it takes exponential time and in the problem the time limit is 1 sec with 128 vertices.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      Except you're allowed to terminate the algorithm once you find 1000 cliques. I already got accepted on this problem with the above algorithm, believe me, it's fine. If you're getting TLE you're doing something wrong, my implementation runs in 0.08s on the Kattis servers.

      EDIT: Additionally, you're not going to find subexponential algorithms for this problem, it's NP-Complete.

      EDIT2: iirc, you do need to implement the advanced techniques mentioned on the wiki (pivoting and vertex ordering).

      → Reply