Toby Walsh

To appear at Computational Symposium on Graph Coloring and Generalizations (COLOR02), Ithaca, NY, 7-8 September 2002


Like the well known 2+$p$-{\sc Sat} problem, the 2+$p$-{\sc Col} problem smoothly interpolates between P and NP by mixing together the polynomial 2-coloring problem and the NP-complete 3-coloring problem. As with 2+$p$-{\sc Sat}, the polynomial subproblem can dominate the problem's solubility and the search complexity. The 2+p-COL problem class has, however, at least one very significant difference over the 2+p-SAT problem class. 2-SAT and 3-SAT (and thus 2+p-SAT) have sharp transitions in satisfiability. On the other hand, 3-COL has a sharp transition in solubility but 2-COL has a smooth transition. In the 2+p-COL problem, we therefore observe phase transition behavior in which there appear to be both smooth and sharp regions. We also show how this problem class can help to understand algorithm behavior by considering search trajectories through the phase space.

Server START Conference Manager
Update Time 23 Jul 2002 at 13:35:57
Maintainer trick@cmu.edu.
Start Conference Manager
Conference Systems