Computer Science – Data Structures and Algorithms
Scientific paper
2011-08-26
Computer Science
Data Structures and Algorithms
Working paper
Scientific paper
This article presents a parametric-complexity exact algorithm to solve the graph 3-COLORING problem. Its maximal complexity is controlled by the parameter {\alpha} which determines the running-time: O(n^f({\alpha})). The algorithm relies on the efficient search of "3-uncolorability witnesses" which, as it is shown here, is in NP.CoNP.P for any fixed {\alpha}, and in general for {\alpha} != f(input). The algorithm returns either a legal 3-coloring, a 3-uncolorability witness or alternatively "undetermined". Hence, it is not compulsory to trust neither the correctness of the algorithm itself nor the particular implementation used, in order to be convinced that the obtained solution is correct. In the "undetermined" case, it can be re-run with a higher {\alpha} until a solution is found, and so, a unique number {\alpha}(G) corresponds to each graph G. Here, it is proved, for any non-negative integer k, that the proportion of graphs such that {\alpha}(G)=k is greater than or equal to the proportion for {\alpha}(G)>k, hence the probability of {\alpha}(G)>k decreases, in the worst-case, at P({\alpha}(G)>k) <= 1/2^k+1 and thus lim k->inf P({\alpha(G)}<= k)=1. As a corollary, it is shown that as {\alpha}->inf (NP U CoNP) \ P -> {} and that P != NP implies {\alpha}(G) in [0,inf). Hence, 3-colorability restricted to {\alpha}(G) <= k is in P. Nevertheless, it remains unknown whether it is NP-complete for some finite k. Experimental analyses have been thoroughly performed. The algorithm has been tested on planar graphs, 4-regular planar graphs and Erdos-Renyi random graphs. The experimental results validate the algorithmic implementation and confirm the theoretical expected results.
No associations
LandOfFree
A parametric-complexity exact 3-COLORING Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A parametric-complexity exact 3-COLORING Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A parametric-complexity exact 3-COLORING Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-613840