Approximating The Minimum Equivalent Digraph.ppt

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.,