New exact algorithms for the 2-constraint satisfaction problem

详细信息    查看全文

• 作者：Alexander Golovnev^a ; ¹ ; Konstantin Kutzkov^b ;
• 关键词：Exact exponential time algorithms ; Constraint satisfaction ; Maximum satisfiability
• 刊名：Theoretical Computer Science
• 出版年：20 March, 2014
• 年：2014
• 卷：526
• 期：Complete
• 页码：18-27
• 全文大小：288 K

文摘

Many optimization problems can be phrased in terms of constraint satisfaction. In particular MAX-2-SAT and MAX-2-CSP are known to generalize many hard combinatorial problems on graphs. Algorithms solving the problem exactly have been designed but the running time is improved over trivial brute-force solutions only for very sparse instances. Despite many efforts, the only known algorithm solving MAX-2-CSP over n variables in less than steps uses exponential space.

Several authors have designed algorithms with running time where is a slowly growing function and d is the average variable degree of the input formula. The current best known algorithm for MAX-2-CSP runs in time and polynomial space. In this paper we continue this line of research and design new algorithms for the MAX-2-SAT and MAX-2-CSP problems.

First, we present a general technique for obtaining new bounds on the running time of a simple algorithm for MAX-2-CSP analyzed with respect to the number of vertices from algorithms that are analyzed with respect to the number of constraints. The best known bound for the problem is improved to for . We further improve the bound for MAX-2-SAT, in particular for we achieve .

As a second result we present an algorithm with asymptotically better running time for the case when the input instance is not very sparse. Building on recent work of Feige and Kogan we derive an upper bound on the size of a vertex separator for graphs in terms of the average degree of the graph. We then design a simple algorithm solving MAX-2-CSP in time , for some and .