Question

I saw other student's Q&A that expert answered. but I can't understand this problem.

please solve this problem.

24. Write an algorithm for the 2-coloring problem whose time complexity is not worst-case exponential in n.

Answer 1

Graph coloring problem is NP-Hard. But 2-coloring problem can be solved easily. So, firstly pick any vertex v mark its color to red (lets say) and then mark its all neighbours with the second color (blue lts say). Continue doing this till all the vertices are colored. Now, we check if there is any bad edge (i.e. both the nodes connected to that particular edge have the same color) then the graph cannot be colored with 2 colors else it is possible. This property will hold only for bipartite graphs.

So the algorithm that we are going to use for this is BFS for the graph. Here's the pseudo code

BFS(s):

mark s as visited and push it into the queue

cnt = 0

while(queue is not empty):

v<- queue.remove()

if cnt == 0

color[v] = 1

else

color[v] = 0

for all unvisited neighbours w of v:

mark w as visited

queue.insert(w)

if color[v] == 0:

color[w] = 1

else

color[w] = 0

This was just the BFS part now just check every edge and check if their adjacent nodes have same colors or not