Vertex cover problem

Vertex cover problem
Fschwarzentruber · CC BY-SA 4.0 · source
Name	Vertex cover problem
Input	An undirected graph
Output	A subset of vertices covering all edges
Complexity	NP-complete

Vertex cover problem The vertex cover problem asks for a minimum-cardinality subset of vertices in an undirected graph that touches every edge. It originates in graph theory and combinatorial optimization and connects to foundational results in computational complexity and algorithm design. The problem has deep ties to landmark concepts and problems studied in theoretical computer science and discrete mathematics.

Definition

A vertex cover of an undirected graph G = (V, E) is a subset C ⊆ V such that every edge in E has at least one endpoint in C. The decision variant asks whether there exists a vertex cover of size at most k for given integer k; the optimization variant seeks a minimum-cardinality cover. The problem is closely related to the Independent set problem and the Maximum matching problem by classical reductions and dualities. Instances arise from representations studied by researchers at institutions such as Bell Labs and in conferences like STOC and FOCS.

Computational complexity

The decision version is one of Karp's 21 NP-completeness results and is NP-complete via reduction from problems like 3-SAT and Vertex cover reduction techniques used in canonical hardness proofs. As an NP-complete problem it is unlikely to admit polynomial-time exact algorithms unless P versus NP problem is resolved in favor of P = NP. Hardness results also include inapproximability bounds proven using techniques related to the Probabilistically Checkable Proofs framework and reductions from Label Cover and other central problems studied at venues such as ICALP and SODA.

Algorithms and approximations

Polynomial-time approximation algorithms achieve constant-factor guarantees; a simple 2-approximation uses a maximal greedy algorithm obtained by repeatedly selecting an uncovered edge and including both endpoints in the cover, an approach taught in textbooks used at universities like MIT and Stanford University. Improved approximations and heuristics draw on linear programming relaxations and rounding techniques connected to work by researchers affiliated with IBM and Microsoft Research. The problem admits an LP-relaxation whose integrality gap informs limits on approximation; tight inapproximability results relate to the Unique Games Conjecture and hardness of approximation frameworks developed by groups at institutions such as Princeton University.

Parameterized and fixed-parameter tractable results

When parameterized by solution size k, the vertex cover decision problem is fixed-parameter tractable: there exist kernelization and branching algorithms yielding runtimes of the form f(k)·n^{O(1)}. Classic FPT algorithms use bounded search trees and kernelization techniques appearing in work by researchers associated with University of Bergen, Carnegie Mellon University, and the University of Edinburgh. Kernelization yields polynomial-size kernels, with advances culminating in linear-vertex kernels under certain models influenced by results from authors publishing in Journal of the ACM and proceedings like ESA. Parameterized complexity theory frames these results alongside hardness classes such as W[1] and techniques like iterative compression developed in algorithmic research communities including DIMACS.

Applications and variations

Vertex cover models numerous applied scenarios: sensor placement and monitoring problems studied at Bell Labs and in industrial research, bioinformatics problems in groups at Broad Institute and European Bioinformatics Institute, and network security formulations explored by researchers at Sandia National Laboratories. Variations include weighted vertex cover, where vertices have costs (studied in operations research at INFORMS conferences), connected vertex cover, and capacitated vertex cover, each with specialized algorithms. The problem is also a building block in reductions for other combinatorial problems and appears in complexity analyses related to graph classes investigated at institutions such as ETH Zurich and UCLA.

Examples and special cases

For bipartite graphs, König's theorem yields equality between the size of a minimum vertex cover and a maximum matching; this classical result is taught in courses at Oxford University and Cambridge University and is computable in polynomial time via matching algorithms by researchers at Bell Labs and AT&T. Trees admit linear-time exact algorithms using dynamic programming techniques similar to those developed in algorithmic graph theory seminars at Cornell University. Special graph classes—planar graphs, bounded-degree graphs, and chordal graphs—offer differing complexity profiles and approximation improvements studied in research groups at Princeton University and Technische Universität München.

Category:Graph theory