Multiple Bipartite Complete Matching Vertex Blocker Problem: Complexity, polyhedral analysis and Branch-and-Cut

• Published in: Discrete optimization 2020-02, Vol.35, p.100551, Article 100551
• Main Authors: Laroche, Pierre, Marchetti, Franc, Martin, Sébastien, Nagih, Anass, Róka, Zsuzsanna
• Format: Article
• Language: English
• Subjects: Bipartite graph; Branch-and-Cut; Computer Science; Integer linear programming; Matching interdiction/blocker problem; Polytope
• ISSN: 1572-5286; 1873-636X
• DOI: 10.1016/j.disopt.2019.100551

Given a bipartite graph G=(U∪V,E), |U|⩽|V|, the surplus of G is defined by the maximum number k such that a matching covering all vertices of U still exists upon removal of any k vertices from V. Given a partition U={U1,…,Um} of U, the Multiple Bipartite Complete Matching Vertex Blocker Problem (MBCMVBP) consists in finding a partition V={V1,…,Vm} of V such that the smallest surplus among those of the induced subgraphs G[Ui∪Vi] is maximized. The removed vertices are related to the blocker notion. We show the strong NP-hardness of the MBCMVBP by using a reduction from the stable set problem. We also propose two integer linear programs for solving this problem. After comparing these two models, we introduce some valid inequalities for the model that outperforms the other one, and we analyze its facial structure. We then derive a Branch-and-Cut algorithm based on these results and conclude by an analysis of the experimental results.