Develope lowerbound algorithm

[TijnLogtens]

• Explain why it works
• Attempt to code it

[LauraIst]

My plan:

1. Use Bron-Kerbosch algorithm for finding all maximal cliques in an undirected graph (maximal means in this case any clique which cannot be expanded by adding more adjacent vertices, because any extra vertices would not be connected to all the ones in the clique).
2. Figure out which of the maximal cliques is the largest.

Bron-Kerbosch algorithm for finding maximal cliques in an undirected graph: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

Video explaining Bron-Kerbosch algorithm (without pivot and with pivot), step by step: https://www.youtube.com/watch?v=132XR-RLNoY

I think we can program the basic version now and in later phases when we need to optimise the algorithms, we can consider the improved versions. Some of them might also work better for some graphs than for others.

[LauraIst]

Possible future improvements:

• modifying Bron-Kerbosch to be with pivot, and possibly with sorting etc
• figuring out how to find the independence number of a graph and complementing our lower bound with that (see http://opencarts.org/sachlaptrinh/pdf/16446.pdf ) for discussion on lower bounds, claiming that the higher of maximum clique or independence number will be the lower bound
• more reading (compare different approaches to see which one is the most efficient): https://ac.els-cdn.com/0166218X8390015X/1-s2.0-0166218X8390015X-main.pdf?_tid=10eaf2af-3a5c-47b6-95d2-85f212232ab5&acdnat=1539630989_68d145265e8caafdfa85f5d2c2dd9790
• Hoffman's bound based on eigenvalues