Problem Complexity: Constraint Tightness

• The chromatic number seems to be a critical threshold for problem complexity

• FP performs “well” when critically or slightly under-constrained

  • #colors equal to or slightly greater than chromatic number
  • FP usually achieves proper coloring when under-constrained

• FP performs “reasonably” & behaves well when over-constrained

  • #colors<chromatic number
  • reduces conflicts significantly below random level
  • doesn’t fall down & doesn’t blow up

• FP’s performance when loosely-constrained is counter-intuitive

  • performance is not as good as might be expected on easy problems