NFL theorem is unusable on structured classes of problems

Nowadays, in the heuristic and metaheuristics community, there is a schism between researchers who say: "we proved experimentally that a given heuristic provides good results on a given problem and we can guess that it is enough general to be applied for other problems", and those who claim: "the No Free Lunch theorem (NFL) proves that there exists no absolute efficient heuristic". The formers suspect the existence of a structure in the solved problem and that structure can occur in other problems. The latters fear that heuristics are especially adapted for the testbed problem this paper addresses structural aspect of combinatorial optimization problems. In a first time, we recall some related works which provide a frame to our work. Particularly, we recall the existence of deceptive problems which are proved to be hard to optimize, the definitions of the five scenarios of knowledge in optimization problem, and some works which already discuss the reach of NFL theorem. In the next part, we give a short overview of how NFL works and discuss its significance with regards to complexity. This leads to the observation that the notion of structure of optimization problems is missing in NFL use. Then, we prove that k-coloring problems respect such a notion of structure, for any k. In the last part we discuss the relevance of our work on four points: the polynomial reduction of NP-complete problems and structure preservation, the connection between our work and the study which squeeze NFL using neighborhood search operators, the position of our study on the five scenarios of knowledge, and finally the difference between metaheuristics and heuristics.