Procedia

Computer
Procedia Computer Science 00 (2016) 1–22 Science

Bipartite Complete Matching Vertex Interdiction Problem:

Complexity, Polyhedral Analysis and Branch-and-Cut.

Pierre Larochea , Franc Marchettia , Sébastien Martina , Anass Nagiha , Zsuzsanna Rókaa
a Université de Lorraine, Laboratoire de Conception, Optimisation et Modélisation des Systèmes, Ile du Saulcy, 57000 Metz, France

Abstract
The Bipartite Complete Matching Vertex Interdiction Problem (BCMVIP) consists in defining the maximum number of vertices
that can be removed in the biggest one of the two sets of vertices of a bipartite graph such that a complete matching still remains.
We show that the BCMVIP can be solved in polynomial time and we give the complete description of the associated polytope. We
generalize this problem to the Multiple BCMVIP (MBCMVIP) which consists in partitioning a bipartite graph such that, for all
induced subgraphs, the number of vertices that can be removed still ensuring a complete matching is maximal. In order to prove the
NP-hardness of this problem, we use a reduction of the stable set problem. We also give two integer linear programs for solving the
MBCMVIP. For each of these programs, we propose some valid inequalities and analyze their facial structure. We then compare
the two associated branch-and-cut algorithms and present some computational results.

Keywords: matching interdiction problem, bipartite graph, polytope, integer linear programming, branch-and-cut

1. Introduction

Given a bipartite graph G “ pU Y V, Eq, the complete matching problem on U consists in finding a matching (a
set of disjoint edges) covering all vertices of U (([3], [8])).
The matching interdiction problem [12] consists in finding the maximum number of edges that can be removed
such that a matching with a given cardinality still remains. In this paper, we first introduce the Bipartite Com-
plete Matching Vertex Interdiction Problem (BCMVIP) in order to find the maximum number of vertices that can
be removed such that a complete matching still remains. We then generalize it to the problem called the Multiple
BCMVIP (MBCMVIP). Given a partition U “ tU1 , ..., Um u of U, the MBCMVIP consists in finding a partition
V “ tV1 , ..., Vm u of V that maximizes the value of an integer k such that, for all i P t1, ..., mu, k is the maximum
cardinality of any subset of Vi that can be removed in the subgraph GrUi Y Vi s while ensuring the existence of a
complete matching on Ui .
This theoretical problem can be applied to assignment problems: it can be used to generate robust solutions or
to define and analyze their robustness. As an illustration, let U be a set of tasks and V a set of resources. The goal
is to determine a feasible assignment of all tasks to available resources in order to maximize a given criteria. In this
case, we aim to maximize the robustness which we define as the maximal number of missing resources still allowing a
valid assignment. Solving interdiction problems is a mean to determine the maximum possible perturbation such that,
beyond that point, no valid solution exists for the studied problem. Practically, these perturbations can be triggered

Email addresses: [email protected] (Pierre Laroche), [email protected] (Franc Marchetti),

[email protected] (Sébastien Martin), [email protected] (Anass Nagih),
[email protected] (Zsuzsanna Róka)
1
 / Procedia Computer Science 00 (2016) 1–22 2

by failures, attacks or absenteeism. Furthermore, such weakness analysis can be used to define tactical and strategic
investments to make the model robust.
In the field of human resources, it is essential to be able to anticipate the potential absenteeism, to ensure the
proper running of the company. This class of problems can be formulated by matching or scheduling models. One
of the problems related to matching interdiction problem has been studied in [11], where the authors consider the
minimum d-blocker problem. The goal is to determine a minimum cardinality subset of edges such that their deletion
from the graph decreases the matching number by at least d units. This problem corresponds to a particular case of
the edge interdiction problem. In [12], the author studies two particular versions of the matching interdiction problem.
The first one, called edge interdiction problem, considers a graph in which each edge has a weight and an interdiction
cost. The goal is to find a subset of edges such that the value of a maximum weight matching without these edges
is minimized, w.r.t. a cost constraint. The second problem is defined in an analogous way, where costs are applied
to vertices instead of edges. These problems are shown as being NP-complete even in bipartite graphs, and some
approximation algorithms are proposed to solve them. The same author, in [13], extended his proof to show the
NP-hardness of these problems in particular scope of bipartite graph.
To illustrate these problems in real life, in health-care services, we can consider the problem of affecting nurses
to jobs according to their skills in such a way that possible absences may not perturb the schedule. Moreover, the
BCMVIP model can be used to identify critical tasks which are the most difficult to fill [7] and hence can help to
define a better policy of human resources such as recruitment strategy, professional training and balancing between
care units. The MBCMVIP model deals with several shifts and can be used to optimize the global staff compositions
on shifts regarding to the number of possible absences. The idea is to have the biggest common flexibility on each
shift. Note that these models can be applied to study problems of assignment in any domain where the management
of staff or production with limited resources is needed (air or rail transports, timetabling, . . . ).
In this paper, we focus on interdiction problems but there are other application areas. For example, considering
computer networks, it is primordial to guarantee the continuity of services in case of dysfunction of some routers
or switches. These problems can be modeled by shortest paths [1], spanning trees [2] or network flows [6] in the
underlying graph.
In the next section, we give some basic definitions. In Section 3, we study the BCMVIP and we prove that it can
be solved in polynomial time. Section 4 presents the definition of the MBCMVIP and shows that it is NP-complete.
In Section 5 we propose and study two Integer Linear Programs. The first one is based on the dual of the model used
for the BCMVIP. The second one is an alternative with a reduced number of variables but an exponential number
of inequalities. We also analyze the associated polytope and present a new family of inequalities. Some resolution
strategies and experimental results are presented in Section 6. Finally, we propose some directions for further research
in Section 7.

2. Basic notions and definitions

Let us first introduce some notations and recall some basic notions concerning graphs, stable sets and matchings.

Graphs. Let G “ pW, Eq a graph, where W is the set of vertices and E Ď W ˆ W is the set of edges. For each
uv P E, the vertices u and v are said neighbors. In the following, the neighborhood
Ť of a vertex v P W is denoted by
NG pvq Ď W. We extend this notation to a subset W 1 Ď W by NG pW 1 q “ vPW 1 NG pvq.

Stable set. A subset S of vertices is a stable set if NG pS q X S “ H. Equivalently, each edge in the graph has at most
one endpoint in S . The size of a stable set is the number of vertices that it contains.

Maximal stable set. A stable set S is said maximal if it cannot be included strictly in another stable set. The problem
of finding such a set is called the maximum stable set problem and is a NP-hard optimization problem. The stable
set decision problem concerning the existence of a stable set of a given size at least K can be solved in polynomial
time if K is a fixed integer. However, if K depends on the number of vertices of the graph, the problem becomes
NP-complete.

2
 / Procedia Computer Science 00 (2016) 1–22 3

Bipartite graph. Let tU, Vu a partition of the set of vertices W (i.e. U YV “ W and U XV “ H) such that NG pUq Ď V
and NG pVq Ď U. G “ pW “ U Y V, Eq is said a bipartite graph.
Let V 1 Ď V, U 1 Ď U and ErU 1 YV 1 s “ tuv | u P U 1 , v P V 1 , uv P Eu. We denote by GrU 1 YV 1 s “ pU 1 YV 1 , ErU 1 YV 1 sq
the sub-graph of G induced by U 1 Y V 1 .

Matchings. Given a graph, a matching is a subset of edges such that no two edges share a common vertex. The
matching problem consists in finding a matching with a maximal cardinality ([3], [9]).

Complete Matchings. In the case of bipartite graphs G “ pU Y V, Eq, the problem of Complete Matching on U
consists in finding a matching covering all vertices of U.
The following theorem is a fundamental result on the existence of a complete matching in bipartite graphs ([5]).
Theorem 1 (Hall). Let G “ pU Y V, Eq be a bipartite graph. There exists a complete matching on U if and only if
|NG pU 1 q| ě |U 1 | for all U 1 Ď U.

Remark that the strong Hall property is defined in [9]. Nevertheless it is not related to our problem.

3. Bipartite Complete Matching Vertex Interdiction Problem (BCMVIP)

In this section, we focus on Bipartite Complete Matching Vertex Interdiction Problem. We first recall definitions
and some classical results given in [7] and illustrate them on some examples.
We also present the complexity of the BCMVIP and we show the relation with the stable set problem in bipartite
graphs.

3.1. Definitions and extended Hall theorem

Definition 1 (k-CM). Let G “ pU Y V, Eq be a bipartite graph. We say that G is k-Complete Matching on U if and
only if, for all V 1 Ď V with |V 1 | “ |V| ´ k, GrU Y V 1 s has a complete matching. For short, we denote by k-CM a
k-Complete Matching on U.

Definition 2 (BCMVIP). Let us denote by κpGq the maximal number k such that G is k-CM. The Bipartite Complete
Matching Vertex Interdiction Problem (BCMVIP) consists in finding κpGq for a given bipartite graph G.
Remark that a k-CM graph is also pk ´ 1q-CM, for k ą 1. On Figure 1, we present a 2-CM (and so 1-CM) graph:
deleting any two vertices (in grey color) from V, there still exists a complete matching on U (bold edges). It is not the
case for more than two vertices, hence κpGq “ 2.

V V V V V V
U U U U U U

