Fault Tree Analysis (FTA) is one of the main problems for reliability studies, in particular for the probabilistic safety assessment of complex systems such as aircrafts or nuclear power plants. The extraction of Minimal Cut Sets (MCS) from a fault tree can be reduced to the problem of finding vertex separators in S-T directed acyclic graphs (S-T DAGs). Prior work introduced a quantum algorithm to identify these s-t vertex separators, but faces scalability issues in larger instances. In this paper, we present a novel hybrid quantum-classical algorithm to solve the problem of st-connectivity using a divide and quantum strategy. Large s–t DAG instances are partitioned into many subgraphs that fit the qubit capacity of current quantum hardware; each subgraph is solved on a quantum device, yielding partial solutions. These solutions are then recombined classically to produce all global vertex separators of the original s-t DAG, which are mapped back to the MCS of the original fault tree. The results showed that we were able to solve larger instances that have not been solved using a classical algorithm previously. We also quantify the effect of realistic noise by comparing results from noisy versus noise-free simulation, and report on prototype runs using IBM’s publicly available quantum hardware.