Question: Assume you have been given an encoding of an instance of VERTEX - COVER problem as an instance of INDEPENDENT - SET problem. What is

Assume you have been given an encoding of an instance of VERTEX-COVER problem as an instance of INDEPENDENT-SET problem. What is the planned direction of the polynomial time reduction?
VERTEX-COVER <=p INDEPENDENT-SET or
INDEPENDENT-SET <=p VERTEX-COVER
Seems like both the scenarios could be possible and could to reducible to polynomial time since vertex cover problem is encoded.
If VERTEX-COVER is intractable, can we conclude that INDEPENDENT-SET is intractable?
YES or NO (No is the answer)
If INDEPENDENT-SET is intractable, can we conclude that VERTEX-COVER is intractable?
YES or NO (Yes is the answer)
If VERTEX-COVER is efficiently solvable, can we conclude that INDEPENDENT-SET is efficiently solvable?
YES or NO (Yes is the answer)
If INDEPENDENT-SET is efficiently solvable, can we conclude that VERTEX-COVER is efficiently solvable?
YES or NO (No is the answer)
Note-- i need explanationation how it is yes or no
and also i need a unique answer like which is greater than OR less than polynomial time reduction
3-SAT,INDEPENDENT SET, VERTEX COVER, SET COVER

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!