Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems

In the design of branch-and-bound methods for NP-hard combinatorial optimization problems, dominance conditions have always been applied. In this work we show how the use of dominance conditions within search tree algorithms can lead to non trivial worst-case upper time bounds for the considered algorithms on bounded combinatorial optimization problems. We consider here the MIN 3-SET COVERING and the max cut problem with maximum degree three. Combining dominance conditions and intuitive combinatorial arguments, we derive two exact algorithms with worst-case complexity bounded above by O * (1.4492 n ) and O * (1.2920 n ) for the former and the latter problem, respectively, where notation O * (·) takes into account only exponential factors, and n is the number of subsets for MIN 3-SET COVERING and the number of vertices of the input-graph for max cut.ou