An Experimental Study of Polynomial Time Algorithms for Minimum 2-Edge Connected Subgraph Problem

In this paper, we focus on the problem of finding a minimum-sized directed 2-edge-connected subgraph, a problem classified as NP-Complete [8], which plays a critical role in various practical applications. We present approximation algorithms aimed at finding efficient, high-quality solutions within polynomial time. These algorithms are based on a comprehensive analysis of the problem of finding a directed 2-edge-connected subgraph, with performance evaluated in terms of the number of edges. The results of our experiments demonstrate that the proposed algorithms effectively reduce the number of remaining edges across different graph scenarios, particularly in high-density graphs. Moreover, they maintain strong connectivity even in the event of edge failures, ensuring the continuity of network operations in the face of faults and disasters.