The first part of the talk focuses on algorithms for Max 2-CSP. A new lower bound for the algorithm by Scott and Sorkin (2007) shows that the existing running time analysis is tight. The lower bound seems to apply to a broad class of branching algorithms, but can be overcome by exploiting global properties of an instance. In particular, the running time upper bound has been improved (Gaspers, Sorkin, 2015) by using graph separators to guide the branching.

The second part of the talk discusses the time complexity of some enumeration problems. It surveys results for enumerating extremal vertex sets in graphs and presents new results for the number of minimal separators in graphs (Gaspers, Mackenzie, 2015) and the number of minimal transversals of rank-k hypergraphs (Cochefert, Couturier, Gaspers, Kratsch, 2015).