The complexity of König subgraph problems and above-guarantee vertex cover
type: Item
instance of: scholarly article
title: The complexity of König subgraph problems and above-guarantee vertex cover
zbMATH Open document ID: 1243.05203
author: Sounaka Mishra
author: Venkatesh Raman
author: Saket Saurabh
author: Somnath Sikdar
author: C. R. Subramanian
published in: Algorithmica
publication date: 2011-12-14T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
review text: 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.
reviewed by: Arnfried Kemnitz
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5988465
zbMATH Keywords: vertex cover
zbMATH Keywords: above guarantee vertex cover
zbMATH Keywords: König graphs
zbMATH Keywords: König vertex/edge deletion sets
zbMATH Keywords: maximum matching
zbMATH Keywords: parameterized complexity
zbMATH Keywords: approximation algorithms
zbMATH Keywords: unique game conjecture
MaRDI profile type: Publication
OpenAlex ID: W2085312445
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: König-Egerváry graphs, 2-bicritical graphs and fractional matchings
cites work: Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
cites work: On approximating minimum vertex cover for graphs with perfect matching
cites work: Independence numbers of graphs - an extension of the Koenig-Egervary theorem
cites work: On the hardness of approximating minimum vertex cover
cites work: Measure and conquer
cites work: Testing for Equality between Maximum Matching and Minimum Node Covering
cites work: Edge Dominating Sets in Graphs
cites work: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: On the power of unique 2-prover 1-round games
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Approximation Algorithms for Steiner and Directed Multicuts
cites work: Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
cites work: Ear-decompositions of matching-covered graphs
cites work: Matching theory
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Parameterized complexity of finding regular induced subgraphs
cites work: Q4856179
cites work: Q5710169
cites work: Almost 2-SAT is fixed-parameter tractable
cites work: Finding odd cycle transversals.
cites work: A characterization of the graphs in which the transversal number equals the matching number
cites work: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
cites work: On hard instances of approximate vertex cover
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1007/S00453-010-9412-2
description: scientific article; zbMATH DE number 5988465