Skip to main content

Advanced Graph Problems

TL;DR​

Tarjan's algorithm finds strongly connected components in O(V + E) single DFS pass, using a recursion stack and low-link values. Bipartite checking uses 2-coloring: attempt to color graph with 2 colors using BFS/DFS; impossible means not bipartite. Euler paths traverse each edge exactly once: existence requires (0 or 2) odd-degree vertices. Network flow concepts: max-flow equals min-cut; Ford-Fulkerson finds max flow by repeatedly finding augmenting paths. These advanced techniques solve problems in connectivity, matching, and resource optimization.

Core Concepts​

Strongly Connected Components (SCC)​

SCC are maximal vertex subsets where each vertex is reachable from every other vertex.

Key properties:

  • Unique decomposition: Every directed graph has unique SCC decomposition
  • DAG of SCCs: Condensing SCCs creates a DAG
  • Applications: Social networks (finding communities), web crawlers (finding cycles)

Why important: Identifies "super-nodes" for condensed graph analysis.

Tarjan's Algorithm​

Tarjan finds all SCCs in single DFS pass using recursion stack and low-link values.

Key concepts:

  • Discovery index: When vertex is first visited
  • Low-link value: Minimum discovery index reachable from vertex
  • Root of SCC: Vertex where low[v] == disc[v]

Algorithm:

  1. DFS from unvisited vertices
  2. Track discovery time and low-link value
  3. Use stack to maintain current path
  4. When low[v] == disc[v], pop stack to find complete SCC

Time complexity: O(V + E) - single DFS pass.

Bipartite Graphs​

Bipartite graph has vertices partitioned into two sets with edges only between sets, never within set.

Properties:

  • 2-colorable: Can be colored with 2 colors such that adjacent vertices have different colors
  • No odd cycles: All cycles have even length
  • Applications: Job scheduling (workers and jobs), matching problems

Bipartite checking:

  1. Attempt 2-coloring using BFS/DFS
  2. For each uncolored vertex, assign color 0
  3. For each neighbor, assign opposite color
  4. If conflict (neighbor same color), not bipartite

Euler Paths and Circuits​

Euler path traverses each edge exactly once. Euler circuit is Euler path forming cycle.

Existence conditions:

  • Euler circuit exists: Graph connected, all vertices have even degree
  • Euler path exists: Graph connected, exactly 0 or 2 vertices have odd degree
  • Cannot exist: More than 2 odd-degree vertices

