How the optimization version of vertex cover problem

Assignment Help Computer Engineering

Reference no: EM131952485

Assignment

1. [Self-reducibility] Show how the optimization version of vertex cover problem is polynomial time-reducible to its decision version. The optimization version, known as min vertex cover problem, is this -- "given a graph G, find the minimum set of vertices that cover all the edges in G". The decision version is this -- "given a graph G and a constant k, is there a vertex cover of at most k vertices?" Here, we say a vertex "covers" an edge if and only if the vertex is an end-node of the edge.

2. [Polynomial-time reduction] Consider the construction of a graph (a.k.a. "gadget") studied in class when proving the polynomial-time reducibility 3-SAT ≤p INDEPENDENT-SET. The construction steps are shown below.

1. Add 3 vertices for each clause, one vertex for each literal.
2. Connect the 3 vertices in each triangle.
3. Connect the vertex of a literal and its negation between triangles.

Show that this construction take polynomial time. Assume a 3-SAT formula Φ is given as a text string that is linearly parsed into literals and clauses. It is adequate to give an informal but accurate analysis of the construction running time complexity in big-O. If you will, however, feel free to actually write the construction algorithm in pseudocode to analyze the running time complexity.

Reference no: EM131952485

Questions Cloud

Share your experiences with training : Share your experiences with training. What are some of the advantages and disadvantages of the different training methods?

Prepare the journal entries to record the transactions : Prepare the journal entries to record the transactions of Beach Supplies Ltd up to and including that which took place on 30 June 2017

Overcome shyness around women : The client, a college sophomore, wants to overcome his shyness around women. He does not date and even does his best to keep away from women

What is the productivity per labor hour : What is the productivity per labor hour?What is their percentage change in productivity per labor hour?

How the optimization version of vertex cover problem : [Self-reducibility] Show how the optimization version of vertex cover problem is polynomial time-reducible to its decision version.

What is the probability that the system will work : What is the probability that the system will work? Draw the diagram of the new system.

Write down the normal form representation of this game : Write down the normal form representation of this game, describing the three essential elements of the game.

Should sharon jones outsource its it services : Calculate the total costs of the production departments (clothing and eyewear) after the support department costs of information technology.

What sort of distributed system architecture would you use : What sort of distributed system architecture would you use for this problem, and why? Why is it better to reuse this function than write out 100 element vector?

User Account

All Pages