Figure 1: 2-CM bibartite graph

Theorem 2 (Extended Hall). Let G “ pU Y V, Eq be a bipartite graph. G is k-CM if and only if, for all non-empty
subset U 1 Ď U, |NG pU 1 q| ě |U 1 | ` k.
Proof.
pñq We first show that if G is k-CM, then |NG pU 1 q| ě |U 1 | ` k for all non-empty U 1 Ď U.
Suppose that there exists U 1 Ď U such that |NG pU 1 q| ă |U 1 | ` k. Let V 1 Ď NG pU 1 q with |V 1 | “ k. Then,
|NG pU 1 qzV 1 | ă |U 1 |. We deduce, by Hall’s theorem, that GrU Y pVzV 1 qs has no complete matching. Thus, G is not
k-CM.
3
 / Procedia Computer Science 00 (2016) 1–22 4

pðq We show now that if |NG pU 1 q| ě |U 1 | ` k for all U 1 Ď U, then G is k-CM.

Suppose that G is not k-CM: there exists V 1 Ď V with |V 1 | “ k such that G1 “ GrU Y pVzV 1 qs has no complete
matching. By Hall’s theorem there exists U 1 Ď U such that |NG1 pU 1 q| ă |U 1 |. It is easy to see that in the graph
G the number of neighbors of U 1 is less than |U 1 | ` |V 1 |. We deduce that |NG pU 1 q| ă |U 1 | ` k which leads to a
contradiction.
In the particular case where k “ 0, this theorem is equivalent to the original Hall theorem.
Let U 1 Ď U be any non-empty subset of vertices, it is clear that |NG pU 1 q| ´ |U 1 | ě κpGq, thus we have the
following result.
Corollary 1. Let G “ pU Y V, Eq a bipartite graph. Then,
´ ¯
κpGq “ 1 min1 |NG pU 1 q| ´ |U 1 | .
U ĎU, U ‰H

In the next section, we will present a mathematical formulation based on these results.

3.2. Mathematical formulation and complexity

We now present an integer linear program formulation allowing to compute κpGq by constructing U 1 .
Let x P t0, 1u|UYV| defined by

1 if u P U 1 ,
"
xu “ @u P U,
0 otherwise,

"
1 if v P NG pU 1 q,
xv “ @v P V.
0 otherwise,

The BCMVIP can be formulated as follows:

˜ ¸
ÿ ÿ
min xv ´ xu (1)
vPV uPU
ÿ
xu ě 1, (2)
uPU
pIPq xu ´ xv ď 0, @uv P E, u P U, v P V, (3)
xw ď 1, @w P U Y V, (4)
´ xw ď 0, @w P U Y V, (5)
xw P t0, 1u, @w P U Y V. (6)

The objective function expresses the Corollary 1. The inequality (2) guarantees that the set U 1 is not empty.
Inequalities (3) ensure that the variables xv associated with the neighborhood of U 1 will be set to 1.
We denote by pPq the linear relaxation of pIPq, i. e. the model pIPq without constraint (6).
Theorem 3. The BCMVIP can be solved in polynomial time.
Proof. We show that the BCMVIP can be solved in polynomial time by using a two-steps proof. In Step 1, we show
the polynomial complexity of the sub-problem obtained by removing the inequality (2). In Step 2, we show that the
BCMVIP can be solved resolving this sub-problem |U| times.
Step 1. Let us consider the set of inequalities (3-5), denoted by Ax ď b, where A is the matrix of coefficients, x is
a vector of variables and b is an integer vector. The coefficients of the matrix AT (transposition of A) are ˘1 or 0 and
4
 / Procedia Computer Science 00 (2016) 1–22 5

each column has at most one coefficient 1 and at most one coefficient -1. By the Poincaré theorem ([10]), AT is totally
unimodular, and so is A. As b is an integer vector, we deduce that the polytope convptx | Ax ď buq is integer ([? ]).
Thus, pPq without the inequality (2), denoted by pP1 q, can be solved in polynomial time.
Step 2. Since any optimal solution must contain at least one vertex, we consider for each ũ P U a sub-problem
pPũ q “ pP1 |xũ “ 1q, where ũ is in the optimal solution. We also remark that the polytope convptx | Ax ď b and xũ “
1uq remains integer. Hence, the problems pPũ q can be solved in polynomial time [4]. Solving pPũ q for each ũ P U, the
optimal solution of the BCMVIP is the minimum among these |U| solutions.
In practice, for some cases depending on the neighborhoods, we can reduce the number of programs pPũ q being
necessary to solve, according to the following proposition.
Proposition 1. Let ũ1 , ũ2 P U. If NG pũ1 q Ă NG pũ2 q then solving pPũ2 q becomes worthless.

Proof. For all U 1 Ď U containing ũ1 and ũ2 , we have

|NG pU 1 q| ´ |U 1 | “ |NG pU 1 ztũ1 uq| ´ |U 1 | ď |NG pU 1 ztũ1 uq| ´ |U 1 ztũ1 u|

Let U21 be a subset associated to the optimal solution of pPũ2 q. The inequality above implies that ũ1 P U21 .

` Let us˘ consider now U11 as being any subset of U containing ũ1 but not ũ2 . By constructing a subset U21 “
U1 ztũ1 u Y tũ2 u for each U11 , we obtain all subsets of` U containing
1
˘ ũ2 but not ũ1 . As NG pũ1 q Ď NG pũ2 q, thus for all
U11 , |NG pU11 q| ´ |U11 | ď |NG pU21 q| ´ |U21 | where U21 “ U11 ztũ1 u Y tũ2 u.
According to Theorem 2, the upper bound given by pPũ1 q is less or equal to the upper bound given by pPũ2 q and
hence solving pPũ2 q is worthless.
We denote by Ũ the set of vertices ũ P U such that there does not exist ũ1 P U verifying NG pũ1 q Ă NG pũq. This
set will be used to improve the efficiency of the computational experiments by improving the model presented in
Section 5.1.
Definition 3. Given a bipartite graph G “ pU Y V, Eq, the Bipartite Non Empty Stable Set Problem (BNEUSSP)
consists in finding a maximum stable set S Ď U Y V containing at least one vertex of U.
Another way to solve the BCMVIP in polynomial time is to reduce it to a stable set problem as shown in the
following proposition.
Proposition 2. BCMVIP is equivalent to BNEUSSP.
Proof. Let x̄v “ 1 ´ xv , for all v P V. We can rewrite the program pPq and we obtain the following linear program.
˜ ¸ ˜ ¸
ÿ ÿ ÿ ÿ
min |V| ´ x̄v ´ xu “ |V| ´ max x̄v ` xu
vPV uPU vPV uPU
ÿ
xu ě 1, (7)
uPU
pP̄q xu ` x̄v ď 1, for all uv P E where u P U and v P V, (8)
xu P t0, 1u, for all u P U, (9)
x̄v P t0, 1u, for all v P V. (10)

Without the inequality (7) this problem is the well-known stable set problem in bipartite graph. The BCMVIP is
equivalent to the BNEUSSP. Hence, we can solve the BCMVIP by solving |U| times the flow graph given in [8].

5
 / Procedia Computer Science 00 (2016) 1–22 6

4. Multiple Bipartite Complete Matching Vertex Interdiction Problem (MBCMVIP)

The MBCMVIP is a generalization of the BCMVIP for the case where the set U is a set of disjoint subsets
forming a partition of U. First, we give some definitions and we illustrate them on some examples. Then, we present
the complexity of this problem.
Definition 4. Let G “ pU Y V, Eq be a bipartite graph, U “ tU1 , ..., Um u be a partition of U and V “ tV1 , ..., Vm u
be a partition of V. For all i P M “ t1, ..., mu, we denote by Hi the subgraph GrUi Y Vi s. We say that pG, U, Vq is
k-Multiple Complete Matching on U if and only if, for all i P M, Hi is k-CM on Ui . For short, we denote by k-MCM
a k-Multiple Complete Matching on U.
A sample 1-MCM solution is presented on Figure 2. The subgraph H1 “ GrU1 Y V1 s is 2-CM and the subgraph
H2 “ GrU2 Y V2 s is 1-CM.

V V
U U

U1 U1 V1

U2 U2 V2

Figure 2: An instance of a 1-MBCMVIP and its solution

Definition 5 (MBCMVIP). Let G “ pU Y V, Eq be a bipartite graph and U “ tU1 , ..., Um u a partition of U.

