A faster polynomial-space algorithm for Max 2-CSP

作者：

Highlights：

• 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/4 to n/5+o(n).

• Provides evidence of the likely limits of this approach.

摘要

•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/4 to n/5+o(n).•Provides evidence of the likely limits of this approach.

论文关键词：Max 2-CSP,Deletion-reduction depth,Deletion depth

论文评审过程：Received 26 April 2014, Revised 26 November 2014, Accepted 30 November 2015, Available online 10 December 2015, Version of Record 29 December 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.11.013