(a) Formally define the decision problems Vertex Cover and Independent Set, expl
ID: 3758860 • Letter: #
Question
(a) Formally define the decision problems Vertex Cover and Independent Set, explaining all tech- nical terms.
(b) Fix a positive integer k. Give a polynomial-time algorithm A for finding a vertex cover of size k in an input graph, or proving that none exists.
(c) Describe an algorithm using A as a subroutine that solves the problem of finding the small- est vertex cover in a graph. What is the largest class of graphs for which this algorithm is guaranteed to run in polynomial time?
(d) Give a polynomial-time reduction (both directions) between Vertex Cover and Independent Set.
Explanation / Answer
(a)
A graph G with n vertices consists of a set of vertices V, with |V| = n, and a set of edges E, such that each edge
is an unordered pair of distinct vertices. We may label the vertices of G with the integers 1, 2, …, n. If the
unordered pair of vertices {u, v} is an edge in G, we say that u is a neighbor of v and write uvE.
VERTEX COVER
A vertex cover C of G is a set of vertices such that for every edge {u,v} of G at least one of u or v is in C.
INDEPENDENT SET
An independent set S of G is a set of vertices such that no unordered pair of vertices in S is an edge.
(b)
Vertex Cover Problem is a known NP Complete problem, i.e., there is no polynomial time solution for this unless P =
NP. Approximate Algorithm is :
Procedure A :
1) Initialize the result as {}
2) Consider a set of all edges in given graph. Let the set be E.
3) Do following while E is not empty
...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
...b) Remove all edges from E which are either incident on u or v.
4) If the size of result set is k, Return result
Else Return "No k-vertex cover exist"
(c)
*if (C) is the number of removable vertices of a vertex cover C of G.
*Procedure Sub1
Given a simple graph G with n vertices and a vertex cover C of G, if C has no removable vertices, output C. Else,
for each removable vertex v of C, find the number (C{v}) of removable vertices of the vertex cover C{v}. Let vmax
denote a removable vertex such that (C{vmax}) is a maximum and obtain the vertex cover C{vmax}. Repeat until the
vertex cover has no removable vertices.
*Procedure Sub2
Given a simple graph G with n vertices and a minimal vertex cover C of G, if there is no vertex v in C such that v
has exactly one neighbor w outside C, output C. Else, find a vertex v in C such that v has exactly one neighbor w
outside C. Define Cv,w by removing v from C and adding w to C. Perform procedure 3.1 on Cv,w and output the
resulting vertex cover.
1). Use Procedure A to find a k-vertex cover.
2). For i = 1, 2, ..., n in turn
Initialize the vertex cover Ci = V{i}.
Perform procedure Sub1 on Ci.
3). For r = 1, 2, ..., nk perform procedure Sub2 repeated r times.
The result is a minimal vertex cover Ci.
Class of graphs for which this algorithm can run in polynomial time :
*Planar Graphs of degree 3
*Biparite Graphs
*Tree Graphs
I have answered 3/4 questions. Please comment if you have any queries on the solution
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.