A shared risk resource group refers to a set of resources that share the same risk. In a computer network with shared risk resource groups, the network can be modeled as a labeled graph. The core connectivity concept within labeled graphs can be described by the Label s-t Cut problem. Given a graph with labels defined on edges, a source s and a sink t, the objective of the problem is to find minimum number of labels such that the removal of edges with these labels can disconnect s and t. The Label s-t Cut problem is NP-hard, and while several approximation algorithms exist, there is a notable lack of heuristic algorithms that perform well in practice. In this paper, we propose a Monte Carlo heuristic for solving the problem. The key contribution of our approach is the concept of the minimal subgraph connecting s and t, which is inspired by Menger’s theorem. Using this concept, we develop a Monte Carlo strategy to score labels based on their frequency of appearance in feasible solutions. Our heuristic then selects the top labels with the highest scores to form a feasible solution. Experimental results on random instances demonstrate that our heuristic significantly outperforms the best existing approximation algorithm for the problem.