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

DOI10.1007/978-3-540-77120-3_25MaRDI QIDQ5387763zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• The complexity of König subgraph problems and above-guarantee vertex cover
• On maximum matchings in König-Egerváry graphs
• König Deletion Sets and Vertex Covers above the Matching Size
• Tractability of König edge deletion problems
• Paths, flowers and vertex cover

Cites work

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

Cited in

(12)

• Parameterizing above or below guaranteed values
• Almost 2-SAT is fixed-parameter tractable
• Tractability of König edge deletion problems
• Backdoors to satisfaction
• Paths, flowers and vertex cover
• König Deletion Sets and Vertex Covers above the Matching Size
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
• Efficiently recognizing graphs with equal independence and annihilation numbers
• Vertex cover problem parameterized above and below tight bounds
• The complexity of König subgraph problems and above-guarantee vertex cover
• On the parameterized vertex cover problem for graphs with perfect matching

This page was built for publication: The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387763)