To formulate a related decision problem for the independent-set problem and prove that it is NP-complete.
Explanation of Solution
Independent set of a graph G represents the set or collection of vertices that are not adjacent to one another. It is a concept in graph theory according to which there should not be any edge connecting the two vertices of a set.
- It is also known as a stable set in which an edge can have at most single endpoint in the graph.
- Thus, the vertices contained in the independent set represent the subset of the vertices of a graph.
Consider the figure or the graph given below containing an independent set of size 3:
Consider a graph containing V vertices and set of edges E. Here, it is required to devise a decision problem for the independent−set problem and proving that it is NP-complete.
Decision problem:
- It is a way of asking the question in order to determine that whether a solution or answer of a particular question exists or not.
- It is a type of problem in a formal system in which the answer or solution of the problem comes out to be in two definite forms as either yes or no.
Consider the following example:
Graph coloring, Hamiltonian cycle or graph. Travelling salesperson Problem (TSP) is some of the common examples of the decision problems (all these can also be expressed as an optimization problem).
Now, it is also asked to show that independent set problem is NP complete.
NP Hard: To show that the problem is NP Hard, the concept of reducing or transforming the instance of the clique problem to an instance of an independent set S.
Consider the instance of the clique problem as This problem is independent set problem having set where is the complement of E.
The set of vertices V represents a clique having size x is in the graph G only in case if V’ is an independent set of graph G’ having the size x and it is also following the fact that the construction of from must be done in polynomial time.
In this regard, it can be concluded that independent set problem is also NP hard. Thus it has been proved that an independent set problem is NP as well as NP-hard so it can be said that it is always NP complete.
To give an
Explanation of Solution
Given a black box subroutine to solve the decision problem defined in part (a) and a graph
To implement the algorithm for solving the problem consider black box as
Algorithm:
//perform search operation
Step 1: start binary search on B to determine the maximum size for the independent set.
//initialization step.
Step 2: Set the independent set I to be an empty set.
Step 3: For each
Construct by removal of and its related edges from the graph
Step 4: If
Set
Else
Here is obtained by removal of all the vertices which are connected to and the edges which are linked to it from the graph
//end
Here, step 1 has a time complexity of
Step2: it has a time complexity of
Step 3-4 : They have the number of iterations equal to
Hence it can be concluded that the time complexity is equal to
To give an efficient algorithm to solve the independent-set problem when each vertex in G has degree 2.
Explanation of Solution
Given that the degree of the graph is 2, which implies that each vertex in the graph has a cardinality or degree 2.
Here, it is required to give an algorithm that can solve the independent set problem of a graph having degree 2.
Also, it is required to analyze the running time and the correctness of an algorithm.
Consider the graphs containing a simple cycle-
Thus, from the above graphs it can be observed that generally the graph containing the vertices of degree 2 is a simple cycle.
Therefore, the independent set problem is such a case can be achieved by initiating at any vertex and start choosing the alternate vertex on the cycle till the size obtained for the independent set to be
Hence, it can also be concluded that that the running time of the algorithm to solve the problem of independent set having V vertices, E edges and degree of each vertex as 2 is
To give an algorithm to solve the independent set problem when G is bipartite.
Explanation of Solution
A bipartite graph commonly known as the biograph is an undirected graph whose vertex set can be partitioned or arranged into two disjoint sets that are independent.
It is possible to color this type of graph by using the two colors only so it is 2 colorable or bichromatic.
There are several applications of these graphs by using graphs like in case of matching problems.
For example:
Consider a bipartite graph given below containing two set of vertices and such that
First find the maximum-matching of the graph by using an algorithm such as augmenting path algorithm or much faster and an improved algorithm known as Hopcroft-Karp bipartite matching algorithm. (Refer section 26-6)
? Repeat the process
¦ for all vertices which are not present in the maximum-matching set (set with largest number of edges), run BFS to find the augmenting path.
¦ Alternate unmatched/matched edges to select the edge which is in the maximum matching and are not connected from the vertices that are not a part maximum matching set.
¦ Reverse or flip the matched edges with unmatched edges and vice-versa.
? Stop the process if no augmenting path is found and return the last matching set.
The running time or running complexity of the algorithm to solve the independent set problem is. The algorithm works correctly if there does not exist any augmenting path with respect to the maximal matching M as obtained by applying the bipartite matching algorithm.
Want to see more full solutions like this?
Chapter 34 Solutions
Introduction to Algorithms
- An independent set of a graph G = (V, E) is a subset V’ V of verticessuch that each edge in E is incident on at most one vertex in V’. Theindependent-set problem is to find a maximum-size independent set in G.Formulate a related decision problem. Then, Prove that this decision problem is NP-complete. (Hint: Reduce fromthe clique problem or from the vertex cover problem.)arrow_forwardBe G = (V. E) a connected graph and u, vEV.The distance Come in u and v, denoted by du, v), is the length of the shortest path between u and v, Meanwhile he width from G, denoted as A(G) is the greatest distance between two of its vertices. Dice k EN such that k>0, consider the following decision problem: k-WIDTH: • I«WIDTH = {G| G is a graph} - L«WIDTH = {G | Gis a connected graph such that A(G) > k} Show that k-WIDTH EP. Hint:Study algorithms that find the shortest path between two vertices of a graph.arrow_forward3) The graph k-coloring problem is stated as follows: Given an undirected graph G = (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in Va color c(v) such that 1< c(v)arrow_forwarda. Explain how to prove that a problem is NP-Complete based onreduction from a known NP-Complete problem.b. An independent set of a graph G = (V, E) is a subset V’ V of verticessuch that each edge in E is incident on at most one vertex in V’. Theindependent-set problem is to find a maximum-size independent set in G.Formulate a related decision problem.c. Prove that this decision problem is NP-complete. (Hint: Reduce fromthe clique problem or from the vertex cover problem.)arrow_forwardAre the following problems in P, NP, co-NP, NP-Hard, NP-complete? Either way, prove it. (a) A kite is a graph on an even number of vertices, say 2n, in which n of the vertices form a clique and the remaining n vertices are connected in a tail that consists of a path joined to one of the vertices of the clique. Given a graph and a goal g, the max kite problem asks for a sub-graph that is a kite and contains 2g nodes. What complexity classes does kite belong in? (b) A 4kite is exactly the same problem, but this time g = 4. What complexity classes does 4kite belong in?arrow_forwardAn independent set of a graph G = (V, E) is a subset V’ is subset of V of verticessuch that each edge in E is incident on at most one vertex in V’. Theindependent-set problem is to find a maximum-size independent set in G. Question: Prove that this decision problem is NP-complete. (Hint: Reduce fromthe clique problem or from the vertex cover problem.)arrow_forward1. Let F be a forest with n vertices and k connected components, with 1 < k < n. (a) Compute ) deg(v) in terms of n and k. vɛV(F) (b) Show that the average degree of a vertex in F is strictly less than 2. (c) Conclude that forests have leaves.arrow_forwardGiven an undirected graph G = (V, E), a vertex cover is a subset of V so that every edge in E has at least one endpoint in the vertex cover. The problem of finding a minimum vertex cover is to find a vertex cover of the smallest possible size. Formulate this problem as an integer linear programming problem.arrow_forwardLet G be a graph with n vertices. The k-coloring problem is to decide whether the vertices of G can be labeled from the set {1, 2, ..., k} such that for every edge (v,w) in the graph, the labels of v and w are different. Is the (n-4)-coloring problem in P or in NP? Give a formal proof for your answer. A 'Yes' or 'No' answer is not sufficient to get a non-zero mark on this question.arrow_forwardLet T:V→V be the adjacency operator of the Petersen graph as illustrated in the enclosed file. Here Vis the vector space of all formal real linear combinations of the vertices v1,..,v10 of the Petersen graph. Question: compute the spectrum of the adjacency operator Tof the Petersen graph. What do you observe?arrow_forwardThe low-degree spanning tree problem is as follows. Given a graph G and an integer k, does G contain a spanning tree such that all vertices in the tree have degree at most k (obviously, only tree edges count towards the degree)? For example, in the following graph, there is no spanning tree such that all vertices have a degree at most three. (a) Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian path. (b) Now consider the high-degree spanning tree problem, which is as follows. Given a graph G and an integer k, does G contain a spanning tree whose highest degree vertex is at least k? In the previous example, there exists a spanning tree with a highest degree of 7. Give an efficient algorithm to solve the high-degree spanning tree problem, and an analysis of its time complexity.arrow_forward3) The graph k-coloring problem is stated as follows: Given an undirected graph G= (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in V a color c(v) such that 1arrow_forwardarrow_back_iosSEE MORE QUESTIONSarrow_forward_iosRecommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSONC How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education