Unformatted text preview:

15-499: Parallel Algorithms Lecturer: Guy BlellochTopic: Graphs III Date: Mar. 3rd, 2009Scribe: Harsha Simhadri14.1 Maximal Independent SetGiven a graph G = (V, E), an independent set is a set of vertices S ⊆ V such that if u, v ∈ S, then(u, v) /∈ E. A maximal independent set is an independent set to which no more vertices can be added without violating the independence property. Let d(v) denote the degree of a vertex v.Algorithm 1 MaxIndSet(V, E)1: MIS ← ∅2: repeat3: Select v ∈ V with probability 1/2d(v) in to set S4: for (u, v)inE do5: if u, v are in S then6: if d(u) > d(v) then7: remove v8: end if9: if d(u) = d(v) then10: remove one of u, v from S11: end if12: end if13: end for14: Call this reduced set I15: Add I to MIS16: Remove I and all it’s neighboring vertices and all incident edges from G17: S ← ∅18: until E = ∅You can find more details for the proof in the link on the course webpage.We define good vertices and edges as follows:• D(v) = {u : (u, v) ∈ E|d(u) ≤ d(v)}• Good Vertices : VG= {v ∈ V | |D(v)| > d(v)/3}• Good Edges : EG= {(u, v) ∈ E|u ∈ VGOR v ∈ VG}Proof outline: 1/2 the edges are good for good vertices a constant probability that will be deleted thereforea constant probability that an edge will be deleted1Lemma 14.1.1 |EG| ≥ |E|/2.Proof: edges from smaller to larger. For bad nodes count two edges out for everyone in. By simple countingat most 1/2 the vertices can be bad.Lemma 14.1.2 ∀v ∈ VG,P(u,v)∈Ed(u)/2 > 1/6.Proof: Just consider the neighbors u with d(u) ≥ d(v). (d(u)/3)/2d(v) > (d(u)/3)/2d(u) > 1/6.Lemma 14.1.3 P r[v ∈ S ∩ v /∈ I] ≤ 1/2Lemma 14.1.4 p(v ∈ I) ≥ 1/4d(v).Lemma 14.1.5 ∀v ∈ VG, P r(v ∈ N(I)) ≥ 1/36.Proof: if d < 3 then simple otherwise...Since half the edges are good, the probability that an edge is removed is at least 1/72.14.2 Biconnected componentsA biconnected compenent of an undirected graph G is a maximal set of edges such that any two edges inthe set lie on a common simple cycle. A bridge is an edge that does not belong to any cycles.Given a graph G(V, E), the following procedure creates a graph G′(V′, E′) on the edges E of G such thetany pair of vertices ue, ue′∈ V′that correspond to edges u, u′that are in a cycle in G will be in the sameconnected component in G′.ab cdef ghi(b,c)(a,b) (a,c)(b,d)(e,d)(f,g)(d,g)(e,f)(e,g)(g,h) (g,i)(h,i)Figure 14.2.1: An example graph G and it’s associated G′Algorithm Outline:2• Generate spanning tree T of G and root it. Denote the parent of vertex v in this tree by p(v)• Calculate preorder number, pre(v), and size, size(v), for every vertex• For each vertex v, calculate the lowest neighbor, low(v), of any vertex in its subtree.• Similarly for highest, high(v).• Add edges to G′as follows:– R1: add (v, p(v)), (p(v), p(p(v))) to G’ if(low(v) < pre(p(v))) OR (high(v) > pre(p(v)) + size(p(v)))– R2: add (v, p(v)), (v, u)) to G’ if(pre(u) < pre(v)) OR (pre(u) > pre(v) + size(v))• Find connected components of G’Root12345 67 89Figure 14.2.2: A rooted tree of G with prefix labelsConsider an arbitrary rooted spanning tree T on G Note that any edge in E − T cannot be a bridge. Gen-erating a prefix label pre(.) for every vertex can be done with tree contraction. Computing the size of eachsubtree size(.) can also be done with tree contraction (leaffix).Compute for every vertex u the minimum and maximum labels min(v), max(v) over all neighbors v of u.Using this computation, we can calcluate the low(.), high(.) for all vertices as follows:• Calculate leaffix min on the minimum to get low(v)• Calculate leaffix max on the maximums to get high(v)Consider the predicate c(v) = low(v) < pre(v) OR high(v) > pre(v) + size(v)Lemma 14.2.1 A tree edge (v, p(v)) is a bridge iff c(v)3Proof: If there is such a condition then there is an edge out of the tree rooted at v and we must have acycle involving (v, p(v)). If there is not such a condition then there is no edge out of the tree and removing(v, p(v)) would disconnect the graph.Now lets consider connecting the cycles. Recall:• R1: add (v, p(v)), (p(v), p(p(v))) to G’ if(low(v) < pre(p(v))) OR (high(v) > pre(p(v)) + size(p(v)))• R2: add (v, p(v)), (v, u)) to G’ if(pre(u) < pre(v)) OR (pre(u) > pre(v) + size(v))Claim : this only connects pairs of edges that are in a cycleTheorem 14.2.2 The connected components in G’ are biconnected components in GProof: By claim, this only connects edges in cycle. We will now argue that vertices of G′that correspondto edges in a cycle in graph G are connected in G′. Note that the pair of edges at the least common ancestorof the cycle will not be connected.look at cases• cycle edges go up tree ... connected by R1• cycle loops from a vertex to an ancestor ... connected by R2 and possibly R1• Cycle crosses between two branches ... connected by R1 and


View Full Document

CMU CS 15499 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?