Exam grade:100 Flashcards
Hamilton cycle
- Each vertex has two edges, one in and one out.
- If we could have an algorithm in polynomial time which tells us whether a graph has or hasn’t an Hamilton graph, we could test all the possiblities of a vertex having exactly 2 edges to see when the algorithm returns YES. Then save them and proceed to the next vertex.
NPC Reductions
We should only think of an instance of the problem we are transforming into. We take an arbitrary case of problem A and transform it to some case, which can be specific case, of problem B.
Main point is that for a verifer to “work” in polynomial time, the length of the certificate must be also polynomial in the length of the encoding of G.
That is, if the encoding of g is n, then the length of the certificate should be bounded by O(n^k), for some k.
- Explain the reduction from 3SAT to CLIQUE*
- Explain the reduction from CLIQUE to VERTEX-COVER*
- Each literal represents a vertex.
- Each vertrex is connected with all the other vertices that follow 2 conditions:
- they do not belong to its clause
- they don’t represent the value of v’s literals’ complement
- NOTE: the clique is of the size of the number of clauses in 3SAT.
- Given the set G=(V,E) with QLIQUE of size k.
- Create the contrary graph (G’ = V,E’)
- Determine whether exists a vertex cover of size |V|-k.
Reduction from HAM-CYCLE(G=(V,E)) to TSP(G’,c,k)
NOTE: G’ is always a complete graph
- Given a graph we should determine using TSP(G,c,k) if there exists an hamilotanian path.
- G’ = (V,E’), E’ = all possible vertices
- we set c(i,j) = 0 if (i,j) belongs to E
- we set c(i,j) = 1 if (i,j) does not belong to E.
Now the important part! we set k to 0. That is, we force the traveler to move only within the edges of E. So that the price he pays will cost at most 0.
- 3CNF - 01IP*
- What did you learn from this reduction*?
Main points:
-
we must express xi and xi’ individually.
- that’s why they reserved place of 2n.
- if the ith place variable is true, than the (n+i)th variable must be false and vice versa.
-
we must enforce the condition that exactly one of xi and xi’ is true.
- Think of how to “fail” if both are true
- Think of how to “fail” if both are false
- else, think of how to “pass”
- we must enforce the condition that if each clause is true we return true, else false.
3CNF to subset-problem
- sum of xi and xi’ must equal 1
- sum of value in a clause belong to {1,2,3}
Show how to solve the subset-sum problem in polynomial time if the target value t
is expressed in unary.
Two main properties taken from this question:
- The run-time depends on the length of the input. Since the length of the input is O(t), and not O(log(t)), a running time of O(nt) is polynomial a not exponential.
- Each operation on a log(t) length number takes log(t)
- We can use dynamic programming also if we search for an exact solution. We set one base case to return true, and the other to return false.
Important points regarding this reduction
- Usually its a good idea to “walk away” from the field of the first instance. If we were to make just m clauses of “F”. we were wrong. because if all the clauses are false, and y = 1 we have a solution.
- Another use of walking away is creating ourselves a new variable.
Important note aboute degree 2 vertices.
Each vertex is contained within a simple cycle.
we can view the graph as disjoint sets of cycles.
Greedy algorithm: when you need to choose an element to some group, what should you you verify?
- You should verify that the element holds a special characterization within the chosen elements.
- You should verify that the group its been added to holds a speical property that makes it a designated one.
Critical point in Kruskal and Prim
- Both algorithms rely on the assumption all the desired edges can be added to the graph.*
- If we make restrictions, we might not allow to add critical edges in the tree - thus making the algorithms wrong.*
