The Probabilistic Minimum Coloring Problem (Extended Abstract)
Cécile Murat · 2003
We study the probabilistic coloring problem (pcolor) un- der a modification strategy consisting, given an a priori solution C ,o f removing the absent vertices from C. We compute the objective function associated with this strategy, we give bounds on its value, we charac- terize the complexity of computing it and the one of computing the optimal solution associated with. We show that pcolor is NP-hard and design a polynomial time approximation algorithm achieving non-trivial approximation ratio. We then show that probabilistic coloring remains NP-hard even in bipartite graphs and that the unique 2-coloring in such graphs is a constant ratio approximation. We finally prove that pcolor is polynomial when dealing with complements of bipartite graphs.