The complexity of König subgraph problems and above-guarantee vertex cover
A graph is called 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 extensively studied from a graph-theoretic point of view. The authors introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. They show that different problems in this context are NP-complete.
scientific article; zbMATH DE number 5988465
scientific article