SCC

Work in Progress

Summary

SCC algorithms

Time ComplexityConstraintType of Graph ADT
kosaraju’s algorithmAL
tarjan’s algorithmAL

SCC related problems

Concept

Strong connectivity

StronglyConnected(G):
    choose any vertex s
    F = Reachable(G, s)
    B = Reachable(reverse(G), s)
	
    return every vertex is marked in both F and B

==>
by definition

<== for any u,v inn G
u~>s~>v and v~>s~>u

so u~>v and v~>u

Strongly connected components

  • subgraphs in which every vertex is reachable from every other vertex
  • 6 vertex graph
012345

Definition

  • Research mutual reachability as an equivalence relation
  • Distinguish strongly connected sets from maximal SCCs
  • Check treatment of isolated vertices and self-loops

can two SCCs share a vertex?

  • no
  • lemma - any two SCCs must be disjoint
  • by contradiction
  • if there is path from u to v, v to u and v to w and w to v, then there is u to w and w to u, so is an SCC

can DAGs have SCCs?

  • no

Component graph

  • is a DAG

  • proof? by contradiction

  • for every directe graph G, the component graph of G is a DAG

  • having a directed cycle among components contradicts maximality

  • Contract each SCC to one meta-vertex

  • Verify why a directed cycle among components would contradict maximality

  • Research how topological order supports downstream DAG algorithms

largest finish time by DFS always gives a vertex in a source component
take the reversal of G?

SCC partition by DFS finish times

  • run DFS on G^r to get finish times
  • while G != 0
    • v <- vertex with largest finish time
    • C <- DFS(v)
    • G <- G / C

component finish time

Kosaraju

SCC(G):
	run full DFS on G
	order = vertices in decreasing finish time

	R = reverse(G)
	comp[v] = UNASSIGNED for every v
	label = 0

	for s in order:
		if comp[s] == UNASSIGNED:
			label = label + 1
			DFS from s in R:
				visit only UNASSIGNED vertices
				assign label to every visited vertex

	return comp

the DFS finish time is what gives us the post-order behaviour

Algorithms

Research directions

  • Derive the 2-SAT satisfiability criterion from implication-graph SCCs
  • Explore dependency cycles and wait-for graphs
  • Study source and sink SCCs in graph augmentation problems
  • Check conventions for the condensation graph edge set

Sources