Data Structure Lecture Note (Week 6, Lecture 16)

Reduction: vertex cover to hitting set

hitting set problem: given a set O of objects and a collection C of subsets of O. Whether there is a set of K objects from O such that for each c in C, there is one element from K in c.

e.g. O = {1,2,3,4,5} C= {{1,2}, {3,4}, {3,2,5}}, K=3, then the set could be {1,3,5}; K =2, the set can be {2,3}; but if K=1, no solution

Reduction from vertex cover to hitting set:

G = (V,E) is an instance of vertex cover with constant K, so our goal is to find a size K subset S of V, such that all edges are having at least 1 endpoints in S. Let O = V, C = {{u,v}: for any (u,v) in E}, K=K, therefore, this is an instance of a hitting set that you need to pick a set of size K to cover all sets in C.

Set Cover Problem

Given a set O of objects and a collection C of subsets of O. Whether there is a subset D of C whose size is K and such that $U_{\delta\in D}\delta = O $

3 - SAT reduction to Set cover

Let a 3-sat instance be $C_1 \wedge C_2\wedge …\wedge C_M $ and each $C_i = x_a \vee x_b \vee x_c$Ci​=xa​∨xb​∨xc​ or $x_a \vee x_b \vee \neg x_c$xa​∨xb​∨¬xc​ and so on. Let the number of variables be N so there are N variables $x_1, x_2,…,x_N $

We want to convert it to a set cover problem with right choice of objects, subsets, and K.

$\forall x_i,$∀xi​, create 4 virtual variables $v_i, vt_i, vf_i, G_i$vi​,vti​,vfi​,Gi​ into O

Add subsets ${v_i, vt_i }, {v_i, vf_i} $ into C for each i. This means that $x_i$xi​ is assigned to F or T, we will let K = 2N and $v_i$vi​ will not be in any other subsets so that we have to pick N subsets from this type such that all $v_i$vi​ are covered.

For each I\i, let $T_{x_i} = {C_j: \text{such that clauses j is satisfied when } x_i = True} + {vt_i, G_i}, F_{x_i} = {C_j: \text{such that clauses j is satisfied when } x_i = False} + {vf_i, G_i} $ Then, in order to pick all G_i, the algorithm has to select one from $T_{x_i} or F_{x_i}$Txi​​orFxi​​ but not both, because K = 2N and first N selections has to be one for each $v_i$vi​

Gi forces you to pick N objects. vi forces you to pick at least N objects.

So $O = \{C_1, C_2,...,C_M \} \cup \{v_1, vt_1,vf_1,G_1, v_2, vt_2,vf_2,G_2,...\}$O={C1​,C2​,...,CM​}∪{v1​,vt1​,vf1​,G1​,v2​,vt2​,vf2​,G2​,...}

$C = {T_{x_1}, F_{x_1}, T_{x_2}, F_{x_2} … , { v_1, vt_1 }, {v_1, vf_1} } $

$T_{x_1} = \{C_1, C_3, vt_1, G_1\}$Tx1​​={C1​,C3​,vt1​,G1​} clauses that will be true if $x_1$x1​ is true PLUS vt, G

$ F_{x_1} = {C_2, C_7,vf_1, G_1} $clauses that will be true if $x_1$x1​ is false PLUS vf, G

2-SAT problem is solvable in polynomial time. In SCC manner

$\neg x\vee y = x \Rightarrow y$¬x∨y=x⇒y

Implication graph: each variable has 2 nodes, and if there is a clause of $x\to y$x→y, we draw an edge from x to y.

Dynamic Programming

Typically, it will choose among multiple subproblem combinations and try to figure out suitable subproblems

First example: LIS (longest increasing subsequence)

1st attempt: can we split the problem in half, solve them independents then merge?

But this cannot merge!

A = [1,4,2,3,6,5]

A1 = [1,4]; A2 = [3,6]

but when you merge, you can only get 1 4 6

But the best answer is 1 2 3 6

2nd attempt

Let R(j) be the subproblem of finding LIS in A from index 0 to j

Another def of subproblem could be: Let P(j) be the subproblem of finding LIS in A from index 0 to j such that the LIS has to include A[j]

$P[j] = \max (\max_{i\le j-1} ( (P[i]+1) * int(A[j] > A[i]) ) , 1 ) $

Notice here, P[j] is cleaner than R[j] since the dependnecy is blocked by forcing A[j] to be included in the solution, therefore you don’t need to worry about whether inheriting solution from subproblem will be feasible or not.

Principles:

1. Only depending on the past, i.e. problem of a smaller scale.

Optimial subproblem structure: your combination of subproblems should cover all the cases of the possible optimal solutions for the super problem

2. If you have to store every possible solution, it’s very likely your DP is not working

3. If you feel hard to write recursions, try to add more constraints to your subproblem definitions, such as forcing the last letter to be included as the last problem