The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number.

The class of graphs where the size of a minimum vertex cover equals that of a maximum matching is known as König-Egerváry graphs. These graphs have been studied extensively from a graph theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding maximum König-Egerváry subgraphs of a given graph. More specifically, we look at the problem of finding a minimum number of vertices or edges to delete to make the resulting graph König-Egerváry. We show that both these versions are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. En route, we point out an interesting connection between the vertex deletion version and the Above Guarantee Vertex Cover problem where one is interested in the parameterized complexity of the Vertex Cover problem when parameterized by the ‘additional number of vertices' needed beyond the matching size. This connection is of independent interest and could be useful in establishing the parameterized complexity of Above Guarantee Vertex Cover problem. [ABSTRACT FROM AUTHOR]
Copyright of Algorithms & Computation (978-3-540-77118-0) is the property of Springer eBooks and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)