| Article ID: | iaor201110811 |
| Volume: | 61 |
| Issue: | 4 |
| Start Page Number: | 857 |
| End Page Number: | 881 |
| Publication Date: | Dec 2011 |
| Journal: | Algorithmica |
| Authors: | Raman Venkatesh, Saurabh Saket, Sikdar Somnath, Mishra Sounaka, Subramanian R |
| Keywords: | analysis of algorithms, complexity, graphical methods, NP-complete, vertex cover |
A graph is König‐Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. 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 König‐Egerváry subgraphs of a given graph. In particular, given a graph