A faster polynomial-space algorithm for Max 2-CSP

• New faster polynomial space algorithm for Max 2-CSP.
• Lower complexity both in terms of edges (the first improvement for 10 years) and in terms of average degree.
• Improves exponent in the cubic graph case from n/4n/4 to n/5+o(n)n/5+o(n).
• Provides evidence of the likely limits of this approach.

We give an algorithm for Max 2-CSP which runs in time O⋆(rm5.555) and uses polynomial space. This compares with the previous fastest published algorithm of Scott and Sorkin [15], which runs in time O⋆(r19m100)=O⋆(rm5.263).The algorithm uses the deletion-reduction depth of a graph; we also consider some of the properties of this parameter, and in particular derive a lower bound on the parameter for cubic graphs.