Fact-checked by Grok 2 weeks ago

Vertex cover

In graph theory, a vertex cover of an undirected graph G = (V, E) is a subset C \subseteq V such that every edge in E is incident to at least one vertex in C.^[1] The minimum vertex cover problem seeks a vertex cover of smallest cardinality, denoted \tau(G), which represents the minimum number of vertices needed to cover all edges.^[2] The decision version of the vertex cover problem—determining whether a graph has a vertex cover of size at most k—is one of the 21 NP-complete problems identified by Karp in 1972 and is formally proven NP-complete via reduction from the independent set problem.^[2] Exact solutions for minimum vertex cover are computationally intractable for general graphs, but fixed-parameter algorithms exist that solve it efficiently when k is small, running in time O(2^k \cdot k^2 \cdot n) or better via kernelization techniques that reduce the instance size.^[1] Approximation algorithms provide efficient near-optimal solutions; a simple greedy algorithm based on maximal matching achieves a 2-approximation ratio by selecting both endpoints of each matched edge, guaranteeing a cover at most twice the optimum.^[1] More sophisticated methods, such as linear programming relaxation followed by rounding, also yield a 2-approximation, and these bounds are tight in the sense that no polynomial-time algorithm can achieve a factor better than $2 - \epsilon for any \epsilon > 0 unless P = NP, as established through probabilistically checkable proofs.^[3]^[4] In bipartite graphs, the minimum vertex cover size equals the maximum matching size by König's theorem, enabling exact polynomial-time solutions using maximum flow algorithms like the Hopcroft-Karp algorithm in O(\sqrt{|V|} \cdot |E|) time.^[5] Vertex cover is dual to the independent set problem, as the complement of a minimum vertex cover forms a maximum independent set, linking it to broader themes in combinatorial optimization.^[1]

Definition and Examples

Formal Definition

In graph theory, a simple undirected graph G is formally defined as an ordered pair G = (V, E), where V is a finite nonempty set of elements called vertices, and E is a finite set of unordered pairs of distinct vertices from V, called edges.^[6] A vertex cover of an undirected graph G = (V, E) is a subset C \subseteq V such that every edge in E has at least one endpoint in C. Formally, this covering condition is expressed as \forall \{u, v\} \in E, \, u \in C or v \in C.^[7]^[8] The size of a vertex cover C is denoted by |C|. A minimum vertex cover is a vertex cover of smallest possible size, and the vertex cover number of G, which is the size of such a minimum vertex cover, is denoted by \tau(G) or \beta(G).^[9]^[10]

Illustrative Examples

Consider a path graph with three vertices a, b, c and edges \{a, b\} and \{b, c\}. The set \{b\} is a minimum vertex cover of size 1, as it covers both edges. The sets \{a, c\} or \{a, b\} are vertex covers of size 2.^[11] For a cycle graph with four vertices a, b, c, d and edges \{a, b\}, \{b, c\}, \{c, d\}, \{d, a\}, the sets \{a, c\} or \{b, d\} are minimum vertex covers of size 2.^[11] In a complete graph K_3 with vertices a, b, c and all possible edges \{a, b\}, \{a, c\}, \{b, c\}, any two vertices form a minimum vertex cover of size 2.^[11]

Mathematical Properties

Fundamental Properties

