On the hardness of approximating minimum vertex cover
From MaRDI portal
Publication:816330
DOI10.4007/annals.2005.162.439zbMath1084.68051OpenAlexW2143698439WikidataQ56338020 ScholiaQ56338020MaRDI QIDQ816330
Publication date: 10 March 2006
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://projecteuclid.org/euclid.annm/1134073588
Related Items
Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Lipschitz bijections between boolean functions, Tracking Paths, Approximating Bounded Degree Deletion via Matroid Matching, Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, New Complexity Results and Algorithms for the Minimum Tollbooth Problem, Testing Consumer Rationality Using Perfect Graphs and Oriented Discs, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, Angle Covers: Algorithms and Complexity, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Vertex isoperimetry and independent set stability for tensor powers of cliques, Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem, Reinforcement learning for combinatorial optimization: a survey, Inapproximability of $H$-Transversal/Packing, Tight Localizations of Feedback Sets, r$r$‐Cross t$t$‐intersecting families via necessary intersection points, Pseudorandom sets in Grassmann graph have near-perfect expansion, On the geometric priority set cover problem, Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm, Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas, Unnamed Item, Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, Variable neighborhood search approach with intensified shake for monitor placement, A combinatorial branch and bound for the safe set problem, Intersection theorems for \((- 1, 0, 1)\)-vectors, Mathematics of computation through the lens of linear equations and lattices, Strong stability of 3-wise \(t\)-intersecting families, The Approximability of Partial Vertex Covers in Trees, High dimensional Hoffman bound and applications in extremal combinatorics, The maximum measure of 3-wise \(t\)-intersecting families, The Greedy Algorithm and the Cohen-Macaulay Property of Rings, Graphs and Toric Projective Curves, Unnamed Item, Unnamed Item, Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem, Quantitative relation between noise sensitivity and influences, A Note on Large H-Intersecting Families, The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, On percolation and ‐hardness, Regular Language Constrained Sequence Alignment Revisited, Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames, Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects, Vertex Cover in Graphs with Locally Few Colors, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Semi-Strong Colouring of Intersecting Hypergraphs, The multi‐integer set cover and the facility terminal cover problem, Unnamed Item, The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification, The k-Observer Problem on d-regular Graphs, Approximating the discrete time-cost tradeoff problem with bounded depth, Some graph optimization problems with weights satisfying linear constraints, Vertex deletion on split graphs: beyond 4-hitting set, Approximating the discrete time-cost tradeoff problem with bounded depth, Definable Inapproximability: New Challenges for Duplicator, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, Stabilizing Weighted Graphs, Distributed set cover approximation: Primal-dual with optimal locality, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINES, Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses, Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs, Approximating Partially Bounded Degree Deletion on Directed Graphs, Cross t-Intersecting Integer Sequences from Weighted Erdős–Ko–Rado, Popularity, Mixed Matchings, and Self-Duality, Partially Symmetric Functions Are Efficiently Isomorphism Testable, Unnamed Item, An extension of the Erdős–Ko–Rado Theorem, Exact and Approximate Algorithms for Movement Problems on (Special Classes of) Graphs, Pipeline Interventions, Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover, Vertex cover meets scheduling, More complete intersection theorems, The weighted complete intersection theorem, Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Models of greedy algorithms for graph problems, Component-cardinality-constrained critical node problem in graphs, Safe sets in graphs: graph classes and structural parameters, Fuzzy covering problem of fuzzy graphs and its application to investigate the Indian economy in new normal, Complexity of approximating CSP with balance/hard constraints, Parameterized complexity and approximation issues for the colorful components problems, Multiply-intersecting families revisited, Exact and approximate algorithms for movement problems on (special classes of) graphs, Covering problem on fuzzy graphs and its application in disaster management system, On graphs whose eternal vertex cover number and vertex cover number coincide, A primal-dual approximation algorithm for \textsc{minsat}, Approximation and hardness results for the maximum edge \(q\)-coloring problem, On approximability of optimization problems related to red/blue-split graphs, Critical edges/nodes for the minimum spanning tree problem: complexity and approximation, Improved approximation of linear threshold functions, Diversity of uniform intersecting families, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, Sunflowers and testing triangle-freeness of functions, Approximability of the vertex cover problem in power-law graphs, Approximation for vertex cover in \(\beta\)-conflict graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Tracking paths, The junta method in extremal hypergraph theory and Chvátal's conjecture, On inverse traveling salesman problems, Finding small stabilizers for unstable graphs, Vertex cover in conflict graphs, Approximation algorithms and hardness results for labeled connectivity problems, Local search is a PTAS for feedback vertex set in minor-free graphs, Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems, Towards faster local search for minimum weight vertex cover on massive graphs, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, Greed is good for deterministic scale-free networks, New techniques for approximating optimal substructure problems in power-law graphs, On Nash-solvability in pure stationary strategies of the deterministic \(n\)-person games with perfect information and mean or total effective cost, Complexity and lowers bounds for power edge set problem, A simple reduction from a biased measure on the discrete cube to the uniform measure, On cross \(t\)-intersecting families of sets, On a biased edge isoperimetric inequality for the discrete cube, Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Beyond rankings: comparing directed acyclic graphs, Flip distance between triangulations of a planar point set is APX-hard, Wildlife corridors as a connected subgraph problem, An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families, Towards a proof of the Fourier-entropy conjecture?, On computing the minimum 3-path vertex cover and dissociation number of graphs, Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem, The complexity of König subgraph problems and above-guarantee vertex cover, Approximating integer programs with positive right-hand sides, On short paths interdiction problems: Total and node-wise limited interdiction, The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut, Rounding to an integral program, Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks, The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture, Complexity and inapproximability results for the power edge set problem, Improved and simplified inapproximability for \(k\)-means, Lift \& project systems performing on the partial-vertex-cover polytope, On optimal approximability results for computing the strong metric dimension, Multi-criteria approximation schemes for the resource constrained shortest path problem, The critical node detection problem in networks: a survey, The 0-1 inverse maximum stable set problem, The price of optimum: complexity and approximation for a matching game, Minimum vertex cover in ball graphs through local search, Combination of parallel machine scheduling and vertex cover, A multiply intersecting Erdős-Ko-Rado theorem -- the principal case, Set systems without a simplex or a cluster, A better list heuristic for vertex cover, Inapproximability of maximal strip recovery, Noise stability of functions with low influences: invariance and optimality, Min sum clustering with penalties, Fixed-parameter tractability results for feedback set problems in tournaments, Minimum \(k\)-path vertex cover, On the minimum vertex cover of generalized Petersen graphs, Exact localisations of feedback sets, The ordered covering problem, Stability versions of Erdős-Ko-Rado type theorems via isoperimetry, Approximability of clique transversal in perfect graphs, An efficient local search framework for the minimum weighted vertex cover problem, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, Approximation algorithm for stochastic set cover problem, Routing to reduce the cost of wavelength conversion, Single machine precedence constrained scheduling is a Vertex cover problem, Upper and lower degree-constrained graph orientation with minimum penalty, Vertex and edge covers with clustering properties: Complexity and algorithms, Strong and weak edges of a graph and linkages with the vertex cover problem, Hardness of edge-modification problems, AK-type stability theorems on cross \(t\)-intersecting families, Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames, Concentration on the Boolean hypercube via pathwise stochastic analysis, Optimization in business strategy as a part of sustainable economic growth using clique covering of fuzzy graphs, The \(k\)-separator problem: polyhedra, complexity and approximation results, Degree-constrained graph orientation: maximum satisfaction and minimum violation
