A mixed approximation algorithm for matching preclusion number in bipartite graphs

The matching preclusion problem, originating from graph theory, is widely applied in various areas such as network reliability analysis and distributed system design. Through the examination of network behavior under edge failures, this paper delivers essential theoretical foundations for advancing reliability design and optimization in diverse fields. The matching preclusion number of a graph <i>G</i>=(<i>V</i>, <i>E</i>) , denoted by <i>mp</i>(<i>G</i>) , is the fewest edges <i>E</i>'&#8838;<i>E</i> that must be removed to completely disrupt any perfect matching within the graph. Given a bipartite graph having perfect matchings, this paper considers how to find a minimum edge set whose deletion results a graph without any perfect matching. Due to the NP-hardness of the problem, we propose a mixed approximation algorithm for solving it. Our algorithm is actually a series of algorithms combined in which each of the algorithms solves a kind of bipartite graph with certain properties. To our best knowledge, our algorithm strengthens the previous best result with respect to approximation algorithms for bipartite graphs with perfect matchings.