The Multiple Bipartite Complete Matching Vertex Interdiction Problem (MBCMVIP) consists in finding a partition
V “ tV1 , ..., Vm u of V such that min κpHi q | i P M is maximum. We denote this maximum number by κpG, U, Vq.
(

We call this problem m-MBCMVIP when the cardinality of the partition U is m.

For instance, the 2-MBCMVIP pG, tU1 , U2 u, tV1 , V2 uq presented on Figure 2 is 1-MCM.
To study the complexity of the m-MBCMVIP, we consider the decision problem associated with this problem, that
is, the existence of a solution. For short, we will also refer to it as m-MBCMVIP. In order to show that m-MBCMVIP
is NP-complete, it is sufficient to show that even the 2-MBCMVIP is NP-complete. For that, we shall use the stable
set decision problem: given a connected graph G1 “ pV 1 , E 1 q and a positive integer K ď |V 1 |, does G1 contain a stable
set of size at least K?
Theorem 4. 2-MBCMVIP is strongly NP-complete.
Proof. We show the NP-completeness of 2-MBCMVIP by a transformation from the stable set problem.
Consider an instance of the stable set problem G1 “ pV 1 , E 1 q and a positive integer K ď |V 1 |. We transform it
into an instance of the 2-MBCMVIP by constructing a graph G “ pU Y V, Eq and a partition U “ tU1 , U2 u in the
following way.
For each edge e1 P E 1 , we associate a vertex u1e1 in U1 . We also consider a unique vertex u2 in U2 .
We split V into three disjoint sets W1 , W2 and W3 . For each edge e1 P E 1 , we associate a vertex v1e1 in W1 . For
each vertex v1 P V 1 , we associate a vertex v2v1 in W2 . We also add an edge u1e1 v1e1 in E, for all e1 P E 1 . For all v2v1 P W2
and for all u1e1 P W1 , we add an edge v2v1 u1e1 if and only if e1 is not incident to v1 in the graph G1 . For all v2 P W2 we
add an edge v2 u2 in E. An instance of the stable set problem is illustrated on Figure 3a and the partial construction
of G, where W3 does not yet appear, is illustrated on Figure 3b. In fact, W3 is a set of dummy vertices, depending on
|V 1 | |V 1 |
the size K of the stable set of G1 : K ď 2 or K ą 2 . To complete the construction, these two cases are studied in
Lemma 1 and Lemma 2, respectively.
6
 / Procedia Computer Science 00 (2016) 1–22 7

va2 W5
U2
va2 W2 vb2 u2
U2
vb2 vc2
u2 U1
vc2 u1ab vd2
U1
u1ab vd2 u1ae ve2 W4
u1ae ve2 u1bc 1
vab W1
u1bc 1
vab u1bd 1
vae
W1
u1bd 1
vae u1be 1
vbc
u1be 1
vbc u1cd 1
vbd
u1cd 1
vbd 1
vbe
1 1
vbe vcd
1
vcd v3 W3

(a) Stable set problem instance (b) Partial construction of G (c) Complete construction of G

Figure 3: Stable set problem instance and the associated bipartite graph for Lemma 1

|V 1 |
Lemma 1. Let K ď 2 . G1 contains a stable set of size at least K if and only if there exists a partition V “ tV1 , V2 u
of V such that pG, U, Vq is at least p|V 1 | ´ K ´ 1q-MCM.
Proof. First we add |V 1 | ´ 2K fictitious vertices in W3 . For each vertex v3 P W3 we add the edges u1 v3 in E for all
u1 P U1 . A complete construction of G is illustrated on Figure 3c.
Let Hi “ GrUi Y Vi s and Ni pwq the neighborhood of the vertex w P Ui Y Vi , where i P t1, 2u.
(ñ) Let us suppose that G1 contains a stable set of size K and let S Ď V 1 be the vertices of this stable set
(S “ te, du on Figure 3a for our example). We split W2 into W4 and W5 : let W4 Ď W2 be the set of vertices associated
to the vertices of S and W5 “ W2 zW4 .
Let Hi j “ GrUi Y W j s and Ni j pwq the neighborhood of the vertex w in Ui Y W j , where i P t1, 2u and j P
t1, 2, 3, 4, 5u. Let V1 “ W1 Y W3 Y W4 and V2 “ W5 .
As N2 pu2 q “ |W5 | “ |V 1 |´K, we deduce that H2 is p|V 1 |´K ´1q-CM. We now show that H1 is also p|V 1 |´K ´1q-
CM. Each vertex u1e1 P U1 has exactly one neighbor in W1 (|N11 pu1e1 q| “ 1) and is connected to all vertices of W3
(|N13 pu1e1 q| “ |V 1 | ´ 2K). Furthermore, |N14 pu1e1 q| “ K ´ 1 (respectively K) if e1 is incident (respectively is not
incident) to a vertex in S . Since the graph is connected, at least one vertex of S is incident to one edge of E 1 , we can
hence consider that |N1 pu1e1 q| ě |V 1 | ´ K. Thanks to the set of vertices W1 , if we add a set of vertices U11 Ď U1 ztu1e1 u
to tu1e1 u, then |N1 pU11 Y tu1e1 uq| ě |V 1 | ´ K ´ 1 ` |U11 Y tu1e1 u|. By Theorem 2, we deduce that the subgraph H1 is
p|V 1 | ´ K ´ 1q-CM.
Thus, pG, U, Vq is p|V 1 | ´ K ´ 1q-MCM.
(ð) Suppose now that there is a partition V “ tV1 , V2 u such that pG, U, Vq is p|V 1 | ´ K ´ 1q-MCM but there is
no stable set of size K in G1 . Let W4 “ V1 X W2 and W5 “ V2 X W2 .
As H2 is p|V 1 | ´ K ´ 1q-CM, we have |W5 | ě |V 1 | ´ K. Suppose that |W4 | “ K ´ 1. Let u1e1 P U1 such that e1 is
incident to a vertex w in V1 : u1e1 has exactly one neighbor in W1 (|N11 pu1e1 q| “ 1) and is connected to all vertices of W3
(|N13 pu1e1 q| “ |V 1 |´2K). Furthermore, as |N14 pu1e1 q| ď K ´2, we have |N1 pu1e1 q| ď K ´2`1`|V 1 |´2K “ |V 1 |´K ´1.
Thus, H1 cannot be p|V 1 | ´ K ´ 1q-CM. Clearly, if |W4 | ă K ´ 1, then H1 cannot be p|V 1 | ´ K ´ 1q-CM neither.
Now we consider |W4 | “ K. Remark that W1 Ď V1 , W3 Ď V1 , V1 “ W1 Y W3 Y W4 and |N11 pu1e1 q| ` |N13 pu1e1 q| “
|V | ´ 2K ` 1. Let S a subset of V 1 associated with the vertices of W4 . As H1 is p|V 1 | ´ K ´ 1q-CM, we have
1

|N14 pu1e1 q| ě K ´ 1. Hence, each edge e1 of E 1 is incident to at most one vertex in S , thus S is a stable set of G1 , which
leads to a contradiction.
|V 1 |
Lemma 2. Let K ą 2 . G1 contains a stable set of size at least K if and only if there exists a partition V “ tV1 , V2 u
of V such that pG, U, Vq is at least pK ´ 1q-MCM.

7
 / Procedia Computer Science 00 (2016) 1–22 8

Proof. First we add 2K ´ |V 1 | fictitious vertices in W3 . For each vertex v3 P W3 we add the edges u2 v3 in E. We will
now prove the following statement to complete the proof: G1 contains a stable set of size K if and only if there exists
a partition V such that pG, U, Vq is pK ´ 1q-MCM.
(ñ) Let us suppose that G1 contains a stable set S of size K. Let W4 be the set of vertices in V associated with the
vertices of S , and W5 “ W2 zW4 : we split W2 into W4 and W5 . An example of a stable and its associated graph can be
seen on Fig. 4.
Let V1 “ W1 Y W4 and V2 “ W3 Y W5 . Then V is a partition such that pG, U, Vq is pK ´ 1q-MCM.
Indeed, as |W5 | “ |V 1 | ´ K and |W3 | “ 2K ´ |V 1 |, u2 has exactly K neighbors. Thus H2 is pK ´ 1q-CM.
Each vertex u1e P U1 has exactly one neighbor in W1 (|N11 pu1e q| “ 1) and at least K´1 neighbors in W4 (|N14 pu1e q| ě
K ´ 1). In an analogous way as in the proof of Lemma 1, we can consider that |N1 pu1e q| ě K and by Theorem 2, we
deduce that the subgraph H1 is pK ´ 1q-CM.
Thus, pG, U, Vq is pK ´ 1q-MCM.

W3 v3

va2 W2 va2
W5
vb2 u2 vb2 u2
U1 U1
u1ab vc2 U2 u1ab vc2 U2

u1ad vd2 u1ad vd2

u1ae ve2 u1ae ve2

W4
u1bc 1
vab u1bc 1
vab
W1 W1
u1bd 1
vad u1bd 1
vad
1 1
vae vae
1 1
vbc vbc
1 1
vbd vbd

(a) Stable set problem instance (b) Partial construction of G (c) Complete construction of G

Figure 4: Stable set problem instance and the associated bipartite graph for Lemma 2

(ð) Suppose now that there exists a partition V “ tV1 , V2 u such that pG, U, Vq is pK ´ 1q-MCM but there is no
stable set of size K in G1 . By using the same notations and the same proof mechanism as for Lemma 1 (ð part), we
consider the case where |W5 | “ |V 1 | ´ K and |W4 | “ K.
Let S a subset of V 1 associated with the vertices of W4 . As H1 is pK ´ 1q-CM, we have |N14 pu1e1 q| ě K ´ 1 and
|N11 pu1e1 q| “ 1. Hence, each edge e1 of E 1 is incident to at most one vertex in S , thus S is a stable set of G1 , which
leads to a contradiction.
From these two lemmas, we deduce that the 2-MBCMVIP is NP-complete.

Corollary 2. m-MBCMVIP is strongly NP-complete.

5. Integer linear programs for m-MBCMVIP

In this section, we propose two integer linear programs for solving m-MBCMVIP. Recall that GpU Y V, Eq is a
bipartite graph and U is a partition of U.

5.1. Dual based formulation

The first integer linear program is based on the dual of the model pPq. Indeed, it is not possible to model the
m-MBCMVIP directly by maximizing the smallest difference on each graph Hi , i P M. If we maximize the smallest
difference on each graph Hi , i P M, then we do not find κpHi q since κpHi q is given by the smallest difference. For this
reason, the dual is used to propose a model where the biggest value obtained by the Duality Theorem is maximized.
8
 / Procedia Computer Science 00 (2016) 1–22 9

Let us first study the BCMVIP. In order to convert the linear relaxation pPq of pIPq into a dual problem pDq, we
consider the sub-problem pPũ q of pPq where ũ P U 1 : the inequality (2) of pPq is replaced by the equality (11) in pPũ q:

˜ ¸
ÿ ÿ
min xv ´ xu
vPV uPU
yũ : xũ “ 1, (11)
pPũ q yuv : xv ´ xu ě 0, @uv P E, u P U, v P V, (12)
yv : ´xv ě ´1, @v P V, (13)
xw ě 0, @w P pU Y Vqztũu. (14)

Then, the dual program pDũ q is defined as follows:

˜ ¸
ÿ
max yũ ´ yv
vPV
ÿ
xũ : yũv ´ yũ ě 1, (15)
vPNG pũq
ÿ
pDũ q xu : yuv ě 1, @u P Uztũu, (16)
vPNG puq
ÿ
xv : yuv ´ yv ď 1, @v P V, (17)
uPNG pvq

yw1 ě 0, @w1 P pU Y Vqztũu, (18)

yuv ě 0, @uv P E, u P U, v P V (19)
yũ free. (20)

By the Duality Theorem, if a standard linear programming problem is bounded feasible, then so is its dual, their
objective functions values are equal. As the matrix associated with P is totally unimodular, then the matrix associated
with D is also totally unimodular. Thus the optimal solution of both programs are integer. Hence, for each vertex ũ of
U, we can define the dual program pDũ q and we obtain the linear program pDq:

max y (21)
ÿ
xũ : yũũv ´ yũũ ě 1, @ũ P U, (22)
vPNG pũq
ÿ
xu : yũuv ě 1, @ũ P U, @u P Uztũu, (23)
vPNG puq
ÿ
pDq xv : yũuv ´ yũv ď 1, @ũ P U, @v P V, (24)
uPNG pvq
ÿ
y ď yũũ ´ yũv , @ũ P U, (25)
vPV
ũ
yw ě 0, @ũ P U, @w P pU Y Vqztũu, (26)
yũuv ě 0, @ũ P U, @uv P E, u P U, v P V, (27)
yũũ free, @ũ P U. (28)

An optimal solution of pDq corresponds to a solution of minimum value of the pDũ q programs, for all ũ P U.
Remark that the coefficient matrix of pDũ q is the matrix AT introduced in the proof of Theorem 3. It has been shown

9
 / Procedia Computer Science 00 (2016) 1–22 10

totally unimodular, hence the objective function values of pDũ q are integer, and so is the objective function value of
pDq. The program pDq allows to solve the BCMVIP.
We denote by pIDi q the program associated with Ui P U. Now we extend this formulation to solve the m-
MBCMVIP by merging the programs pIDi q, i P M. We define the binary variables

1 if v P Vi ,
"
xvi “ @v P V and @i P M.
0 otherwise,

We can deduce the following integer linear program:

max y
ÿ
yũũv ´ yũũ ě 1, @i P M, @ũ P Ui , (29)
vPNi pũq
ÿ
yũui v ě 1, @i P M, @ũ P Ui , @u P Ui ztũu, (30)
vPNi pui q
ÿ
yũuv ´ yũv ď 1, @i P M, @v P V, @ũ P Ui , (31)
uPNi pvq
ÿ
yi ď yũũ ´ yũv , @i P M, @ũ P Ui , (32)
vPV
pID1 q y ď yi , @i P M, (33)
yũuv ď µxvi @i P M, @ũ P Ui , @uv P E, u P Ui , v P V, (34)
yũv ď µxvi @i P M, @ũ P Ui , @v P V, (35)
ÿ
xvi “1 @v P V, (36)
iPM
yũw ě 0, @i P M, @ũ P Ui , @w P pUi Y Vqztũu, (37)
yũuv ě 0, @i P M, @ũ P Ui , @uv P E, u P Ui , v P V, (38)
yũũ free, @i P M, @ũ P Ui , (39)
xvi P t0, 1u, @i P M, @v P V (40)

where µ is a big constant value.

Inequalities (29) – (32) extend (22) – (25), (33) is derived from the objective function (21) and (34) – (36) ensure
the partitioning. Indeed, @v P V, i P M, if xvi “ 1, then all variables y associated with v in (34) – (35) are free, thanks
to the constant µ. Otherwise, all these values are equal to 0 and thus are not considered in the subset Vi . A solution
where all xi are fixed to 0 or 1 implies an integer value for all variables.
Thanks to Proposition 1 (page 5), considering only the variables associated with Ũ in the previous model is
sufficient.

5.2. Second Formulation

In this section, we propose an alternative formulation using a smaller number of variables and without the big
constant µ. An experimental study will be presented in Section 6 in order to compare the efficiency of the two
formulations.

5.2.1. Integer Linear Program Formulations

Recall that our goal is to find a partition V “ tV1 , ..., Vm u of V such that pG, U, Vq is κpG, U, Vq-MCM and that
we denote by Hi the subgraph GrUi Y Vi s, where i P M.
We now present the integer linear program formulated to find V. Let xvi , @v P V, @i P M, be defined as below and
z P N` be the value of κpG, U, Vq.
10
 / Procedia Computer Science 00 (2016) 1–22 11

So the expressed model is as follows:

max z
ÿ
xvi “ 1, for all v P V, (41)
iPM
ÿ
pP1 q xvi ´ z ě |U 1 |, for all i P M and for all U 1 Ď Ui , (42)
vPNG pU 1 q

xvi P t0, 1u, for all v P V and for all i P M, (43)

z P N` (44)

where inequalities (41) ensure that each vertex v P V belongs to only one set of the partition V and inequalities (42)
verify Theorem 2 on each Hi , i P M.

5.2.2. Polyhedral Study

To simplify the polyhedral study without modifying the optimal solution, we relax (41) by the following inequal-
ities:

ÿ
xvi ď 1 for all v P V. (45)
iPM

Let PpG, Uq be the convex hull of the solution of program pP1 q, that is,

PpG, Uq “ convptx P t0, 1u|V|ˆm , z | x, z satisfy (42), (45)uq.

A solution of PpG, Uq is a couple pV̆, z1 q where V̆ “ tV̆0 , V̆1 , ..., V̆m u is a partition of V, V̆0 is the set of all vertices
not in V̆1 Y ... Y V̆m and z1 is an integer such that z1 ď κpG, U, Vq.
Let the incidence vector xV̆ P t0, 1u|V|ˆm of the partition V̆ be given by
"
1 if v̆ P V̆i
xv̆i “ @v̆ P V̆i , @i P M.
0 otherwise,
Remark that, for all v̆ P V̆0 , m
ř i
i“1 xv̆ “ 0.

Hypothesis 1. We consider that, for all v P V, there exists a matching in Gztvu.

We can verify this hypothesis in polynomial time. If it is not verified, then z “ 0.
Proposition 3. The polytope PpG, Uq is full dimensional if and only if a 1-MCM solution exists.
Proof.
(ñ) If a 1-MCM solution does not exist, then z “ 0 and the polytope is not full dimensional.
(ð) We suppose that PpG, Uq is contained in a hyperplane defined by the linear equation

ax ` bz “ α (46)

where a “ paiv , v P V, i P Mq P R|V|ˆm , b P R and α P R. We will show that a “ 0, b “ 0 and PpG, Uq cannot be
included in the hyperplane (46), since it is not empty. As there exists a 1-MCM solution, there exists a solution where
z “ 1. We denote this solution by pV̆, 1q. Clearly pV̆, 0q is also valid for PpG, Uq and thus verifies (46). Then we
deduce b “ 0.
Let v P V. There exists a solution pV̆v , 0q which is valid for PpG, Uq where V̆v “ tV̆v,0 , V̆v,1 , . . . , V̆v,m u and
v P V̆v,0 . Otherwise, a 1-MCM solution does not exist.
Let i P M and let V̆v,i be the partition obtained from V̆v by moving the vertex v from V̆v,0 to V̆v,i . Then, the
solution pV̆v,i , 0q is also valid for PpG, Uq. We deduce that, for all i P M, aV̆v “ aV̆v,i . This equality holds for any
vertex v P V, we can thus conclude that a “ 0 and hence PpG, Uq is full dimensional.
11
 / Procedia Computer Science 00 (2016) 1–22 12

Proposition 4. If a 1-MCM solution does not exist, then dimpPpG, Uqq “ |V| ˆ m.
Proof. Clearly, we have the equality z “ 0.
Now we prove that all equalities of PpG, Uq are equivalent to z “ 0. We suppose that PpG, Uq is contained in a
hyperplane defined by the linear equation

ax “ α (47)

where a “ paiv , v P V, i P Mq P R|V|ˆm and α P R. We will show that a “ 0 and that PpG, Uq cannot be included in
the hyperplane (47), since it is not empty.
Let v P V, i P M and V̆v , V̆v,i defined as in the proof of Proposition 3. By the Hypothesis 1, there exists a solution
pV̆v , 0q which is valid for PpG, Uq, where v P V̆v,0 . The solution pV̆v,i , 0q is also valid for PpG, Uq and we deduce
that, for all i P M, aV̆v “ aV̆v,i . Thus a “ 0 and dimpPpG, Uqq “ |V| ˆ m.
In the following, for a better understanding of the proofs, we consider that a 1-MCM solution exists in G. The
proofs can be adapted for the case when no 1-MCM solution exists.
Proposition 5. The inequality (45) associated with v P V defines a facet of PpG, Uq.
Proof. Let us denote by ax ` bz ď α the inequality (45) associated with v P V. Let a1 x ` b1 z ď β be a facet defining
an inequality of PpG, Uq such that tx P PpG, Uq : ax ` bz “ αu Ď tx P PpG, Uq : a1 x ` b1 z “ βu. We show that
a1 “ ρa and b1 “ ρb for some ρ P R.
As a 1-MCM solution exists, there exists a solution where z “ 1. We denote this solution by pV̆, 1q. Clearly
pV̆, 0q is also valid for PpG, Uq and thus verifies (46). Then we deduce b “ 0.
Let v1 P Vztvu and i P M. By hypothesis, there exists a solution pV̆v1 , 0q which is valid for PpG, Uq where
v1 P V̆v1 ,0 . It is clear that the solution pV̆v1 ,i , 0q is also valid for PpG, Uq. We deduce aV̆v1 “ aV̆v1 ,i for all i P M. Thus
aiv1 “ 0 for all i P M and v1 P Vztvu.
Furthermore, there also exists a valid solution pV̆v1 , 0q for PpG, Uq where v P V̆v,0 1
. It is clear that the solution
1 1
1
pV̆v,i , 0q is also valid for PpG, Uq. We deduce that aV̆v,i “ aV̆v, j for all i, j P M. We set aiv “ ρ and we deduce that
aiv “ avj “ ρ for all i, j P M.
Proposition 6. The inequality (42) associated with i P M and U 1 Ď Ui defines a facet of PpG, Uq if and only if
1. if U 1 Ă Ui , then there does not exist U 2 Ď Ui where U 1 Ă U 2 such that |NG pU 1 q| ´ |U 1 | ě |NG pU 2 q| ´ |U 2 |,
2. there does not exist U 2 Ď Ui where |U 2 | “ |U 1 | such that NG pU 2 q Ă NG pU 1 q,
3. GrU 1 Y NG pU 1 qs is connected.
4. there exists a partition V̆ “ tV̆0 , ..., V̆m u and k ą 0 such that pG, U, V̆q is k-MCM, satisfying |V̆i X NG pU 1 q| “
|U 1 | ` k.
Proof.
(ñ)
1. If there exists U 2 Ď Ui where U 1 Ă U 2 such that NG pU 1 q “ NG pU 2 q then the inequality (42) associated with i and
U 1 is a linear combination of the inequality (42) associated with i and U 2 , the trivial inequalities ´xvi ě ´1 for all
v P NG pU 2 qzNG pU 1 q and p|NG pU 2 qzNG pU 1 q| ´ |U 1 |q times the trivial inequality 0 ě ´1.

2. If there exists U 2 Ď Ui where |U 2 | “ |U 1 | such that NG pU 2 q Ă NG pU 1 q then the inequality (42) associated with i
and U 1 is a linear combination of the inequality (42) associated with i and U 2 and the trivial inequality xvi ě 0 for
all v P NG pU 1 qzNG pU 2 q.

3. Suppose that GrU 1 Y NG pU 1 qs is not connected. Let U1 Ă U 1 such that GrU1 Y NG pU1 qs is a connected component.
In this case, the inequality (42) associated with i and U 1 is a linear combination of the inequality (42) associated
with i and U1 , the inequality (42) associated with i and U 1 zU1 and the trivial inequality z ě 0.
12
 / Procedia Computer Science 00 (2016) 1–22 13

4. Suppose that there does not exist a partition V̆ “ tV̆0 , ..., V̆m u such that pG, U, V̆q is k-MCM satisfying |V̆i X
NG pU 1 q| “ |U 1 | ` k. Then,
ř|V̆i X NG pU
1
q| ą |U 1 | ` k, for all k-MCM solutions pG, U, V̆ “ tV̆0 , ..., V̆m uq. We
i
deduce that the inequality vPNG pU 1 q xv ´ z ě |U 1 | ` 1 is valid. Clearly this inequality dominates the inequality
(42) associated with i and U 1 .

(ð) Let us denote by ax ` bz ď α the inequality (42) associated with i P M and U 1 Ď Ui . Let a1 x ` b1 z ď β be a
facet defining an inequality of PpG, Uq such that tx P PpG, Uq : ax ` bz “ αu Ď tx P PpG, Uq : a1 x ` b1 z “ βu. We
show that a1 “ ρa and b1 “ ρb for some ρ P R.
Remark that by the conditions 1–3 there exists, for all V 1 Ď NG pU 1 q where |V 1 | “ |U 1 |, a matching A such that
|A X GrU 1 , V 1 s| “ |U 1 |.
Let v P VzNG pU 1 q. By Hypothesis 1, there exists a complete matching A on U where v is not covered by A.
We denote the solution associated with A by pV̆v , 0qA . Clearly the solutions pV̆v, j , 0qA for j P M are valid. These
solutions pV̆v , 0qA and pV̆v, j , 0qA for all j P M are valid for PpG, Uq and verify the inequality (42) associated with U 1
to the equality. We deduce aV̆v “ aV̆v, j for all j P M. Thus a1vj “ 0 for all j P M and v P VzNG pU 1 q.
Let v P NG pU 1 q. By Hypothesis 1, there exists a complete matching A on U where v is not covered by A. We
denote the solution associated with A by pV̆v , 0qA . Clearly the solutions pV̆v, j , 0qA for j P Mztiu are valid. These
solutions pV̆v , 0qA and pV̆v, j , 0qA for all j P Mztiu are valid for PpG, Uq and verify the inequality (42) associated with
U 1 to the equality. We deduce aV̆v “ aV̆v, j for all j P Mztiu. Thus a1vj “ 0 for all j P Mztiu and v P NG pU 1 q.
Let v1 , v2 P NG pU 1 q. By Hypothesis 1, there exists a complete matching A1 without v1 and with v2 . As
GrU 1 , NG pU 1 qs is connected, there exists an alternative path between v1 and v2 . We define the complete match-
ing A2 using this alternative path. The solutions pV˘v1 , 0qA1 and pV˘v2 , 0qA2 associated respectively to A1 and A2 are
valid for PpG, Uq and verify the inequality (42) associated with U 1 to the equality. We deduce aV̆v1 “ aV̆v2 . Thus
a1iv1 “ a1iv2 “ ρ for all v1 , v2 P NG pU 1 q.
By condition 4, there exists a partition V̆ “ tV̆0 , ..., V̆m u such that pG, U, V̆q is k-MCM, satisfying |V̆i XNG pU 1 q| “
|U | ` k. Let v P V̆i and V̆1 “ tV̆0 Y tvu, V̆i ztvu, pV̆ j q jPMzt0,iu u. The solutions pV̆, kq and pV̆1 , k ´ 1q are valid for
1
1 1
PpG, Uq and verify the inequality (42) associated with U 1 to the equality. We deduce aV̆ ` bV̆ “ aV̆ ` bV̆ . Thus
i 1
av “ ´b and so b “ ´ρ.
In the following lemma we show that condition 4 is stronger than conditions 2 and 3. Nevertheless, the latter are
easier to implement. Indeed, verifying the condition 4 is NP-hard as the k-MCM property must be checked.
Lemma 3. In Proposition 6, condition 4
– does not imply condition 1;
– implies conditions 2 and 3.
Proof. We suppose that there exists a partition V̆ “ tV̆0 , ..., V̆m u such that pG, U, V̆q is k-MCM, satisfying |V̆i X
NG pU 1 q| “ |U 1 | ` k.
4 œ 1: In order to give a counter-example for condition 1, we want to find U 2 Ď Ui where U 1 Ă U 2 such that
|NG pU 1 q| ´ |U 1 | ě |NG pU 2 q| ´ |U 2 |. We can consider that NG pU 1 q Ă Vi . By condition 4, we have |V̆i X
NG pU 1 q| “ |NG pU 1 q| “ |U 1 | ` k. Let |NG pU 2 q| “ |NG pU 1 q| ` `1 and |U 2 | “ |U 1 | ` `2 . We have |NG pU 2 q| ´
|U 2 | “ |NG pU 1 q| ´ |U 1 | ` `1 ´ `2 . By choosing `1 “ `2 , we obtain |NG pU 1 q| ´ |U 1 | “ |NG pU 2 q| ´ |U 2 |p“ kq.

4 ñ 2: We suppose that there exists U 2 Ď Ui where |U 2 | “ |U 1 | such that NG pU 2 q Ă NG pU 1 q. Then, |NG pU 2 q| ă

|NG pU 1 q|, so we have |U 2 | ` k “ |U 1 | ` k “ |V̆i X NG pU 1 q| ą |V̆i X NG pU 2 q| and so k ą |V̆i X NG pU 2 q| ´ |U 2 |
which leads to a contradiction with the extended Hall theorem: k ď |V̆i X NG pU 2 q| ´ |U 2 |.
4 ñ 3: The graph GrU 1 Y pNG pU 1 q X V̆i sq is connected, otherwise |V̆i X NG pU 1 q| ´ |U 1 | ą k ˆ ` where ` is the number
of connected subgraphs in U 1 . We deduce that GrU 1 Y NG pU 1 qs is connected.

13
 / Procedia Computer Science 00 (2016) 1–22 14

5.2.3. Valid Inequalities

Recall that inequalities (42) give an upper bound of z considering each subset Ui P U “ tU1 , ..., Um u separately.
Now, we extend this family of inequalities by considering these subsets two by two, simultaneously. In the following
example, we can see the interest of this approach. Let U s , Ut P U, s ‰ t, suppose that |U s | “ |Ut | “ 2 and
NG pU s q “ NG pUt q with cardinality 4. Using inequalities (42), z is bounded by 2. However, it is straightforward that
z “ 0.
For any subsets U s1 Ď U s and Ut1 Ď Ut , we denote by NG pU s1 Ut1 q “ NG pU s1 q X NG pUt1 q the set of common
neighbors of U s1 and Ut1 . Let us consider ÑG pU s1 q “ NG pU s1 qzNG pU s1 Ut1 q the set of vertices belonging exclusively to
the neighborhood of U s1 . In the same way, we define ÑG pUt1 q “ NG pUt1 qzNG pU s1 Ut1 q.
Let us denote by
! ) ! )
k̃max “ max |ÑG pU s1 q| ´ |U s1 |, |ÑG pUt1 q| ´ |Ut1 | and k̃min “ min |ÑG pU s1 q| ´ |U s1 |, |ÑG pUt1 q| ´ |Ut1 |

