Sammanfattning En graf är König-Egerváry om storleken på ett minsta vertex omslag är lika med en maximal matchning i grafen. Dessa grafer har studerats ingående ur graf-teoretisk synvinkel. I detta dokument introducerar och studerar vi den algoritmiska komplexiteten i att hitta König-Egerváry subgrafer i en given graf. I synnerhet, med tanke på en graf G och ett icke-negativt heltal k, är vi intresserade av följande frågor: 1. Finns det en uppsättning k hörn (kanter) vars radering gör grafen König-Egerváry? 2. Finns det en uppsättning k hörn (kanter) som framkallar en König-Egerváry subgraph? Vi visar att dessa problem är NP-kompletterade och studerar deras komplexitet med avseende på tillnärmning och parameteriserad komplexitet. I detta syfte studerar vi först den algoritmiska komplexiteten hos ABOVE GUARANTEE VERTEX COVER, där man är intresserad av att minimera det ytterligare antal hörn som behövs utöver den maximala matchningsstorleken för vertex omslaget. Samtidigt som vi studerar den parameteriserade komplexiteten i problemet med att ta bort k hörn för att få en König-Egerváry graf, visar vi ett antal intressanta strukturella resultat på matchningar och vertex omslag som kan vara användbara i andra sammanhang.
Vårt arbete är nära relaterat till Mishra et al. REF om problem med vertex- och kantremoval för egenskapen König-Egerváry graf.
The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}