The complexity of König subgraph problems and above-guarantee vertex cover (Q652520)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The complexity of König subgraph problems and above-guarantee vertex cover |
scientific article |
Statements
The complexity of König subgraph problems and above-guarantee vertex cover (English)
0 references
14 December 2011
0 references
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.
0 references
vertex cover
0 references
above guarantee vertex cover
0 references
König graphs
0 references
König vertex/edge deletion sets
0 references
maximum matching
0 references
parameterized complexity
0 references
approximation algorithms
0 references
unique game conjecture
0 references
