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 \(\varDelta (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 \(\varDelta (G) \le \varDelta \) for some constant \(\varDelta \in \mathbb {Z}_{\ge 1}\) . We also show that the problem of computing \(\varDelta (G)\) admits an FPT algorithm. We also establish further results on \(\varDelta (G)\) when G is a forest.