A fundamental relation in graph theory links the minimum vertex cover to the independence number through the Gallai identities. For any graph G with vertex set V(G) of size n = |V(G)|, the size of the minimum vertex cover \tau(G) and the independence number \alpha(G) satisfy \tau(G) + \alpha(G) = n. This equality holds because the complement of a maximum independent set is a minimum vertex cover, and vice versa.^[12] A related identity involves edge covers: the size of the minimum edge cover \rho(G) plus the size of the maximum matching \nu(G) equals n, provided G has no isolated vertices. This follows from extending a maximum matching to cover all vertices by adding at most n - 2\nu(G) edges incident to uncovered vertices.^[13] Another key inequality provides a lower bound on the minimum vertex cover size. For any graph G with m = |E(G)| edges and maximum degree \Delta(G), \tau(G) \geq m / \Delta(G). This bound arises because each vertex in a vertex cover can incident to at most \Delta(G) edges, so at least m / \Delta(G) vertices are needed to cover all edges. For example, in a star graph with n-1 leaves, \tau(G) = 1 = (n-1)/ (n-1), achieving equality. In bipartite graphs, the minimum vertex cover size equals the maximum matching size, by König's theorem: \tau(G) = \nu(G). This equivalence, which does not hold in general graphs, underpins many algorithmic results for bipartite matching problems.^[14] The minimum vertex cover size exhibits monotonicity properties with respect to graph modifications. Adding edges to a graph G to form a supergraph H yields \tau(H) \geq \tau(G), as any vertex cover of H covers all edges of G, but new edges may require additional vertices. Conversely, for any subgraph H of G, \tau(H) \leq \tau(G), since the restriction of a minimum vertex cover of G to V(H) covers the edges of H. These properties follow directly from the definition of vertex covers.^[12]

Connections to Other Graph Structures

A vertex cover in a graph G = (V, E) is the complement of an independent set, and conversely, the complement of an independent set is a vertex cover. If C \subseteq V is a vertex cover, then no edge has both endpoints in V \setminus C, so V \setminus C induces no edges and is thus an independent set. This duality implies that the minimum vertex cover number \tau(G) equals |V| - \alpha(G), where \alpha(G) is the independence number.^[15]^[16] Every vertex cover of a graph without isolated vertices is a dominating set, as each vertex is either in the cover or incident to an edge covered by the set, hence adjacent to a vertex in the cover. The converse does not hold; for instance, a graph with an isolated vertex requires that vertex in any dominating set to cover itself, but vertex covers need only cover edges and may omit isolated vertices.^[17] The minimum edge cover exhibits a duality analogous to that between vertex covers and independent sets, via the Gallai identities relating packing and covering parameters. Specifically, the size of a minimum edge cover \rho(G) equals |V| - \nu(G), where \nu(G) is the size of a maximum matching; this follows because a maximum matching leaves |V| - 2\nu(G) unmatched vertices, each requiring an additional edge to cover, yielding a minimum edge cover of size \nu(G) + (|V| - 2\nu(G)) = |V| - \nu(G). This relation connects to vertex covers through the line graph L(G), where the independence number \alpha(L(G)) equals \nu(G), as independent sets in L(G) correspond to matchings in G.^[16]^[18] In hypergraphs, the vertex cover concept extends naturally: a vertex cover is a set of vertices intersecting every hyperedge. While the standard definition applies to graphs as 2-uniform hypergraphs, the generalization to hypergraphs of uniformity greater than 2 captures more complex set systems, such as in set cover problems, but retains the core property of covering all "edges" with vertices. Focus remains on simple undirected graphs for foundational theory.^[19] The vertex cover problem traces its origins to Dénes Kőnig's 1931 work on bipartite graphs, where he proved that the minimum vertex cover size equals the maximum matching size, establishing a cornerstone duality in matching theory.^[20]

Computational Aspects

Decision and Optimization Problems