Finding Euler path (Hierholzer's algorithm):

  1. If using Euler circuit conditions, start at any vertex
  2. If using path conditions with 2 odd-degree vertices, start at one
  3. Follow edges greedily; when stuck, backtrack and find another starting point
  4. Result is Euler path (may need reversal)

Network Flow Concepts​

Flow network has source, sink, and edges with capacities. Flow assigns value to each edge respecting capacity constraints and flow conservation.

Key concepts:

  • Capacity: Maximum flow on edge
  • Flow conservation: Inflow equals outflow (except source and sink)
  • Residual capacity: Remaining capacity after current flow
  • Augmenting path: Path from source to sink with available capacity
  • Max-flow min-cut theorem: Maximum flow equals minimum cut capacity

Ford-Fulkerson approach:

  1. Start with zero flow
  2. While augmenting path from source to sink exists:
    • Find path with positive residual capacity
    • Add minimum residual capacity along path to flow
    • Update residual capacities (forward and backward)

Key Algorithms​

Tarjan's SCC Algorithm​

Single-pass DFS finding all strongly connected components using discovery times and low-link values.

Bipartite Graph Checking​

Two-coloring approach: attempt to color graph with 2 colors; success means bipartite, failure means not.

Euler Path Finding (Hierholzer's Algorithm)​

Greedy path following with backtracking to ensure all edges traversed exactly once.

Ford-Fulkerson Maximum Flow​

Iterative path augmentation in residual graph until no augmenting paths remain.

Practical Example​

from collections import defaultdict, deque

class AdvancedGraph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_directed_edge(self, u, v):
        self.graph[u].append(v)

    # Tarjan's Algorithm for SCC
    def tarjan_scc(self):
        index_counter = [0]
        stack = []
        lowlinks = {}
        index = {}
        on_stack = defaultdict(bool)
        sccs = []

        def strongconnect(v):
            index[v] = index_counter[0]
            lowlinks[v] = index_counter[0]
            index_counter[0] += 1
            stack.append(v)
            on_stack[v] = True

            for w in self.graph[v]:
                if w not in index:
                    strongconnect(w)
                    lowlinks[v] = min(lowlinks[v], lowlinks[w])
                elif on_stack[w]:
                    lowlinks[v] = min(lowlinks[v], index[w])

            if lowlinks[v] == index[v]:
                scc = []
                while True:
                    w = stack.pop()
                    on_stack[w] = False
                    scc.append(w)
                    if w == v:
                        break
                sccs.append(scc)

        for v in self.graph:
            if v not in index:
                strongconnect(v)

        return sccs

    # Bipartite check using 2-coloring
    def is_bipartite(self):
        color = {}

        for start in self.graph:
            if start in color:
                continue

            queue = deque([start])
            color[start] = 0

            while queue:
                u = queue.popleft()
                for v in self.graph[u]:
                    if v not in color:
                        color[v] = 1 - color[u]
                        queue.append(v)
                    elif color[v] == color[u]:
                        return False

        return True

    # Euler path detection
    def has_euler_path(self):
        in_degree = defaultdict(int)
        out_degree = defaultdict(int)

        for u in self.graph:
            for v in self.graph[u]:
                out_degree[u] += 1
                in_degree[v] += 1

        odd_diff = 0
        for v in set(list(self.graph.keys()) + list(in_degree.keys())):
            diff = out_degree[v] - in_degree[v]
            if diff != 0:
                if abs(diff) != 1:
                    return False
                odd_diff += 1

        return odd_diff == 0 or odd_diff == 2

    # Hierholzer's algorithm for Euler path
    def euler_path(self):
        in_degree = defaultdict(int)
        out_degree = defaultdict(int)
        graph = defaultdict(list)

        for u in self.graph:
            for v in self.graph[u]:
                graph[u].append(v)
                out_degree[u] += 1
                in_degree[v] += 1

        start = None
        for v in graph:
            if out_degree[v] - in_degree[v] == 1:
                start = v
                break

        if start is None:
            start = next(iter(graph))

        stack = [start]
        path = []

        while stack:
            v = stack[-1]
            if graph[v]:
                u = graph[v].pop()
                stack.append(u)
            else:
                path.append(stack.pop())

        return path[::-1]

# Test
g = AdvancedGraph()
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3)]
for u, v in edges:
    g.add_directed_edge(u, v)

print("SCCs:", g.tarjan_scc())
print("Is bipartite:", g.is_bipartite())
print("Has Euler path:", g.has_euler_path())

Common Pitfalls​

warning

Mixing SCC detection with regular connectivity: SCCs require directed graphs; undirected graphs don't have meaningful SCCs. Use connected components for undirected graphs.

Wrong degree counting for Euler paths: Count actual edges (not vertices). Multi-edges count multiple times. Self-loops count for both in and out degree.

Starting Euler path from wrong vertex: For path with 2 odd-degree vertices, must start from one of them, not arbitrary vertex. Wrong start makes path impossible.

Not building residual graph for flow: Flow algorithms need residual capacities and backward edges. Forgetting backward edges prevents finding optimal flow.

Confusing bipartite with 2-colorability: Not all 2-colorable graphs are valid problem instances; graph structure matters. Verify bipartite property separately.

Topological sorting not on DAG: Tarjan SCC assumes DAG structure; cyclic graphs need different handling. Verify acyclicity first for correct results.

Self-Check​

  1. How does Tarjan's algorithm identify SCC root vertices? What is the significance of low-link values?
  2. Why must a bipartite graph have no odd-length cycles? Prove this property.
  3. For network flow, why is max-flow = min-cut true? What does this mean practically?

One Takeaway​

info

Advanced graph algorithms solve complex structural problems. Tarjan's SCC algorithm efficiently decomposes directed graphs into strongly connected components in one DFS pass. Bipartite checking via 2-coloring identifies graph structure quickly. Euler paths traverse edges exactly once, useful for routing and circuit problems. Network flow concepts model resource allocation where max-flow equals minimum cut capacity, enabling optimal distribution solutions. Understanding these algorithms unlocks solutions to real-world problems in social networks, transportation, and telecommunications.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing, 1(2), 146-160.
  • Ford, L. R., & Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics, 8(3), 399-404.