Suppose we are given a graph G(V, E) representing a computer network where verti
ID: 3776896 • Letter: S
Question
Suppose we are given a graph G(V, E) representing a computer network where vertices represent routers and edges represent physical connections. Suppose that we want to upgrade some of the routers in our network with special new, but expensive routers that can perform sophisticated monitoring operations for incident connections. We are interested to determine if k new routers are sufficient to monitor every connection in our network. Is the above problem a P or an NP-complete problem? If it is P, give a solution, if not state why it is an NP-complete problem.Explanation / Answer
This problem is NP-hard problem. we have VERTEX-COVER on hands.Let us now show that VETEX-COVER problem is NP-hard, by reducing the 3SAT problem to it in polunomial time. This reduction is interesting in two repsects. First,it shows an example of reducing a logic problem to a graph problem. Second, it ilustrates an application of the component design proof technique.
Let S be a given instance of 3SAT problem,that is,a CNF formula such that each clause has exactly threee literals. We construct a graph G and in integer k such that G has a vertex cover of size at most k if and only if S is satisfiable. WE begin our construction by adding the following :
For wach variabel x i used in the formula S , we add two vertices in G, one that we label with x i ad other we label with x i. We also add the edge(xi,xi) to G.These lables are for our own benefit, after we construct the graph G we can always relabe vertices with integers if that is what an instance of VERTEX-COVER problem should look like.
Each edge (xi,xi) is a truth setting componenet, for, with this edge in G, vertex cover must include at least one of xi. in Addition, we add the foloowing : for each clause Ci = (a+b+c) in S, we form a traingle consisting of three vetices, i1,i2 and i3 and three edges, (i1,i2),(i2,i3) and (i3,i1). Note that any vertex cover will have to include at least two of the verticesin {i1,i2,i3} for each such traingle. Each such triangle is a satisfaction-enforcing component. We then connect these two types of componenets, by adding, for each clause Ci=(a+b+c), the edges (i1,a), (i2,b) and (i3,c).
Finally we set the integer parameter k = n+2m, where is the number of variable in S and m is the number of clauses.Thus, if there is a vertex cover of size ay most k, it must have size exactly k. This completes the construction of an instance of the VERTEX-COVER problem.
this construction clearly runs in polunomial time, so let us considerits correctness.
Suppose there is an assignment of Boolean values to variables in S so that S is satisfied. from the grapg G constructed from S, we can build a subset of vertices C that contains each literal a that is assigned 1 by the satisfying assignment. For wach clause Ci = (a+b+c), the satisfying assignemnt sets at least one of a,b or c to 1. Whichever one a ,b or c is 1. We include the other two in our subset C. this C is of size n+2m. Also notice that eac hedge in a truth-setting component adn clause-satisfying component is covered and two of every three edges incident on a clause-satisfying component are also covered.Also an edge incident to a component associated clause Ci that is not covered by a vertex in the component must be convered by the node in C lableded with literal, for corresponding literal in Ci is 1. Supposr then the converse, namely that there is a vertex in the cover C of size at most n+2m. By construction, this set must have size exaclty n+2m, for it must conatin one vertex from each truth-setting component and two vertices from each clause satisfying component. This leaves one edge incident to a clause satisfying component that is not covered bt a vertex in the clausesatisfying component,hence all of S is satisfied. Therefore S is satisfiable if and only if G has vertex cover of size at most k. this gives us the VERTEX-COVER is NP-Complete.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.