Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

What is this problem about?

The Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree interview question asks you to analyze the edges of a weighted undirected graph. A critical edge is one that, if removed, would increase the weight of the Minimum Spanning Tree (MST). A pseudo-critical edge is an edge that can be part of some MST, but not necessarily all MSTs. You need to return two lists: one containing the indices of all critical edges and another for pseudo-critical edges.

Why is this asked in interviews?

This "Hard" difficulty problem is used by Google, Amazon, and Uber to test a candidate's advanced graph algorithm knowledge. It evaluation your mastery of Kruskal's Algorithm or Prim's Algorithm and your ability to reason about MST properties. It requires you to think about how individual edges affect the global optimization goal, which is a key skill in network design and infrastructure planning.

Algorithmic pattern used

This problem relies on MST construction using Union Find.

1. First, calculate the weight of the baseline MST using Kruskal's algorithm.
2. For each edge $E$:
   • Check if Critical: Construct an MST without edge $E$. If the resulting weight is greater than the baseline (or the graph becomes disconnected), $E$ is critical.
   • Check if Pseudo-Critical: If not critical, construct an MST while forcing edge $E$ to be included first. If the resulting weight equals the baseline MST weight, $E$ is pseudo-critical.

Example explanation

Graph: 3 nodes, 3 edges: (0-1, wt 1), (1-2, wt 1), (0-2, wt 1). Any two edges form an MST of weight 2.

1. Baseline MST weight = 2.
2. Check edge (0-1):
   • Remove it: MST using (1-2) and (0-2) has weight 2. Baseline unchanged. Not critical.
   • Force it: MST starting with (0-1) and adding (1-2) has weight 2. Equals baseline.
   • Result: Edge (0-1) is pseudo-critical. By symmetry, all three edges in this triangle are pseudo-critical.

Common mistakes candidates make

• Inefficient sorting: Re-sorting all edges for every check. You should sort once and use the sorted list for all MST builds.
• Missing the "Pseudo" definition: Forgetting that an edge is pseudo-critical only if it can reach the same minimum weight as the baseline.
• Ignoring disconnected graphs: Failing to handle the case where removing an edge makes it impossible to form a spanning tree.

Interview preparation tip

MST problems are almost always solved with Kruskal's + Union Find. To optimize, remember that Kruskal's is very fast once the edges are sorted. The core of this problem is the "Include/Exclude" logic applied to Kruskal's.