Tractability of Konig Edge Deletion Problems
A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if a graph has a set of at most k edges whose deletion results in a Konig graph. While the vertex deletion version of this problem was shown to be fixed-parameter tractable (FPT) more than a decade ago, the fixed-parameter tractability status of Konig Edge Deletion has remained open since then. It has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. In addition, we prove that a variant of this problem, where we are given a graph G and a maximum matching M, and we want a Konig edge deletion set of size at most k that is disjoint from M, is fixed-parameter tractable. This is based on a joint work with Rian Neogi, Venkatesh Raman, and S. Vaishali. This work has been published in Theoretical Computer Science (DOI link: https://doi.org/10.1016/j.tcs.2019.09.011).