Self reduction Flashcards
Decision problem
Problem whose answer is yes/No
Search problem
Problem whose solution is the answer
Optimization problem
Problem whose answer is the best possible solution
Vertex cover S of G(V,E)
A vertex cover S of G(V,E) is a set of vertices whose removal result in an edgeless graph.
V is a trivial vertex cover.
V - “any” vertex is another vertex cover
Self reduction
If the reduction of the “search version of X” to the”decision version of X” can be done in polynomial time, then we say X self reduces in polynomial time
Vertex-cover self reduction
Check
Independent Set self reduction
Consider I have a black-box that answer the decision problem of Independent set with yes or no. Also consider a Graph G(V,E) with a Independent set of size K. I remove any first vertex and I check the blackbox; If I stilll have a vertex cover of size K, I remove another vertex. If when removing the vertex , I dont have an indepndent set, I keep that vertex ( it is one of my indpendent set) and remove another and check. We keep on until the size of fixed vertices is K (equal to the size of IS)
3 coloring self reduction
Consider I have a black box that answer the decision problem of 3 coloring. Consider I have a Graph G that is 3 colorable. I choose a vertex and I color it with color 1 , it is adjacent colors are colored with different colors. I add an edge from the vertex and check if the graph if still 3 colorable, if so I add another edge, else if not I color these 2 vertices with same color and move to the next vertex.
Minimum vertex cover
Minimum vertex cover is a vertex cover that has the smallest number of vetices among all possible vertex covers
Minimal vertex cover
A minimal vertex cover is a vertex cover that does not contain another vertex cover
A minimum is minimal, but a minimal is not necessarily a minimum
True
How to check a vertex cover in polynomial time
For each edge (uv) do
if (Sol(u)==0 & Sol (v)==))
return false
return true
