Question 1: 2-SAT (25 points)
Recall that a 2-SAT Instance consists of n variables x1, . . . , xn and m clauses C1, . . . , Cm where each clause Ci = `i1 _ `i2 is the disjunction of two literals. In this problem you will develop a linear time algorithm to solve 2-SAT by reducing the 2-SAT instance to the Strongly Connected Components problem. Given we construct directed graph G defined as follows:
Nodes: For each literal ` we add a node v` (2n nodes total)
Notation: Given a node v` we use v` to denote the node corresponding to `. For example if`=xthenv` =vx.
Edges: For each clause C = ` _ `0 we add two directed edges (v`, v`0 ) and (v`0 , v`).
Part 0 Suppose that we have a directed path P = v`1,v`2,…,v`k in G . Explain why P = v`k,…,,v`2,v`1 is a valid directed path in G .
Part 1: Suppose that for some literal ` the nodes v` and v` are in the same strongly con- nected component in G . Show that the 2-SAT instance is not satisfiable.
Part 2: Suppose that for every literal ` the nodes v` and v` are in separate strongly con- nected components in G . Show that the 2-SAT instance is satisfiable.
Part 3: Describe an O(n+m) time algorithm which solves the 2-SAT problem. If the 2-SAT formula is not satisfiable then the algorithm should output “no-solution” otherwise the algorithm should output a satisfying assignment. You should analyze the running time of your algorithm and give a brief (but clear) explanation of why your algorithm is correct.
Hints: It may be helpful to think of directed edges as logical implications. You may find it easier to solve parts 2 and 3 together.
Solution:
Resources: Collaborators:
2
Question 2 (25 points)
Let Bipartite(G) be a predicate that outputs 1 if and only if G is bipartite and let VertexCover(G, k) be a predicate that outputs 1 if and only if G has a vertex cover of size k. Let AND(G, k) = Bipartite(G)⇥VertexCover(G,k)(resp. XOR(G,k)=Bipartite(G) VertexCover(G,k))be
the predicate that outputs 1 if and only if G is both bipartite and has a vertex cover of size
k (resp. exactly one of the claims holds). We now define the decision problem AND: Given an undirected graph G = (V, E) and an integer k 1 decide whether or not AND(G, k) = 1. Similarly, we can define the decision problem XOR: Given an undirected graph G = (V, E) and an integer k 1 decide whether or not XOR(G, k) = 1.
One of the two decision problems is decidable in polynomial time and the other is NP- Complete. Your mission is to identify which problem is easy and which problem hard. You should give a polynomial time algorithm to solve the easy problem and you should prove that the other problem is NP-Complete.
Hint: The Ko ̈nig-Egerv ́ary Theorem says that in a bipartite graph the size of the maximum matching is equal to the cardinality of the minimum vertex cover.
Solution:
Resources: Collaborators:
3
Question 3: Puzzle Challenge (25 points)
Alice has designed a challenging puzzle to submit to the World Puzzle Federation. Her dream is that her puzzle appears in the 2021 U.S. Puzzle Championship. The puzzle is on an n ⇥ m grid, where each square of the grid may be empty, or occupied by a cross piece, or occupied by a circle piece (see figure for reference). Given an initial configuration of circles and crosses on the n ⇥ m grid, the goal of the puzzle is to remove some pieces (can be circle or cross pieces or both), so that the remaining pieces satisfy both the constraints defined below:
1. Every row contains at least one piece.
2. No column contains pieces of both types, i.e., every column either contains only circle pieces or only cross pieces or neither.
In order to test the di culty of her puzzle, she asks her friend Bob to try his hand at it. Bob quickly realizes that there are initial configurations for which solving this puzzle is impossible, and worse, even deciding whether this puzzle is solvable is actually NP-hard.
Given an initial configuration of circles and crosses, prove that it is NP-hard to determine whether this puzzle is solvable.
1. Clearly state the known NP-hard problem you are reducing from, say A, and describe the polynomial-time transformation that takes an instance of A and converts it to an instance of the puzzle. (10 points)
Hint. Reduce from 3-SAT.
2. Prove that the puzzle has a solution if and only if the known NP-hard problem A has a solution. (15 points)
Solution:
Resources: Collaborators:
4
Question 4: Road Trip with Tolls (25 points)
Let G = (V,E) be a directed graph representing the US road network. Raymond wants to drive his car from his house in West Lafayette (node s) to visit his friend who lives at node t in Pittsburgh. Each edge e has a time cost c(e) and a toll fee d(e), where both are non-negative integers. Suppose that Raymond has enough budget B for the trip.
1. (12 pts) Raymond wants to know if it is possible to reach his friend’s place t in time at most T with his budget B. Help Raymond prove that this problem is NP-complete with general inputs (that is, general G, s, t, c, d, B, and T).
(Hint: Show a reduction by using the Set-Partition problem. We recall that in this problem, we have a set of positive integers I = {i1,i2,…,in} where the sum is S = Pnj=1 ij, the goal is to determine if there is a subset I0 ⇢ I such that Pij2I0 ij = S/2. You can consider a “line-like” graph from s to t with n 1 vertices between them, and there is a pair of “parallel paths” between each pair of neighbor vertices.)
2. (4 pts) After realizing that this problem is NP-complete, Raymond knows that it may take him a lot of time to figure out how to visit his friend. So, he decides to ask Rohan, who is an expert in US road network that can quickly answer the following YES/NO question: given u,v 2 V, B0 and T0, is there a u v path with total fee at most B0 and time at most T0? This time, Raymond wants to know the minimum time T⇤ needed to reach his friend’s place without exceeding his budget B. Help Raymond e ciently find T ⇤ by asking Rohan. How many questions should he ask?
3. (9 pts) Finally, Raymond figured out T⇤. Now he needs to know the best route before visiting his friend. Help Raymond e ciently find an a↵ordable route (which takes T⇤ time) by asking Rohan. How many questions should he ask?
Solution:
Resources: Collaborators:
5