upper bounds of the optimal solution for U s and Ut when considering only the exclusive neighborhoods. Then, it
is clear that the upper bound of the optimal solutions are less than or equal to k̃min ` |NG pU s1 Ut1 q|.
By considering the common neighborhood NG pU s1 Ut1 q, two cases have to be studied in order to know how vertices
of this set can complete ÑG pUt1 q and ÑG pU s1 q to give a better upper bound ksup for both sets.

1. k̃max ´ k̃min ě |NG pU s1 Ut1 q|: only one of the two subsets, ÑG pU s1 q or ÑG pUt1 q, can be completed with the common
vertices in such a way that ksup “ k̃min ` |NG pU s1 Ut1 q|.

2. k̃max ´ k̃min ă |NG pU s1 Ut1 q|: first, one of the two subsets, ÑG pU s1 q or ÑG pUt1 q, can be completed with k̃max ´ k̃min
1 1
common vertices; the´ remaining common vertices ¯ can complete both ÑG pU s q and ÑG pUt q equally. We deduce
that ksup “ k̃max ` |NG pU s1 Ut1 q| ´ pk̃max ´ k̃min q {2.

Let ` “ s if |ÑG pU s1 q| ´ |U s1 | ă |ÑG pUt1 q| ´ |Ut1 | and ` “ t otherwise.

Remark that, if in a solution a common vertex v P NG pU s1 Ut1 q is assigned to a subset Vi where i P Mzts, tu, this
vertex cannot be used to complete ÑG pU s1 q or ÑG pUt1 q. Then, ksup will be decreased by at least 1{2.
Furthermore, if in a solution a vertex v P ÑG pU`1 q is assigned to a subset Vi where i P Mzts, tu, this vertex cannot
be used to complete ÑG pU s1 q or ÑG pUt1 q. Then, ksup will be decreased by 1. Thus the following inequalities are valid
for all U s1 and Ut1 :

