A recent line of research has been to speed up exponential-time algorithms (deterministic or randomized) for maximization problems such as Max 2-Sat and Max Cut. The fastest previous algorithms run in time Õ(2m/5) for a Max 2-Sat instance with m clauses, and Õ(2m/4) for a Max Cut instance with n vertices and m edges (by applying the Max 2-Sat algorithm to a transformation of the graph). In this paper, we work with a larger class of problems, “Max (r, 2)-CSP”. We give a deterministic algorithm which solves any m-constraint Max (r, 2)-CSP instance in time Õ(r19m/100) (i.e., Õ(rm/5.26···)) and space O(mn). In particular, in time Õ(219m/100) we can solve Max Cut, Max Dicut, Max 2-Lin, Max 2-Sat, Max-Ones-2-Sat, maximum independent set, and minimum dominating set, and in time Õ(k19m/100) we can solve Max k-Cut; weighted versions of any of these problems can be accommodated at no extra cost. The algorithm is relatively simple, using just two transformation rules and one splitting rule, and the analysis hinges on a small linear program.
By: Alexander D. Scott; Gregory B. Sorkin
Published in: RC23457 in 2004
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .