Luca Ferrarini: A journey through the Total Matching Problem

Speaker: Luca Ferrarini

Room: A707

Date: 02/12/2024 14:00

Abstract:

A total matching of a graph G = (V, E) is a subset of G such that its elements, i.e. vertices
and edges, are pairwise not adjacent. In this context, the Total Matching Problem calls for
a total matching of maximum size. This problem generalizes both the Stable Set Problem,
where we look for a stable set of maximum size, and the Matching Problem, where instead
we look for a matching of maximum size. In this talk, we present a polyhedral approach to
the Total Matching Problem, and hence, we introduce the corresponding polytope, namely
the Total Matching Polytope. To this end, we will present several families of nontrivial valid
inequalities that are facet-defining for the Total Matching Polytope. In addition, we provide a
first linear complete description for trees and complete bipartite graphs. For the latter family,
the complete characterization is obtained by projecting a higher-dimension polytope onto the
original space. This leads to an extended formulation of compact size for the Total Matching
Polytope of complete bipartite graphs. In the second part of the talk, we examine the natural
integer programming formulation of the problem through the prism of subdeterminants. First,
we focus on the case of forests. We give an alternative characterization of the maximum
subdeterminant ∆ of the constraint matrix, as well as an approximation of ∆. Then, we
switch to general graphs and give an FPT algorithm for computing ∆. Finally, we show that
the total matching problem can be solved in strongly polynomial time when ∆ is bounded by
a constant.