Total Matching and Subdeterminants

In the total matching problem, one is given a graph $G$ with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incident union of a stable set and a matching. We consider the natural formulation of the problem as an integer program (IP), with variables corresponding to vertices and edges. Let $M=M(G)$ denote the constraint matrix of this IP. We define $\mathrm{\Delta }(G)$ as the maximum absolute value of the determinant of a square submatrix of $M$. We show that the total matching problem can be solved in strongly polynomial time provided $\mathrm{\Delta }(G)\le \mathrm{\Delta }$ for some constant $\mathrm{\Delta }\in {\mathbb{Z}}_{\ge 1}$. We also show that the problem of computing $\mathrm{\Delta }(G)$ admits an FPT algorithm. We also establish further results on $\mathrm{\Delta }(G)$ when $G$ is a forest.