The vertex cover problem can be approached through several computational variants, each highlighting different aspects of its complexity. The decision problem, often denoted as Vertex Cover, takes as input an undirected graph G = (V, E) and a non-negative integer k, and asks whether there exists a vertex cover of size at most k. This problem belongs to NP, as a proposed cover can be verified in polynomial time by checking all edges. It is NP-complete, as shown by Karp, who established a polynomial-time reduction from the Clique problem, where an instance of Clique on graph H with parameter l transforms into a Vertex Cover instance on the complement graph \overline{H} with parameter |V(H)| - l.^[8] The optimization variant seeks to compute a minimum vertex cover, i.e., one of smallest cardinality that covers all edges in G. This problem is NP-hard, as its solution would enable solving the decision version via binary search over possible values of k from 0 to |V|, and repeated calls to an oracle for the optimization problem.^[21] The associated search problem requires not just determining the size but outputting an actual minimum vertex cover, which inherits the NP-hardness of the optimization version.^[21] The NP-completeness of the decision problem follows from various reductions from other NP-complete problems. One standard reduction is from 3-SAT: given a 3-CNF formula \phi with n variables and m clauses, construct a graph with a gadget for each variable consisting of two vertices (one for the literal and its negation) connected by an edge, and for each clause a gadget consisting of three new vertices forming a triangle, with each of these vertices connected by an edge to the graph vertex representing the corresponding literal in that clause; set k = n + 2m. A vertex cover of size at most k exists if and only if \phi is satisfiable, as selecting one endpoint per variable edge fixes a truth assignment (using n vertices), and the clause gadgets can then be covered using at most two vertices each (total $2m) consistent with that assignment.^[22] Although NP-complete in general, the decision problem is solvable in polynomial time on restricted graph classes. For bipartite graphs, König's theorem equates the size of the minimum vertex cover to the size of the maximum matching; the latter can be found in O(|E| \sqrt{|V|}) time using the Hopcroft-Karp algorithm, from which a minimum vertex cover is constructed via alternating paths.^[5] For trees, a dynamic programming algorithm computes a minimum vertex cover in O(|V|) time: root the tree at an arbitrary vertex, and for each subtree, compute the minimum cover size including or excluding the root, recursing on children while ensuring edges to them are covered.^[23] The vertex cover decision problem also admits a natural parameterization by the solution size k, where the question is whether G has a vertex cover of size at most k; this parameterized version is fixed-parameter tractable, solvable in time f(k) \cdot |V|^{O(1)} for some function f, with algorithmic details addressed elsewhere.

Integer Linear Programming Formulation

The minimum vertex cover problem can be formulated as an integer linear program (ILP) using binary decision variables for each vertex in the graph. For a graph G = (V, E) with vertex set V and edge set E, introduce a binary variable x_v \in \{0, 1\} for each v \in V, where x_v = 1 if vertex v is included in the cover and x_v = 0 otherwise.^[24] The objective is to minimize the total number of selected vertices, given by

\min \sum_{v \in V} x_v,

subject to the constraints that ensure every edge is covered by at least one endpoint:

x_u + x_v \geq 1 \quad \forall \{u, v\} \in E,

