Week 5 (Exact Exponential Algorithms, DP on Trees)

Question 1

What are exact exponential time algorithms?

Answer 1

Since NP-hard problems can either be always correct or run in polynomial time, we can make exact exponential time algorithms that run in (2-∈)^n.n^O(1) time for some ∈>0.

Question 2

What is the branching algorithm for vertex cover?

Answer 2

For any vertex of degree >=2:
- Pick v and decrease the number of vertices by 1
- Don’t pick v and decrease the number of vertices by 3 (v+2 neighbours)

To find the minimum value, we have to solve both.

Recurrence: T(n) <= T(n-1) + T(n-3)

Question 3

What is a linear homogenous recurrence?

Answer 3

Where the RHS terms are to the power of one and there are no constants

Question 4

How can we solve branching recurrences?

Answer 4

Set T(n) = x^n:

e.g
T(n) <= T(n-1) + T(n-3)
x^n <= x^n-1 + x^n-3
x^3 <= x^2 + 1
x <= 1.46
=> 1.47^n.n^O(1)

Question 5

How can we solve 3-SAT using the branching algorithm?

(Design a O((2-∈)^N.N.M) time algorithm)

Answer 5

For each literal, there are 8 possible assignments where each literal has 3 variables.

T(n) <= 8.T(n-3) -> T(n) = 2^n. No improvement

By ignoring (F,F,F), we get:
T(n) <= 7.T(n-3)
x^n = 7.x^n-3
x^3 = 7
x = 1.913
=> T(n) = 1.913^n

Question 6

What is the travelling salesman problem?

Answer 6

Given a set C of n cities (C1,…,Cn) and a distance function dist: CxC -> R^>=0, we want to start at C1 and end at C1 after visiting all cities exactly once

Question 7

What is the brute force for the travelling salesman problem?

Answer 7

(n-1)! routes with n^O(1) time to calculate distance => 2^(nlogn)

Question 8

How can we solve the travelling salesman problem using dynamic programming?

Answer 8

• OPT[S, ci] = minimum length from c1 to ci via S
• Base case when |S|=1, for i >= 2 OPT[{ci},ci] = dist(c1,ci)
• Let cj be the last city visited before ci, guess all probabilities for cj:
  recurrence = OPT[S, ci] = min cj ∈ (S\ci) {OPT[s{ci},cj] + dist(cj,ci)}
• The number of entries is O(2^n . n) and each computation takes min over |S| entries, looks up and adds |S|-1 entries
• Running time = O(2^n . n) x O(n)

Question 9

What is the Set Cover problem?

Answer 9

Given a set U = {u1,…,un} of N elements and a set S = {S1,…,Sm} of non-empty subsets of U such that |S|=M, find a collection S’ from S of a minimum size such that the union of sets in S’ covers all elements of U

Question 10

What is the brute force of the Set Cover problem?

Answer 10

O(2^M . N . M)

Try all 2^M subsets of S and check S’ in O(N.M)

Question 11

How can we solve the Set Cover problem using dynamic programming?

Answer 11

For each non-empty subset X ⊆ U and each 1 <= j <= M, let OPT[X,j] be the minimum cardinality subset of {S1,…,Sj} that covers all elements from X. If it doesn’t cover X, set to infinity

(Recurrence is part of the excercises)

Running time =O(2^N . N . M)

Question 12

How can we solve Max Independent Set using dynamic programming?

Answer 12

Root the tree T at any arbitrary vertex r

OPT[v] = the maximum independent set for T(v), where T(v) is the subset of T

Base case: OPT[n] = 1 for all leaves n
Final answer: OPT[r] where T(r) is the full tree

OPT[v] = max{∑ x ∈ child[v] OPT[x] ; 1 + ∑ y ∈ grandchild[v] OPT[y]}

Correctness: If v is in the independent set, we skip its children. Else, we include its children

Running time: O(n) entries, with look-up of O(n) existing entries, O(n) additions and one max operation.

Total time: O(n^2)

Question 13

How can we solve Min Vertex Cover using dynamic programming?

Answer 13

Root the tree T at any arbitrary vertex r

OPT[v] = the minimum set for T(v), where T(v) is the subset of T

Base case: OPT[n] = 1 for all leaves n
Final answer: OPT[r] where T(r) is the full tree

OPT[v] = min{|children| + ∑ x ∈ grandchild[v] OPT[x] ; 1 + ∑ y ∈ child[v] OPT[y]}

Correctness: If v isn’t in the set, all of its children have to be. If v is in the set, all edges are covered by v

Running time: