A New Algorithm for Optimal 2-Constraint Satisfaction and Its .ppt

1、A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications,Ryan Williams Computer Science Department, Carnegie Mellon UniversityPresented by Mu-Fen Hsieh,MAX-CUT,Given a graph G = (V,E), positive integer N, is there a partition of V into disjoint sets S and T=V-S such that the number

2、 of the edges from E that have one endpoint in S and one endpoint in T is at least N? Proved to be NP-hard by reducing from MAX-2-SAT Karp, 1972 Can be solved in polynomial time if G is planar Hadlock, 1975, Orlova et al., 1972 Can be transformed to an instance of MAX-2-SAT in polynomial time,MAX 2-

3、Satisfiability,Given a set U of n variables, a collection C of m clauses over U such that each clause has |c| = 2, positive integer N |C|, is there a truth assignment for U that simultaneously satisfies at least N of the clauses in C? Garey et al., 1976 Solvable in polynomial time if N = |C| Even et

4、 al., 1976 Approximated in O(2-)n), O(2-)m) Dantsin et al.,2001 Previous best worst-case bound: O*(2m/5) Hirsch et al., 2003 This paper counts number of truth assignments that simultaneously satisfies exactly N of the clauses in C in O(m32n/3) time,Encode Max-Cut as Max-2-SAT,The size of the cut ass

5、ociated to the assignment = |E| - number of violated clauses,T,T,T,F,F,F,Split and list: split the set of n variables into k partitions of equal size, and list 2n/k variable assignments for each partition.,Set k=3, we get O(m32n/3),MAX-CUT,MAX-2-SAT,k-CLIQUE,Matrix Multiplication,Polynomial-time tra

6、nsformation,Split and list,Fast k-Clique Detecting and Counting,Locate 3-clique: given G = (V,E) with n = |V|, let A(G) be its adjacency matrix. tr(A(G)3) = 6 * (number of triangles in G),0 1 11 0 11 1 0,A(G)=,2 1 1 1 2 1 1 1 2,A(G)2=,2 3 33 2 33 3 2,A(G)3=,Fast k-Clique Detecting and Counting,Locat

7、e k-clique: build a graph Gk/3 = (Vk/3,Ek/3) where Vk/3 = (k/3)-cliques in G and Ek/3 = c1,c2:c1,c2 Vk/3,c1 c2 is a (2k/3)-clique in G Each triangle in Gk/3 corresponds to a unique k-clique in G? Time complexity: For example, to locate 6-clique:,Split and List,Step 1: Delegating responsibilityDefine

8、 responsibility map r: C (|k| ),x1 x2 0 0 0 1 1 0 1 1,x3 x4 0 0 0 1 1 0 1 1,x5 x6 0 0 0 1 1 0 1 1,Split and List (Cont.),Step 2: Weighting accordinglyConsider the partitions as a weighted k-partite complete graph. Assign weights to both vertices and edges.,x1 x2 0 0 0 1 1 0 1 1,x3 x4 0 0 0 1 1 0 1 1

9、,x5 x6 0 0 0 1 1 0 1 1,# of cliques = 2n,# of vertices = k2k,Split and List (Cont.),Step 3: Enumerate unweighted graphs reducing from the weighted graph in step 2. Each unweighted graph, constructed in amortized time O(1), consists of cliques of weight N. Decompose N into different combinations of w

10、eights ( nonnegative integers)Consider variables y1,2, y1,3,yk-1,k where y1,2 0,1,2,N. Solve the following equation: y1,2+y1,3+y1,k + y2,1 +yk-1,k = Nvi: some node in partition i w(): weight of some node or some edge,w(v1) + w(v2) + w(v1,v2),w(vj) + w(vi,vj),w(vi,vj),Time Complexity,Set k=3, we get O(m32n/3),