The complexity of König subgraph problems and above-guarantee vertex cover

DOI10.1007/S00453-010-9412-2zbMath1243.05203OpenAlexW2085312445MaRDI QIDQ652520

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

Publication date: 14 December 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.435.1176

zbMATH Keywords

maximum matchingapproximation algorithmsvertex coverparameterized complexityKönig graphsabove guarantee vertex coverKönig vertex/edge deletion setsunique game conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

König graphs for 3-paths and 3-cycles ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Stabilizing Network Bargaining Games by Blocking Players ⋮ On approximability of optimization problems related to red/blue-split graphs ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Note on maximal bisection above tight lower bound ⋮ Additive stabilizers for unstable graphs ⋮ Finding small stabilizers for unstable graphs ⋮ Unnamed Item ⋮ Research on solution space of bipartite graph vertex-cover by maximum matchings ⋮ Graph Stabilization: A Survey ⋮ Stabilizing network bargaining games by blocking players ⋮ Faster graph bipartization ⋮ Stabilizing Weighted Graphs ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ A characterization of König-Egerváry graphs with extendable vertex covers ⋮ Tractability of König edge deletion problems ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4

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
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• Parameterized complexity of finding regular induced subgraphs
• Almost 2-SAT is fixed-parameter tractable
• Ear-decompositions of matching-covered graphs
• Matching theory
• Testing for Equality between Maximum Matching and Minimum Node Covering
• 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}\)
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Approximation Algorithms for Steiner and Directed Multicuts
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Measure and conquer
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Edge Dominating Sets in Graphs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On hard instances of approximate vertex cover

This page was built for publication: The complexity of König subgraph problems and above-guarantee vertex cover