The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number

DOI10.1007/978-3-540-77120-3_25zbMath1193.05133OpenAlexW1772739528MaRDI QIDQ5387763

Venkatesh Raman, C. R. Subramanian, Saket Saurabh, Sounaka Mishra, Somnath Sikdar

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Backdoors to Satisfaction, On the parameterized vertex cover problem for graphs with perfect matching, Efficiently recognizing graphs with equal independence and annihilation numbers, Vertex cover problem parameterized above and below tight bounds, Parameterizing above or below guaranteed values, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition, Almost 2-SAT is fixed-parameter tractable

Cites Work

• Unnamed Item
• Unnamed Item
• On approximating minimum vertex cover for graphs with perfect matching
• A characterization of the graphs in which the transversal number equals the matching number
• Finding odd cycle transversals.
• On the hardness of approximating minimum vertex cover
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Approximation Algorithms for Steiner and Directed Multicuts
• Parameterizing MAX SNP Problems Above Guaranteed Values
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Improved Parameterized Upper Bounds for Vertex Cover