Graph Problems

Question 1

What is the Clique problem?

Answer 1

Where an undirected graph and a non negative integer k is given, and the algorithm returns yes if the graph contains a clique of size k. (A set of nodes so that every node is connected to every other node) ; no otherwise

Question 2

What is the time complexity for the clique problem with a graph with n nodes, if a brute force algorithm is used

Answer 2

We can check all potential cliques of size up to k in time O(n^(k+2) k^2).

For k=O(1) we have O( n^(k+2) )

Question 3

What is a subset of the clique problem that can be solved in polynomial time?

Answer 3

Planar graphs. This is because they cannot have cliques of size 5 or larger.

Question 4

What is the graph colouring problem?

Answer 4

Where an undirected graph and a non negative integer k is given, and the algorithm returns yes is the graph can be coloured with k colours so that no pair of adjacent nodes have the same colour; no otherwise

Question 5

What is a bi-partite graph?

Answer 5

A graph were there are two sets of nodes, and none of the nodes in the same set are directly connected.

Question 6

What cases of the graph colouring problem are in P?

Answer 6

Where k is not equal to 3.