On the Computational Complexity of the Bipartizing Matching Problem

Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza +1

We study the problem of determining whether a given graph~$G=(V,E)$ admits a matching~$M$ whose removal destroys all odd cycles of~$G$ (or equivalently whether~$G-M$ is bipartite).…