Approximating The Minimum Equivalent Digraph.ppt

《Approximating The Minimum Equivalent Digraph.ppt》由会员分享，可在线阅读，更多相关《Approximating The Minimum Equivalent Digraph.ppt（28页珍藏版）》请在麦多课文档分享上搜索。

1、Approximating The Minimum Equivalent Digraph,S. Khuller, B. Raghavachari, and N. Young. 1995 SIAM J. Computing,Some Math Knowledge (1),Fourier Coefficients and Series:,Some Math Knowledge (2)*,Some Math Knowledge (3),Parsevals Theorem:,Some Math Knowledge (4)*,The MEG (minimum equivalent graph) prob

2、lem,Input: A directed graph G = (V, E ). Output: the smallest subset of edges that maintains reachability relations.,B,A,C,B,A,C,MEG is NP-hard*,Let G = ( V, E ) be a strongly connected digraph and |V | = n. G has a Hamiltonian Cycle |MEG(G )| = n. Pf: (=),a1,a2,ak,(n k ) nodes, each has indegree =

3、1.,Variants,Acyclic MEG problem: G is an acyclic digraph. polynomial time solvable.MSCSS (minimum strongly connected spanning subgraph) problem: G is a strongly connected digraph.,Reduce MEG to MSCSS (1),Step1: decompose G into Strongly connected components in polynomial time.,A,B,C,D,E,Reduce MEG t

4、o MSCSS (2),Step 2: acyclic MEG problem is in P.,A,B,C,D,E,A,B,C,D,E,Reduce MEG to MSCSS (3),Step 3: Solve MSCSS(A), , MCSS(E).,A,B,C,D,E,Two Implications,1. MSCSS is NP-hard,2. If MSCSS problem has error ratio k, then MEG problem has error ratio k.,Pf: After Step 1, 2, We get,A,B,C,D,E,Let C(A), ,

5、C(E) be the costs of our approximating solutions. Let C*(A), , C*(E) be costs of the optimal solutions.= C(A) kC*(A), , C(E) kC*(E),C* = C*(A)+ C*(B)+ C*(C) + C*(D)+ C*(E) + 4,C k ( C*(A)+ C*(B)+ C*(C) + C*(D)+ C*(E) ) + 4,(C / C*) k,A,B,C,D,E,C = C(A)+ C(B)+ C(C) + C(D)+ C(E) + 4,C kC*(A)+ kC*(B)+

6、kC*(C) + kC*(D)+ kC*(E) + 4,The approximation algorithm for the MSCSS problem,CONTRACT-CYCLESk (G ) 1. for i = k, k-1, k-2, , 2 2. While the graph contains a cycle with at least i edges 3. Contract the cycle. 4. return edges on those contracted cycles.,Is this algorithm correct?,1,2,5,3,4,6,7,8,6,7,

7、9,1. for i = k, k-1, k-2, , 2 2. While the graph contains a cycle with at least i edges 3. Contract the cycle. 4. return edges on those contracted cycles.,Let Gi = the graph after after contracting cycles with i edges. Let ni = #vertices remain in the graph after contracting cycles with i edges. Let

8、 ei = #edges on the contracted cycles with i edges,Symbol Definitions,Error ratio analysis (1),(Contraction Lemma): For any digraph G and set of edges S, C*(G ) C*(G S ),Error ratio analysis (2),Error ratio analysis (3),Error ratio analysis (4),Theorem: Contract-Cyclesk(G ) returns at most rk C*(G )

9、 edges, where,ni = #vertices remain in the graph after contracting cycles with i edges. ei = #edges on the contracted cycles with i edges,Time Complexity (1),How to find cycles with k edges ? Step 1: Find all simple paths P with k-1 edges. Step 2: foreach p P, check whether there is a path from the

10、tail of p to the head of p.,If k is even, there at most mk/2 such paths, where m = #edges:,Time Complexity (2)*,m,k/2,Time Complexity (3)*,If k is odd, there at most nm(k-1)/2 such paths:,m,(k-1)/2,1,n,Time Complexity (4),O(m) time to check whether there is a path from the tail of p to the head of p. O(kn) = O(n) iterations of the while loop. O(nm1+ k/2), k is even. O(n2m(1+k)/2), k is odd.,1. for i = k, k-1, k-2, , 2 2. While the graph contains a cycle with at least i edges 3. Contract the cycle. 4. return edges on those contracted cycles.,