CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
evil999man
evil999man

Reputation: 212

Partially coloring a graph with 1 color

I just started reading graph theory and was reading about graph coloring. This problem popped in my mind:

We have to color our undirected graph(not completely) with only 1 color so that number of colored nodes are maximized. We need to find this maximum number. I was able to formulate an approach for non cyclic graphs :

My approach : First we divide graph into isolated components and do this for each component. We make a dfs tree and make 2 dp arrays while traversing it so that root comes last :

dp[0][u]=sum(dp[1][visited children])

dp[1][u]=sum(dp[0][visited children])

ans=max(dp[1][root],dp[0][root])

dp[0][i] , dp[1][i] are initialized to 0,1 respectively.

Here 0 signifies uncolored and 1 signifies colored.

But this does not work for cyclic graphs as I have assumed that no visited children are connected.

Can someone guide me in the right direction on how to solve this problem for cyclic graphs(not by brute force)? Is it possible to modify my approach or do we need to come up with a different approach? Would a greedy approach like coloring a nodes with least edges work?

Upvotes: 2

Views: 535

Answers (1)

amit
amit

Reputation: 178521

This problem is NP-Hard as well, and is known as maximum independent set problem.

A set S<=V is said to be Independent Set in a graph if for each two vertices u,v in S, there is no edge (u,v).

The maximum size of S (which is the number you are seeking) is called the independence number of the graph, and unfortunately finding it is NP-Hard.

So, unless P=NP, your algorithm fails for general purposes graphs.

Proving it is fairly simple, given a graph G=(V,E), create the complementary graph G'=(V,E') where (u,v) is in E' if and only if (u,v) is NOT in E.

Now, given a graph G, there is a clique of size k if and only if there is an independent set of size k in G', using the same vertices (since if (u,v) are two vertices the independent set, there is no edge (u,v) in E', and by definition there is an edge in E. Repeat for all vertices in the independent set, and you got a clique in G).

Since clique problem is NP-Hard, this makes this one such as well.

Upvotes: 5

Related Questions