1 ÿ ÿ ÿ ÿ
z` xvi ` xvi ď k sup . (48)
2
vPNG pU s1 Ut1 q iPMzts,tu vPNG pU`1 q iPMzts,tu

6. Implementation and experimental results

In this section, we first present some strategies used to solve our problems. Then we explain the way we produced
some instances to test our approach, before analyzing the obtained results.

6.1. Resolution strategy

For both families of inequalities we propose a separation algorithm. For the first one, we also propose some
improvements. Then, we explain how our Branch-and-Cut algorithm is managed.

6.1.1. Separation Algorithm

|V|ˆm
Given a solution px˚ , z˚ q P R` ˆ R` , the separation problem for a family of inequalities consists in determin-
ing whether px˚ , z˚ q satisfies these inequalities and, if not, in finding one of these inequalities which is violated by
px˚ , z˚ q. An algorithm which solves this problem is called a separation algorithm associated with these inequalities.

14
 / Procedia Computer Science 00 (2016) 1–22 15

Separation of inequality (42). The number of inequalities (42) in pP1 q is exponential. Hence, a polynomial time
separation algorithm is necessary to allow using these inequalities inside a cutting plane algorithm. The equivalence
between separation and optimization in combinatorial optimization [4] implies that the linear relaxation of problem
|V|ˆm
pP1 q can be solved in polynomial time. Let px˚ , z˚ qřP R` ˆ R` be a solution of the linear relaxation. For all
i P t1, ..., mu, we want to find a set Ui P Ui such that vPNG pU 1 q xvi˚ ´ z˚ ă |Ui1 |.
1
i
We separate the problem in m sub-problems. Each sub-problem is associated with a single set Ui Ď U. In
the following, we consider the graph GrUi Y Vs. Let w : v Ñ R` be the weight function where wpvq “ xvi˚ for
all v P V.`řThe separationřproblem˘ consists in solving the integerřlinear program pP1 q with the objective function
i
z1 “ min vPV wpvqxv ´
1 ˚
uPUi xu . If z ă z then the inequality
1 1
vPNG pUi1 q xv ´ z ě |U i |, where U i is given by the
optimal solution of pP1 q, is violated when respecting px˚ , z˚ q. In this case we add the inequality associated with i and
Ui1 . Otherwise all inequalities (42) are verified.
It is possible that the added constraint does not define a facet. For this reason, we propose some improvements
according to the conditions 1 – 3 of Proposition 6.
ř
Improvement 1. If the resulting Ui1 does not respect condition 1, then there exists a set Ũi1 where vPNG pŨ 1 qzNG pU 1 q wpvq “
i i
|Ũi1 | and NG pŨi1 qzNG pUi1 q “ |Ũř1
i | which implies that wpvq “ 1, for all v P NG pŨ 1
i qzNG pU 1
i q. Thus, we aim to
maximize |Ui1 |. By subtracting uPU  xu from the objective function, where  is a small value, we ensure the
maximality of Ui1 (see Figure 5a).
Improvement 2. If the resulting Ui1 does not 2 2
ř respect condition 2, then there exists a set U Ď Ui with |Ui | “ |Ui |
1
2 1
such that NG pUi q Ă NG pUi q. Then, vPNG pU 1 qzNG pU 2 q wpvq “ 0.
i i

Thus, we aim to minimize |NG pUi1 q| (see Figure 5b). By adding vPV  xv to the objective function, where  is a
ř
small value, we ensure the minimality of NG pUi1 q.
Improvement 3. If GrUi1 Y NG pUi1 qs is not connected then, for each connected component, if the induced inequality
is violated, then we add it (see Figure 5c).

′′
Ui,1
Ui′ Ui′′
′′
Ũi′ Ui,2

Ui′

1 0
Ui′′ Ui′

(a) Improvement 1 (b) Improvement 2 (c) Improvement 3

Figure 5: Improvements of the separation algorithm

Separation of the inequality (48) . We propose a heuristic for solving the separation problem associated to inequality.
Let M 1 Ď M and U 1 “ tUi1 , i P M 1 u the set of sets found by the previous algorithm. This heuristic is based on the set
U 1 . Indeed, for all couples pUi1 , U 1j q P U 1 2 , if the inequality (48) associated with this couple is violated, then we add
it.

6.1.2. Branch-and-Cut Algorithm

In this section, we present a Branch-and-Cut algorithm for solving pP1 q. Our aim is to address the algorithmic
applications of the model and the theoretical results presented in the previous sections. To start the optimization, we
consider the linear program
maxtz|x P r0, 1smˆ|V| , z P N` , x satisfies (41)u.
An important task in the Branch-and-Cut algorithm is to determine whether or not an optimal solution of the linear
relaxation of the MBCMVIP is feasible. An optimal solution x˚ of the linear relaxation is feasible for the MBCMVIP
15
 / Procedia Computer Science 00 (2016) 1–22 16

