Computer Science
Vertex Cover Problem
The Vertex Cover Problem is a computational problem that involves finding the smallest set of vertices in a graph that covers all the edges. It is an NP-complete problem, meaning that it is difficult to solve for large graphs and there is no known efficient algorithm to solve it. The problem has applications in network design, scheduling, and optimization.
Written by Perlego with AI-assistance
Related key terms
1 of 5
4 Key excerpts on "Vertex Cover Problem"
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
A similar result with a higher value of c was recently proved by Alon, Moshkovitz & Safra (2006). Related problems • Hitting set is an equivalent reformulation of Set Cover. • Vertex cover is a special case of Hitting Set. • Edge cover is a special case of Set Cover. • Set packing is the dual problem of Set Cover. • Maximum coverage problem is to choose at most k sets to cover as many elements as possible. Vertex cover In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. Its decision version, the Vertex Cover Problem , was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem in computational complexity theory. Furthermore, the Vertex Cover Problem is fixed-parameter tractable and a central problem in parameterized complexity theory. The minimum Vertex Cover Problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem. Covering-packing dualities Covering problems Packing problems Minimum set cover Maximum set packing Minimum vertex cover Maximum matching Minimum edge cover Maximum independent set Definition Formally, a vertex cover of a graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C . The set C is said to cover the edges of G . The following figure shows examples of vertex covers in two graphs (the set C is marked with red). ________________________ WORLD TECHNOLOGIES ________________________ A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number τ is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in two graphs.
eBook - PDF- Armen S. Asratian, Tristan M. J. Denley, Roland Häggkvist(Authors)
- 1998(Publication Date)
- Cambridge University Press(Publisher)
Chapter 10 Coverings 10-1 Some examples of covering problems JVlany problems in graph theory can be formulated as an instance of the following, somewhat general, covering problem: We are given two sets X and Y, and with each element x € X there is an associated subset K(x) of elements of Y (which are covered in some sense by the element x). We know that U xeX K( x ) = Y> our task is to find a subset XQ C X of mini- mum cardinality such that {J xe x 0 K( x ) = Y"• The set X is called the covering set and the set Y is the covered set Every subset X f C X satisfying \J x£X f K( x ) = Y ls c&Ued a covering of Y by X. Our problem is to find a covering consisting of as few elements as possible, a minimum covering of F by X. As an example we might take X to be the set of all matchings in a bipartite graph G, 7 to be the set of edges E{G), and K(M) = M for each matching M e X. Then a proper A(G)- colouring of G induces a minimum covering of Y by X. There are many other possible such examples, several are given in the exercises for this section. Later, in Section 12.2, we will consider covering the edges of a non-bipartite graph with bipartite subgraphs with prescribed properties. First, however, there are several special forms of coverings for bipartite graphs which merit particular attention. So let G be a bipartite graph with bipartition (Vi, V2) without isolated vertices. Problem 1 (A minimum covering of V2 by Vi) Here the covering set X is the vertex set Vi, the covered set is V2, and K{x) = NG(X) for each a: € Vi. It is necessary to find a subset XQ C VI of minimum cardinality such that NG(XO) = V2. 174 175 10.1 Some examples of covering problems Example A museum wants to employ a number of interpreters to give tours in a number of different languages. How can the museum employ as few of the job applicants as possible, whilst still being able to offer tours in all the languages? This problem is easily reformulated as an instance of Problem 1.
eBook - PDFPhase Transitions in Combinatorial Optimization Problems
Basics, Algorithms and Statistical Mechanics
- Alexander K. Hartmann, Martin Weigt(Authors)
- 2006(Publication Date)
- Wiley-VCH(Publisher)
(B → C) Let V \ V be an independent set, and i, j ∈ V \ V . By definition, there is no edge {i, j } ∈ E, and so there is an edge {i, j } ∈ E C . Therefore, V \ V is a clique of G C . (C → A) Let V \ V be a clique of G C , and {i, j } ∈ E. This means {i, j } ∈ E C by definition of G C . Thus, we have i ∈ V \ V or j ∈ V \ V because V \ V is a clique. Hence, i ∈ V or j ∈ V . By definition of vertex cover, V is a vertex cover. QED The minimum vertex cover is a vertex cover of minimum cardinality. From the theorem above, for a minimum vertex cover V , V \ V is a maximum independent set of G and a maximum clique of G C . In Fig. 3.4, a graph together with its minimum vertex cover is displayed. Related to the minimization problem is the following decision problem, for given integer K: Vertex Cover (VC): Does a given graph G have a vertex cover V with |V | ≤ K? In Chap. 4 we will see that VC is a so-called NP-complete problem, which means in particular that no fast algorithm for solving this problem is known – and not even expected to be able to be constructed. This proposition and its relation to statistical physics will be the main subject of this book. 3.1.5 The graph coloring problem The last problem which we discuss in this section is a scheduling problem. Imagine you have to organize a conference with many sessions which, in principle, can take place in parallel. Some people, however, want to participate in more than one session. We are looking for a perfect schedule in the sense that every one can attend all the sessions he wants to, but the total conference time is minimum. The mapping to an undirected graph is the following: The sessions are considered as vertices. Two of them are connected by an edge whenever there is a person who wants to attend both. We now try to color the vertices in such a way that no adjacent vertices carry the same color.
eBook - PDF- W Art Chaovalitwongse, Sergiy Butenko, Panos M Pardalos(Authors)
- 2009(Publication Date)
- World Scientific(Publisher)
An extremely simple search tree approach for solving V ERTEX C OVER is to just take one vertex and branch into two cases: either this vertex is in the vertex cover or not. This leads to a search tree of size O (2 n ) . As we outline in this section, we can do much better than that and obtain a search tree whose depth is upper-bounded by k , giving a size bound of O (2 k ) . Since usually k n , this can draw the problem into the zone of feasibility even for large graphs (as long as k is small). The basic idea is to find a small subset of the input instance in polynomial time such that at least one element of this subset must be part of an optimal solution to the problem. In the case of V ERTEX C OVER , the most simple such subset is any two vertices that are connected by an edge. By definition of the problem, d In general, the constraint k < n is easily established. As Dehne et al. [23] point out in their studies of C LUSTER E DITING , it depends on the concrete problem which search strategy for the “optimum” value of k is most efficient to employ in practice. Fixed-Parameter Algorithms for Graph-Modeled Data Clustering 11 . . . k . . . . . . . . . k − 1 k − 2 k − 1 k − 2 k − 2 k − 2 Fig. 1.2. Simple search tree for finding a vertex cover of size at most k in a given graph. The size of the tree is upper-bounded by O (2 k ) . one of these two vertices must be part of a solution. Thus, a simple search-tree algorithm to solve V ERTEX C OVER on a graph G proceeds by picking an arbitrary edge e = { v, w } and recursively searching for a vertex cover of size k − 1 both in G − v and G − w . e That is, the algorithm branches into two subcases knowing one of them must lead to a solution of size at most k —if one such solution exists. As shown in Fig. 1.2, these recursive calls of the simple V ERTEX C OVER algorithm can be visualized as a tree structure.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