along with the integrality requirements x_v \in \{0, 1\} for all v \in V. This formulation directly models the requirement that no edge remains uncovered, as each constraint forces at least one incident vertex to be selected.^[24]^[25] A natural linear programming (LP) relaxation of this ILP is obtained by replacing the integrality constraints with $0 \leq x_v \leq 1 for all v \in V, yielding a polynomial-time solvable program whose optimal value provides a lower bound on the integer optimum. For bipartite graphs, this LP relaxation is integral, meaning its optimal solutions are always integer-valued, and thus the LP can be used to compute an exact minimum vertex cover in polynomial time via duality with maximum matching (König's theorem).^[25]^[26] Exact solutions to the ILP can be obtained using general-purpose integer programming solvers that implement branch-and-cut algorithms, such as CPLEX or SCIP, which iteratively solve LP relaxations, branch on fractional variables, and add cutting planes to tighten the formulation.^[27]

Algorithms for Exact Solutions

Branch-and-Bound Techniques

Branch-and-bound algorithms solve the minimum vertex cover problem exactly by systematically exploring the search space of possible vertex subsets while pruning branches that exceed known bounds. A typical approach selects a vertex, typically of maximum degree, and branches into two subproblems: one including the vertex in the cover (removing it and its incident edges) and one excluding it (removing the vertex and adding edges between its neighbors to enforce coverage). To prune inefficient branches, lower bounds are computed for the minimum cover size in subgraphs, such as degree-based bounds (summing half the degrees of isolated vertices), maximum matching sizes, or clique covers. For instance, the EMVC algorithm employs degree, MaxSAT-based, and clique lower bounds, demonstrating superior performance on dense DIMACS benchmarks compared to prior solvers like SBMS and FastVC.^[28] These methods are exponential in the worst case but effective for moderate-sized instances.

Fixed-Parameter Tractable Algorithms

Fixed-parameter tractable (FPT) algorithms solve the k-vertex cover problem—determining if there is a vertex cover of size at most k—efficiently when k is small, with running time f(k) · poly(n) where n = |V|. A standard branching algorithm selects an arbitrary edge (u, v) and recurses on two cases: including u (remove u and incident edges, decrement k) or including v (similarly), ensuring the search tree has depth at most k and at most 2^k leaves. The base case checks if k ≥ 0 and the graph has no edges. To improve efficiency, kernelization preprocesses the instance: include all vertices of degree > k in the cover (reducing k accordingly), remove isolated vertices, and reject if the number of remaining edges exceeds k^2 (since a cover of size k covers at most k(k-1)/2 + k edges in the kernel). This yields a kernel with O(k^2) vertices and edges. The overall time complexity is O(2^k · k^2 + n + m), where m = |E|, making it practical for small k.^[29]

Approximation and Hardness

Approximation Algorithms

The greedy algorithm for approximating the minimum vertex cover selects a vertex of maximum degree, adds it to the cover, removes the vertex and all its incident edges from the graph, and repeats this process until no edges remain. This approach is straightforward and runs in polynomial time, but it does not guarantee a constant-factor approximation; its worst-case performance ratio is \Omega(\log n) on certain graphs, making it inferior to other methods for general instances.^[30] A well-established 2-approximation algorithm constructs a maximal matching M in the graph and includes both endpoints of each edge in M into the vertex cover. The size of this cover is at most $2|M|, and since |M| \leq \tau(G) where \tau(G) is the size of the minimum vertex cover (as every edge in M requires at least one distinct vertex in any cover), the approximation ratio is 2. This technique originates from early work on graph approximation problems.^[31] An alternative 2-approximation leverages the linear programming relaxation of the vertex cover integer program, where the LP solution provides a lower bound on \tau(G). By rounding each fractional variable x_v \geq 1/2 to 1 and others to 0, the resulting integer solution forms a valid vertex cover whose cost is at most twice the LP optimum, hence at most $2\tau(G). This LP-based method was introduced as part of broader covering problem approximations.^[32] Slightly improved ratios beyond 2 are possible using randomized rounding on the LP relaxation combined with subgraph modifications to handle small odd cycles. One such algorithm achieves an approximation ratio of $2 - \Theta(\log \log n / \log n). A more recent advancement achieves $2 - \Theta(1/\sqrt{\log n}), refining the bounds while maintaining polynomial-time efficiency. These advancements stem from local-ratio techniques and semidefinite programming applied to weighted instances.^[33]^[34] Local search heuristics enhance practicality for large-scale graphs by starting with an initial cover (e.g., from the maximal matching algorithm) and iteratively swapping vertices to reduce the cover size while preserving coverage, often exploring small neighborhoods like k-improvements for small k. These methods lack strong worst-case guarantees but yield high-quality solutions empirically, outperforming simpler approximations on massive real-world networks.^[35]

Inapproximability Results

The minimum vertex cover problem is NP-hard to approximate to within a factor of $1.3606 unless P = NP.^[36] This result, obtained via probabilistically checkable proofs (PCP) and gap-amplification techniques, significantly improved upon prior unconditional hardness bounds and resolved a key open question regarding the approximability threshold for the problem.^[36] Under the Unique Games Conjecture (UGC), the problem exhibits stronger inapproximability: it is NP-hard to approximate within a factor of $2 - \epsilon for any constant \epsilon > 0.^[37] This conditional result, based on reductions from unique games to vertex cover, establishes a tight gap hardness, implying no (2 - o(1))-approximation algorithm exists unless P = NP, as it nearly matches the performance of the trivial greedy 2-approximation algorithm.^[37]

Applications

Theoretical Applications

In matching theory, vertex covers play a central role in establishing duality between maximum matchings and minimum covers in bipartite graphs. König's theorem states that in any bipartite graph G, the size of the maximum matching equals the size of the minimum vertex cover, denoted \tau(G).^[5] This equivalence not only provides a min-max theorem but also enables algorithmic solutions for both problems via flows or linear programming relaxations, highlighting vertex cover's utility in proving structural results about matchings. Vertex cover serves as a special case of the set cover problem, where the universe consists of the edges of the graph and each vertex corresponds to a set containing all incident edges. This reduction demonstrates that vertex cover inherits the NP-hardness of set cover while allowing tailored hardness proofs for graph-specific instances.^[38] For example, reductions from 3-SAT to vertex cover leverage this structure to establish inapproximability thresholds, such as the constant-factor barrier under the unique games conjecture, which in turn inform broader covering problem complexities. The minimum feedback vertex set, which hits all cycles in a graph, relates to vertex cover since every vertex cover induces an acyclic subgraph by eliminating all edges. Consequently, the size of the minimum feedback vertex set is at most \tau(G), providing a theoretical bound that aids in analyzing cycle-hitting problems.^[39] This inequality \tau(G) \geq feedback vertex set number underscores vertex cover's role in bounding feedback structures, useful in proofs for acyclic orientations and tournament analyses. Vertex covers contribute to bounds in graph coloring through their complement relation to independent sets. By the Gallai identities, for a connected graph G without isolated vertices, \tau(G) + \alpha(G) = n, where \alpha(G) is the independence number and n = |V(G)|.^[16] Combined with the bound \chi(G) \geq n / \alpha(G) from partitioning into color classes, this yields \tau(G) \geq n / \chi(G) as a lower bound on the vertex cover size in terms of the chromatic number \chi(G). Additionally, Brooks' theorem gives \chi(G) \leq \Delta(G) + 1 for connected graphs that are neither complete nor odd cycles, where \Delta(G) is the maximum degree, contrasting with vertex cover-derived estimates.^[40] In combinatorial optimization, vertex covers in bipartite graphs exhibit duality within matroid frameworks, where the problem aligns with transversal matroids on the bipartition. König's theorem emerges as a consequence of matroid intersection duality, equating the minimum vertex cover to the corank in the graphic matroid dual. This perspective extends to weighted variants and polyhedral characterizations, facilitating exact solutions via separation oracles and underscoring vertex cover's foundational role in matroid-based optimization.

Practical Applications

Vertex cover finds practical application in enhancing network reliability, particularly in communication and sensor networks where selecting a minimal set of nodes ensures monitoring or protection of all links. In wireless ad-hoc networks (WANETs), vertex cover is used to identify a subset of nodes that covers every communication edge, enabling efficient link monitoring to detect failures or attacks while minimizing resource overhead. For instance, a metaheuristic approach formulates the problem as finding a minimum vertex cover to optimize sensor placement for coverage in dynamic topologies, reducing energy consumption and improving fault tolerance.^[41] Similarly, in wireless sensor networks (WSNs), hard-constrained vertex cover algorithms select nodes to cover all edges, maximizing network lifetime by balancing coverage and communication efficiency, with experimental results showing covers as small as 37% of total nodes.^[42] In bioinformatics, vertex cover aids in analyzing protein-protein interaction (PPI) networks to identify key molecules in biological pathways, such as those involved in diseases. By modeling proteins as vertices and interactions as edges, a partial dense vertex cover game identifies protein complexes as dense subgraphs where selected vertices cover essential interactions, revealing functional modules with high biological relevance; this non-cooperative game-theoretic formulation outperforms traditional clustering in detecting overlapping complexes in yeast PPI data.^[43] Additionally, approximate minimum vertex cover algorithms pinpoint structurally important amino acids by selecting residues that cover critical bonds in protein graphs, providing insights into stability and folding pathways, as demonstrated on benchmark protein structures.^[44] For VLSI design, vertex cover supports optimization in fault-tolerant circuit allocation and layout to maximize manufacturing yield. In reconfigurable VLSI arrays, generating minimal vertex covers determines row/column allocations that cover all defective cells, enabling efficient sparing strategies to bypass faults and improve chip reliability. This approach ensures every defective element in the array graph is incident to a selected spare row or column, facilitating higher yields in large-scale integrated circuits.^[45] In social networks, vertex cover helps identify influencers by selecting a minimal set of users whose connections cover all interactions, supporting viral marketing campaigns. This selection targets nodes that dominate information flow, ensuring broad reach with limited seeding; approximation algorithms scale this to large graphs, achieving near-optimal covers for influence propagation in real-world platforms.^[46] Vertex cover integrates with scheduling problems involving machine conflicts, where jobs form a graph and selected jobs must cover conflicting pairs to minimize makespan on parallel machines. The vertex cover meets multiprocessor scheduling (VCMS) problem motivates this by modeling servers as vertices and incompatibilities as edges, using covers to assign feasible subsets that optimize resource use in cloud or grid computing environments.^[47] Recent applications include machine learning for feature selection, where vertex cover on hypergraphs models dependencies to select minimal attributes covering all data relations, improving classifier accuracy in dynamic datasets from the 2010s onward.^[48] In cybersecurity, vertex cover enhances threat coverage by selecting nodes to monitor all potential attack edges in network graphs, as in intrusion detection systems where minimum covers identify critical points for anomaly detection and risk mitigation.^[49]

References

[1]
[PDF] 1 Introduction 2 Vertex Cover
Nov 22, 2015 · 2 Vertex Cover. Recall that a vertex cover in a graph is a set of vertices such that every edge is incident to (touches) at least one of them. ...
[2]
[PDF] Introduction to Graph Theory - Tandy Warnow
Definition: A vertex cover in a graph is a set V0 of vertices so that every edge in the graph has at least one of its endpoints in. V0. In other words, a vertex ...
[3]
A survey of approximately optimal solutions to some covering and ...
We survey approximation algorithms for some well-known and very natural combinatorial optimization problems, the minimum set covering, the minimum vertex ...
[4]
[PDF] Vertex Cover Might be Hard to Approximate to within 2 − ε
A simple 2- approximation algorithm exists for this problem: construct a maximal matching by greedily adding edges and then let the vertex cover contain both ...
[5]
[PDF] 1 Bipartite matching and vertex covers - Princeton University
A vertex cover is a subset of the nodes that together touch all the edges. (a) An example of a bipartite graph. (b) An example of a matching. (dotted lines).
[6]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book introduces graph theory, presenting basic material and applications to math and real-world problems, with new proofs and efficient methods.
[7]
Vertex Cover Kernelization Revisited | Theory of Computing Systems
Mar 8, 2012 · A vertex cover of an undirected graph G is a subset of the vertices that contains at least one endpoint of every edge. An instance of the Vertex ...
[8]
[PDF] Reducibility among Combinatorial Problems
Together Cook & Karp, and independently Levin laid the foundations of the theory of NP-Completeness. • “… Karp introduced the now standard methodology for.
[9]
https://arxiv.org/pdf/2507.00798
[10]
[PDF] Lower Bounds on the Vertex Cover Number and Energy of Graphs
The minimum size of a vertex cover of G is called the vertex cover number and it is denoted by β = β(G). The vertex covering problem and vertex cover number is ...<|control11|><|separator|>
[11]
A Simple Introduction to Graph Theory - Brian Heinold
[Gallai identities] For any graph with n vertices we have. α+β = n; α'+β' = n, provided the graph has no isolated vertices. Let's look at #1 first. Suppose S ...
[12]
Edge Cover Number -- from Wolfram MathWorld
The size of a minimum edge cover in a graph G is known as the edge cover number of G, denoted rho(G). If a graph G has no isolated points, ...
[13]
[PDF] Approximation Algorithms In this lecture we will discuss some NP ...
Therefore, the size of any matching provides a lower bound for the size of any vertex cover. Using a maximal matching with the above will give us a sufficiently ...
[14]
[PDF] 1. Lecture notes on bipartite matching
Feb 8, 2011 · Theorem 1.1 (König 1931) For any bipartite graph, the maximum size of a matching is equal to the minimum size of a vertex cover. We shall prove ...<|separator|>
[15]
[PDF] Lecture 23: Cliques and independent sets - Faculty Web Pages
Nov 5, 2024 · A subset S ⊆ V (G) is an independent set if and only if its complement V (G) − S is a vertex cover. For S to be an independent set, no edge can ...
[16]
[PDF] Lecture 1: Matchings on bipartite graphs 1 Basic Concepts
Prove that a matching M of a graph G is maximum iff there is no M-augmenting path. A subset U ⊆ V (G) is called a vertex cover of G iff every edge of G is ...
[17]
[PDF] The k-center problem - KIT - ITI Algorithmik
Feb 14, 2007 · Also, not every vertex cover is a dominating set.Isolated vertex. Page 5. Rob van Stee: Approximations- und Online-Algorithmen. 5. Proof We ...
[18]
[PDF] COMP260 Spring 2014 Notes: February 4th
Any set of vertices V 0 with {{u, v} : u ∈ V 0} (smallest or otherwise) is called a vertex cover of the graph. Intuitively, a cover is a dusting of vertices ...
[19]
[PDF] 1 Vertex Cover on Hypergraphs
Sep 11, 2019 · The vertex cover problem on hypergraphs is to find the smallest set S such that every edge X ∈ F intersects S at least once.
[20]
A translation of "Graphok és matrixok" by Dénes Kőnig (1931) - arXiv
Sep 5, 2020 · This paper, originally written in Hungarian by Dénes Kőnig in 1931, proves that in a bipartite graph, the minimum vertex cover and the maximum matching have ...
[21]
[PDF] COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP ...
Garey/David S. Johnson. Page 2. Library of Congress Cataloging in ... 3 VERTEX COVER and CLIQUE. 3.1.4 HAMILTONIAN CIRCUIT. 3.1.5 PARTITION... 3.2 ...
[22]
[PDF] 3-satisfiability reduces to vertex cover
Given an instance Φ of 3-SAT, we construct an instance (G, k) of VERTEX-COVER that has a vertex cover of size 2k iff Φ is satisfiable. Construction. ・G ...
[23]
[PDF] Dynamic Programming on Trees - Washington
Find the minimum vertex cover in a tree. Give every vertex a weight, find the minimum weight vertex cover. A set S of vertices is a vertex cover if ...
[24]
[PDF] approximating covering and packing problems: set cover, vertex ...
Approximation algorithms for the set covering and vertex cover problems. ... Maximizing submodular set functions: formulations and analysis of algorithms.
[25]
[PDF] Linear Programming Relaxations for Combinatorial Problems Vertex ...
Mar 31, 2016 · This is an integer linear program because it involves the {0,1} constraint on x. Many hard optimization problems can be written in this way.
[26]
[PDF] A Round and Bipartize Approximation Algorithm for Vertex Cover
Nov 3, 2022 · It is known that its standard linear programming relaxation is integral for bipartite graphs and half-integral for general graphs. As a ...
[27]
https://www.ibm.com/docs/en/icos/22.1.0?topic=algorithms-branch-cut-price
[28]
[PDF] Chapter 6 Approximation algorithms
Dec 10, 2013 · For this problem, the greedy algorithm will always take the vertex with the highest degree (i.e., the one covering the largest number of ...
[29]
A probabilistic algorithm for vertex cover - ScienceDirect.com
Feb 1, 2024 · A vertex cover ... Garey and Johnson [10] presented a simple algorithm of approximation ratio 2, based on maximal matching for general graphs.
[30]
Approximation Algorithms for the Set Covering and Vertex Cover ...
The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is 2 − o ⁡ ( 1 ) .
[31]
A better approximation ratio for the vertex cover problem
Bar-Yehuda, R., and Even, S. 1985. A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discrete Math. 25, 27--45. Google Scholar.
[32]
[PDF] Local Search for Minimum Vertex Cover in Massive Graphs - IJCAI
In this paper, we propose a simple and fast local search algorithm called. FastVC for solving MinVC in massive graphs, which is based on two low-complexity ...
[33]
On the hardness of approximating vertex cover
We prove the Minimum Vertex Cover problem to be NP-hard to approximate to within a factor of 1.3606, extending on previous PCP and hardness of approximation ...Missing: inapproximability | Show results with:inapproximability
[34]
Vertex cover might be hard to approximate to within 2−ε
We show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result.
[35]
[PDF] Lower Bounds Based on ETH - Simons Institute
Sep 3, 2015 · Double-exponential dependence on k cannot be avoided! Assuming ETH, there is no 22o(k) · nO(1) time algorithm for Edge Clique Cover. Proof: ...
[36]
[PDF] Set Cover
This particular proof was fairly easy, because, as the proof indicates, Vertex Cover is basically a special case of Set Cover.
[37]
[PDF] On Feedback Sets in Tournaments - Georgia Institute of Technology
Clearly a vertex cover of size at most k in G will act as a feedback vertex set of size at most k in G0. So let W0 denote a feedback vertex set in G0. Let W ...
[38]
[PDF] Lecture 25: Bounds on chromatic number - Faculty Web Pages
Nov 12, 2024 · This gives us another lower bound on chromatic number: Theorem 1.2. If G is an n-vertex graph with independence number α(G), then χ(G) ≥ n α(G).
[39]
A Metaheuristic Algorithm for Vertex Cover based Link Monitoring ...
Graph theory provides a great foundation to tackle the emerging problems in WANETs. A vertex cover (VC) is a set of vertices where every edge is incident to at ...
[40]
Hard constrained vertex-cover communication algorithm for WSN ...
The experimental results demonstrate the feasibility of our evolutionary approach in finding minimal vertex cover set, which is less than 37% of total sensors ...Missing: reliability | Show results with:reliability<|separator|>
[41]
Identifying protein complexes in PPI network using non-cooperative ...
Aug 21, 2017 · We formulate a Partial Dense vertex Cover (PDC) game for protein complex identification. The strategy set of a player is determined by a ...
[42]
Identification of structurally important amino acids in proteins by ...
We propose the application of approximate minimum vertex cover algorithms (MVC) as a novel approach for identifying the structurally important residues, which ...
[43]
[PDF] Whom to befriend to influence people - arXiv
Nov 29, 2016 · Abstract. Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person v in the network ...
[44]
Vertex Cover Meets Scheduling | Algorithmica - ACM Digital Library
We call this problem family vertex cover meets multiprocessor scheduling (VCMS). The problem is motivated by networks where vertices represent servers and each ...Missing: conflicts | Show results with:conflicts
[45]
Dynamic Feature Selection Algorithm Based on Minimum Vertex ...
Jun 17, 2018 · Firstly, we discuss the relationship between feature selection of information system and minimum vertex cover of hypergraph, and feature ...
[46]
https://www.sciencedirect.com/science/article/abs/pii/S0960077924003163