Reductions Flashcards
Assume problem A with input x
We want to use Reduction from A to B.
What are the steps?
- Apply x to f to get f(x)
- where f(x) is an input for problem B
- Apply f(x) to an algorithm for problem B to get y
- Apply y on g to get an output for problem A
What are the steps in proving a reduction is correct?
Correctness proof structure:
- Correctness statement
- Explains what we need to prove
- Helping statement
- Usually suggests equivalence between some result of problem A to some result of problem B
What is the sub-strings problems?
What is the problem B for which the sub-strings problem can be solved using reduction?
- What is the input translation?
- What is the correctness statement?
- What is the helping statement?
Sub-strings problem
Input: a sequence of n words of length 3. W={W1,W2,…,Wn}
Definition: A legal string T for W is a string that satisfies:
- It is of length n+2
- The set of all its consecutive sub-strings of length 3 is exactly W.
Output: is there exists a legal string T for W()
- A decision problem
Problem B: “finding an Hamilton path in a directed graph”
- Input translation:
- Directed graph G=(V,E)
- V=W
- E = {(Wi,Wj): Wi’s last 2 chars = Wj’s first 2 chars}
- Directed graph G=(V,E)
-
Correctness statement:
- There is an Hamilton path for G if and only if there is a legal string T for W.
- Proof: right from the helping statements.
-
Helping statement 1:
- Existence of a legal string T for W implies existence of an Hamilton path for G
-
Proof:
- Decompose T into n words of length 3 by setting Wi to be a word starting at Ti to T(i+2).
- By defintion, all the Wi’s form W
- W=V thus Wi is a vertex in G
- By how we formed E, there’s an edge between Wi to W(i+1)
-
Helping statement 2:
- Existence of Hamilton path for G implies existence of legal string T for W.
-
Proof:
- Assume Hamilton path P={V1,..Vn}
- Define T={A,B,C1,C2,C3..,C,2}
- W1 = ABC1, W1 = BC1C2, and Wi determine the 3 length word in T starting at T_i.
What is an Hamilton path and what’s its best run-time Algorithm?
What is an Euler path and what’s its best run-time algorithm?
It is a path which visits every vertex exactly once.
It is NP complete!
Is is a path which visits every edge exactly once.
Best run-time O(|E|+|V|), actually possible in O(|E|)
What is the problem C for which the sub-strings problem can be solved using reduction, where C is not NP-HARD?
What is the input translation?
What is the correctness statement?
What is the helping statement?
Problem C:
- “finding an Euler path in a directed graph”
Input translation:
- V = {vi | first two or last two chars of some Wi}
- E = W. That is, edge Wi connect its Seifa to its Reisha.
Correctness statement:
There is an Euler path for G if and only if there is a legal string T for W.
Proof:
right from the helping statements.
Helping statement 1:
Existence of a legal string T for W implies existence of an Euler path for G
Proof:
Decompose T into (n+1) consecutive words Vi of length 2 by setting Vi to be a word starting at Ti to T(i+1).
Let us look at (Vi|Vi+1). Because T is a legal solution for W, (Vi|V(i+1)) is a word Wi in W.
According to the translation function: there’s an edge in E from Wi to Wi+1, and the path:
P= {W1,W2,..,W(n+1)} is an Euler path. Because they form n unique words in W.
Helping statement 2:
Existence of an Euler path for G implies existence of legal string T for W.
Proof:
Assume an Euler path P={V1,..V(n+1)}
By the input translation function: there’s an edge between Vi and V(i+1), thus Vi|V(i+1) = Wi in W.
Because Vi shares two chars with Vi+1, we can form T= V1|V2|…|Vn which is of size n+1.
Define Euler’s path
- Desctibe the theorem:*
- In connected and directed graph there exists an Euler path if there exist vertices s and t such that:*
- A path which passes through all edges, but visits each one of these exactly once.*
- For each v!=s,t ; in(v)=out(v)*
- For s ; in(s) + 1= out(s)*
- For v ; in(s) = 1 + out(s)*