if x˚ is integer and x˚ satisfies inequalities (42). Thus, whether or not x˚ is feasible for MBCMVIP can be verified
in polynomial time. If not, the Branch-and-Cut algorithm uses the inequalities (42) and (48) and their separations
are successively performed. We remark that all inequalities are global (i.e. valid in all the Branch-and-Cut tree) and
several inequalities may be added at each iteration.

6.2. Instances
We have produced our instances for the m-MBCMVIP, using the following parameters:
• m: the number of slots (2 or 5),
• nU : the size of Ui (10, 25, 50, 75),
• nV : the size of V (1.25 ˆ nU , 1.5 ˆ nU , 1.75 ˆ nU ),
• d: the density of the graph (10%, 20%, or 40% of nU ).
The generator of instances begins to build a matching and randomly completes the graph using two different
strategies.
First Generator. We consider a uniform degree distribution on V. This generator completes the graph by randomly
adding edges to ensure the uniformity of the distribution.
|E|
Second Generator. We consider a global density ( |U|ˆ|V| ) and the generator completes the graph by randomly adding
edges to ensure the global density.
For a better understanding of the results, we present the experiments on instances with a uniform partition of U:
|Ui | “ |U|{m for all i P t1, ..., mu. We randomly generated 5 instances for each set pm, nU , nV , dq of parameters, thus
obtaining 700 different instances.
All the tests have shown that these two strategies don’t have any influence on the obtained results. Thus, in the
following, for the sake of clarity, we will only present results on instances given by first generator. Indeed, the two
sets of instances lead to the same conclusions.

6.3. Results
All the models of BCMVIP and MBCMVIP are implemented in Java using CPLEX 12.6 solver, on an Intel core
i5 running at 3.4 GHz, with 8 GB of RAM.

6.3.1. Dual formulation

In Section 5.1 we proposed an improvement which goal was to reduce the size of the ILP, replacing U by Ũ.
We used our benchmark to investigate the efficiency of this method. Considering the high computing times of dual
formulation, we restricted our study to the 110 smallest instances of our benchmark. In the Table 1, we show the four
instances where the method effectively reduced the size of the ILP. The three first columns identify the instance. In
column 4 (resp. column 5) is indicated the computing time, in seconds, of the ILP without improvement (resp. with
improvement). In columns 6 and 7 are given the number of nodes of the branching tree for both variants. The last
column presents the number of nodes not considered in the dual formulation.

|U| |V| density CPU 1 CPU 2 No 1 No 2 |UzŨ|

50 62 10 2 2 0 0 1
50 62 10 0 1 0 0 5
50 62 10 0 0 0 0 1
50 75 10 1 2 0 0 1

Table 1: Analysis of the dual formulation improvement

The obvious conclusion is that this improvement is useless as less than 4% of the instances takes benefit of the
method. Moreover, the time spent to compute Ũ is too important regarding the gain on computing time. Remark that
in real-life applications, this improvement could be more efficient.
16
 / Procedia Computer Science 00 (2016) 1–22 17

6.3.2. Comparison between formulations

We proposed two formulations in sections 5.1 and 5.2; the goal of this section is to evaluate these models. Table 2
presents some results on the basic dual formulation and on the second formulation without improvement. Each line
represents five randomly generated instances, sharing the same parameters. The benchmark used is restricted to the
smallest instances, allowing to solve at least one instance over five, in less than one hour.
The three first columns identify the instance. In column 4 (resp. column 5) is indicated the average computing
times over the five instances, in seconds, of the dual formulation (resp. the second formulation). In columns 6 and 7
are given the average number of nodes of the branching tree for both variants. The last two columns present the ratio
of instances solved in less than one hour.

|U| |V| density CPU 1 CPU 2 No 1 No 2 opt 1 opt 2

50 62 10 14 0 494.6 0 5/5 5/5
50 62 20 429.8 1.4 254.4 9.8 5/5 5/5
50 62 40 1428 0 566.4 0 5/5 5/5
50 75 10 2.8 0.6 0 0 5/5 5/5
50 75 20 123.8 2.6 553.2 4.6 5/5 5/5
50 75 40 1926.6 1.6 708.8 2.6 4/5 5/5
50 87 10 3.6 0.6 18.6 0 5/5 5/5
50 87 20 379 3 330.4 11.8 5/5 5/5
50 87 40 2298.4 4 462.8 1562.6 2/5 5/5
100 125 10 1241.8 4 44.2 6 4/5 5/5
100 125 20 3234.2 19.6 69.4 11480.6 2/5 5/5

Table 2: Comparison of the two formulations

The second formulation allows to solve all instances in less than 50 seconds, whereas the dual formulation only
solves 48 instances over 55. Furthermore, the computing times of the dual formulation is far greater. The standard
deviation of the number of nodes in the branching tree for the dual formulation is smaller than in the second formula-
tion. As the second formulation leads to models considering less variables, the computing times and memory amount
needed to solve are better than the ones for the dual formulation.
In the next experimental results, we focus on the second formulation and its improvements.

6.3.3. Second formulation

In this section, we focus on the second formulation and the different improvements proposed in previous sections.
In a first part, we present an analysis of computing times for some instances. We have excluded instances with
small density, for which the computing times are too tiny to expect any improvement. The execution time results are
represented by grouped bar charts in Figures 6 and 7, for various densities and graph sizes.
Each instance have been solved using inequalities (42), and adding one or a combination of the following variants:
• with no improvement,
• with improvement 1,

• with improvements 2,
• with improvements 3,
• using inequalities (48).
The 5 cases above are labeled from imprv 0 to imprv 4.

17
 / Procedia Computer Science 00 (2016) 1–22 18

We have first studied the improvements for 2 slots. the results are presented on Figure 6.

2 slots – density 0.1 – gen 1 2 slots – density 0.1 – gen 1

50 50
(sec)

(sec)
40 40

30 30
time

time
20 20
CPU

CPU
10 10

0 0
100×125 100×150 100×175 150×187 150×225 150×262 100×125 100×150 100×175 150×187 150×225 150×262
degree = 10 degree = 15 degree = 10 degree = 15

number of edges number of edges

2 slots – density 0.2 – gen 1 2 slots – density 0.2 – gen 1

150 150

125 125
(sec)

(sec)
100 100
time

time

75 75

50 50
CPU

CPU

25 25

0 0
100×125 100×150 100×175 150×187 150×225 100×125 100×150 100×175 150×187 150×225
degree = 20 degree = 30 degree = 20 degree = 30

number of edges number of edges

2 slots – density 0.4 – gen 1 2 slots – density 0.4 – gen 1

70 70
60 60
(sec)

(sec)

50 50
time

time

40 40
30 30
CPU

CPU

20 20
10 10
0 0
100×125 100×150 100×175 150×187 150×225 100×125 100×150 100×175 150×187 150×225
degree = 40 degree = 60 degree = 40 degree = 60

number of edges number of edges

imprv 0 imprv 1 imprv 2 imprv 3 imprv 4 imprv 0 imprv 12 imprv 14 imprv 24 imprv 124

Figure 6: Execution time results for 2 slots

On the left side we show the results obtained by testing each improvement individually; on the right side we
combined the different improvements. Considering the results for individual improvements, we can observe that, with
a small density, the various improvements lead to slower computing times. Nevertheless, for degree 15 we observe
that the improvement 4 leads to better computing times. For medium densities, improvement 4 also decreases the
computing times, whereas improvements 1 and 2 are better for higher densities. Improvement 3 has no real influence
on the computing times for our benchmark. Considering combined improvements, improvement 3 not being relevant,
we studied the combination of improvements 1, 2 and 4. As seen earlier, with small densities, it is better to use
no improvement. For medium densities, none of the combinations achieves to give better computing times than
improvement 4. Combinations are really efficient when solving high density graphs, but none of them are suitable for
all instances.

18
 / Procedia Computer Science 00 (2016) 1–22 19

On five slots (Figure 7), the efficiency of improvements is limited to high density instances. Moreover, one can
remark that the inequalities (48) are more efficient for 5 slots than for 2 slots with high densities. Indeed, the number
of inequalities is greater for 5 slots (5 choose 2). For small and medium densities, the different improvements never
achieve to give better computing times.

5 slots – density 0.1 – gen 1 5 slots – density 0.1 – gen 1

12 12
(sec)

(sec)
9 9
time

time
6 6

3 3
CPU

CPU
0 0
125×156 125×187 125×218 125×156 125×187 125×218
degree = 12 degree = 12

number of edges number of edges

5 slots – density 0.2 – gen 1 5 slots – density 0.2 – gen 1

250 250
(sec)

(sec)
200 200
time

time
150 150
100 100
CPU

CPU
50 50
0 0
125×156 125×218 250×312 125×156 125×218 250×312
degree = 25 degree = 50 degree = 25 degree = 50

number of edges number of edges

5 slots – density 0.4 – gen 1 5 slots – density 0.4 – gen 1

700 700
(sec)

(sec)

600 600
500 500
time

time

400 400
300 300
200 200
CPU

CPU

100 100
0 0
125×187 125×218 250×312 250×375 375×468 375×562 125×187 125×218 250×312 250×375 375×468 375×562
degree = 50 degree = 100 degree = 150 degree = 50 degree = 100 degree = 150

number of edges number of edges

imprv 0 imprv 1 imprv 2 imprv 3 imprv 4 imprv 0 imprv 12 imprv 14 imprv 24 imprv 124

Figure 7: Execution time results for 5 slots

We also tested our algorithm on bigger instances, with more vertices and edges. Figure 8 shows the computing
times for nine families of five instances with size between 300 ˆ 420 to 500 ˆ 800 and five slots. Tests using
density 0.4 (resp. 0.5) are on the left side (resp. right size). Many big instances can be solved in less than one hour.
Nevertheless, the efficiency of our algorithm mainly depends on the density of the graphs. Indeed, with density 0.5, all
instances are solved in less than 550 seconds, whereas with density 0.4, 10 over 45 instances are not solved within one
hour. For higher densities, the improvements are more efficient, whereas when considering small densities, applying
improvements has a negative impact.

19
 / Procedia Computer Science 00 (2016) 1–22 20

5 slots – density 0.4 – gen 1 5 slots – density 0.5 – gen 1

3,600 500

3,000
400
(sec)

(sec)
2,400
300
time

time
1,800
200
CPU

CPU
1,200

100
600

0 0
300×420 300×450 300×480 400×560 400×600 400×640 500×700 500×750 500×800 300×420 300×450 300×480 400×560 400×600 400×640 500×700 500×750 500×800
degree = 120 degree = 160 degree = 200 degree = 150 degree = 200 degree = 250

number of edges number of edges

0 imprv 1 imprv 2 imprv 4 imprv

Figure 8: Execution time results for big instances on 5 slots

In this end of section, we focus our analyze on the biggest instances of our tests; details are presented in Tables 3
and 4. The entries in these tables are:

δv : the degree of all v P V (given by the first generator, the average value for the second generator),
|U| : the size of U,
|V| : the size of V,
imprv : the associated improvement,
CPU : the total CPU time in seconds,
Ct(42) : the number of generated inequalities (42),
Ct(48) : the number of generated inequalities (48),
No : the number of generated nodes in the Branch-and-Cut or Branch-and-Bound tree.
Table 3 shows the results for instances generated using a density of 0.4. After having focused on computing times
in previous analyze we will now give more attention to the number of generated inequalities and the size of search
space. Firstly, we can remark that the number of nodes in the branching tree (given in the last column) is not correlated
with the improvements proposed in the previous section. Indeed, in most cases the number of nodes is similar but we
also have some instances showing big variations. Furthermore, we denote that the number of nodes is relatively small
with respect to the size of instances. This shows the efficiency of our algorithm in terms of memory usage. Secondly,
our algorithm finds an exact solution using only few inequalities (less than 250), which implies CPU and memory
performances. The results also show that our improvements do not systematically reduce the number of constraints,
whereas improvements 1 and 2 theoretically should strengthen the inequalities Ct(42) . We cannot give any explanation
to that, we hope that this theoretical strengthen will be effective for real life instances. Indeed, in real life instances
the graph structure should help our algorithm.
Table 4 shows the results for instances generated using a density of 0.5. Firstly, denote that all instances are solved
in less than 10 minutes. Secondly, comparing to the results of table 3, the branching tree size is even smaller (less than
2). Furthermore, the size of the instances does not influence the number of nodes. Finally, the number of inequalities
generated by the branch-and-cut (Ct(42) , Ct(48) ) is always less than 25; this proves the strength of our inequalities as
only a small amount of them is needed to solve the instances. Thus, we can conclude that our algorithm is well fitted
for high density graphs.
Remark that for the two different densities, the branch-and-cut always generates 10 inequalities Ct(48) correspond-
ing to 5 choose 2 for all instances. This implies that the first added inequality for 2 specific slots dominates all next
inequalities generated by the associated separation algorithm. It can be explained by the lack of efficiency of our
separation heuristic. We aim to improve this in future works.

20
 / Procedia Computer Science 00 (2016) 1–22 21

δv |U| |V| imprv CPU Ct(42) Ct(48) No δv |U| |V| imprv CPU Ct(42) Ct(48) No
0 77.2 14.2 1.6 0 47.6 6.8 1.4
1 65.6 13.0 1.6 1 51.2 6.8 1.4
420 420
2 93.6 14.6 2.4 2 52.6 6.8 1.4
4 82.6 14.4 10.0 2.4 4 47.2 6.4 10.0 1.0
0 355.6 62.0 40.8 0 50.2 9.6 1.0
1 374.0 61.2 39.0 1 56.0 9.6 1.0
120 300 450 150 300 450
2 607.4 65.8 41.6 2 60.6 9.6 1.0
4 359.6 60.8 10.0 35.0 4 59.0 9.6 10.0 1.2
0 1105.6 180.6 232.0 0 88.8 11.0 1.2
1 1482.4 228.6 1173.8 1 93.6 11.0 1.2
480 480
2 1438.2 203.6 427.6 2 109.0 11.2 1.4
4 1159.4 193.6 10.0 233.6 4 87.0 10.8 10.0 1.6
0 168.2 11.0 1.2 0 134.0 6.4 1.2
1 164.0 11.6 1.4 1 140.0 6.4 1.2
560 560
2 225.0 11.8 1.2 2 149.0 6.4 1.2
4 174.2 12.4 10.0 1.4 4 136.0 7.2 10.0 1.0
0 809.8 46.4 24.2 0 145.0 9.8 1.4
1 986.8 48.4 32.6 1 171.2 9.8 1.4
160 400 600 200 400 600
2 1129.2 46.6 23.6 2 163.8 9.8 1.4
4 864.6 46.6 10.0 23.8 4 141.4 9.2 10.0 1.0
0 ą1h 223.8 430.6 0 233.4 10.4 1.8
1 ą1h 225.8 459.4 1 242.0 10.2 1.2
640 640
2 ą1h 214.6 340.6 2 225.0 10.2 1.2
4 ą1h 232.6 10.0 324.6 4 187.2 10.2 10.0 1.0
0 322.6 10.6 1.2 0 302.6 6.4 1.2
1 361.2 10.8 1.2 1 358.0 6.4 1.2
700 700
2 359.6 10.8 1.2 2 309.0 6.4 1.2
4 402.8 12.0 10.0 1.6 4 304.0 6.2 10.0 1.0
0 1593.6 43.0 19.2 0 303.4 8.2 1.2
1 1999.6 42.0 17.6 1 404.8 8.2 1.0
200 500 750 250 500 750
2 2557.6 43.6 18.2 2 347.2 8.2 1.2
4 1937.4 46.8 10.0 22.0 4 316.2 7.8 10.0 1.0
0 ą1h 96 69.8 0 436.2 10.2 1.2
1 ą1h 99 65.6 1 520.0 10.2 1.2
800 800
2 ą1h 93 68.8 2 480.2 10.2 1.4
4 ą1h 98 10.0 59.6 4 472.0 10.4 10.0 1.0

Table 3: 5 slots – density 0.4 – generator 1 Table 4: 5 slots – density 0.5 – generator 1

7. Concluding remarks

In this paper, we have introduced two new problems. The first one (BCMVIP) consists in finding the maximum
number of vertices in a bipartite graph that can be removed such that a complete matching still remains. It has
been shown to be polynomial thanks to the integrality property of the associated polytope. This result is based on
our generalized Hall theorem. The second problem (MBCMVIP) deals with partitioned sets of vertices. Its NP-
completeness has been shown and two mathematical formulations have been proposed and compared. Then, a deeper
study has been conducted for the best one. A polyhedral analysis allowed to strengthen the model. Experimental
results have shown that the proposed improvements can lead to better results in some cases but no generalization can
be done.
In future work, we aim to generalize inequalities (48) to more than two subsets, propose a dedicated separation
algorithm and study a variant of the problem taking into account priorities on some subsets of vertices or considering
incompatibility constraints.

21
 / Procedia Computer Science 00 (2016) 1–22 22

References
[1] D. S. Altner, Ö. Ergun and N. A. Uhan The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approxima-
bility, Operations Research Letters, 38(1), 33-38, 2010.
[2] C. Bazgan, S. Toubaline, D. Vanderpooten, Critical edges/nodes for the minimum spanning tree problem: complexity and approximation,
Journal of Combinatorial Optimization, 26(1), 178-189, 2013.
[3] J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards, 69B, 125-130,
1965.
[4] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 169-197,
1981.
[5] P. Hall, A Contribution to the Theory of Groups of Prime-Power Order, Proceedings of the London Mathematical Society, 29-07, 1934.
[6] L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf and J. Zhao, On Short Paths Interdiction Problems: Total and
Node-Wise Limited Interdiction , Theory of Computing Systems, 43(2), 204-233, 2008.
[7] P. Laroche, F. Marchetti, S. Martin and Z. Roka, Bipartite Complete Matching Vertex Interdiction Problem: Application to Robust Nurse
Assignment. IEEE International Conference on Control, Decision and Information Technologies (CoDIT’14), Metz, 3-5 Novembre, 2014,
France. IEEE Conference Publications. DOI: 10.1109/CoDIT.2014.6996890, pages 182 ? 187 (2014)
[8] L. Lovász and M. D. Plummer, Matching theory, North-Holland, 1986.
[9] X. Lu, D.-W. Wang and C.K. Wong, The strong Hall property and symmetric chain orders, Discrete Mathematics, 203 (1-3), 161-168, 1999.
[10] H. Poincaré, Second complement l’analysis situs, Proc. London Math. Soc., 32, 277-308, 1901.
[11] R. Zenklusen, B. Ries, C. Picouleau, D. de Werra, M.-C. Costa and C. Bentz, Blockers and transversals, Discrete Mathematics, 309, pp.
4306-4314, 2009.
[12] R. Zenklusen, Matching interdiction, Discrete Applied Mathematics, 158, 1676-1690, 2010.
[13] R. Zenklusen, A Short Note on the NP-Completeness of Node-Wise Limited Matching Interdiction, Technical report, 2012.

22