CS 170, Spring 2020 HW 12 A. Chiesa J. Nelson
In the Undirected Rudrata path problem (aka the Hamiltonian Path Problem), we are given
a graph G with undirected edges as input and want to determine if there exists a path in G
that uses every vertex exactly once.
In the Longest Path in a DAG, we are given a DAG, and a variable k as input and want to
determine if there exists a path in the DAG that is of length k or more.
Is the following reduction correct? Please justify your answer.
Undirected Rudrata Path can be reduced to Longest Path in a DAG. Given the undirected
graph G, we will use DFS to find a traversal of G and assign directions to all the edges in G
based on this traversal. In other words, the edges will point in the same direction they were
traversed and back edges will be omitted, giving us a DAG. If the longest path in this DAG
has |V |− 1 edges then there must be a Rudrata path in G since any simple path with |V |− 1
edges must visit every vertex, so if this is true, we can say there exists a rudrata path in the
original graph. Since running DFS takes polynomial time (O(|V | + |E|)), this reduction is
valid.
4 (3,3)-SAT
Consider the (3,3)-SAT problem, which is the same as 3-SAT except each literal or its nega-
tion appears at most 3 times across the entire formula. Notice that (3,3)-SAT is reducible
to 3-SAT because every formula that satisfies the (3,3)-SAT constraints satisfies those for
3-SAT. We are interested in the other direction.
1
3 A Reduction Warm-up
2 Opting for releasing your solutions
We are considering releasing a subset of homework submissions written by students for stu-
dents to see what a full score submission looks like. If your homework solutions are well
written, we may consider releasing your solution. If you wish that your solutions not be
released, please respond to this question with a ”No, do not release any submission to any
problems”. Otherwise, say ”Yes, you may release any of my submissions to any problems”.
List the names and SIDs of the members in your study group. If you have no collaborators,
you must explicitly write none.
1 Study Group
CS 170 HW 12
CS 170, Spring 2020 HW 12 A. Chiesa J. Nelson
Show that (3,3)-SAT is NP-Hard via reduction from 3-SAT. By doing so, we will have
eliminated the notion that the ”hardness” of 3-SAT was in the repetition of variables across
the formula.
Give a precise description of the reduction and prove its correctness.
5 Public Funds
You are looking to build a new fence for your mansion, to keep out pesky people protesting
profligate purchases. You have m bank accounts at your disposal to use to pay for your fence;
each account i has a balance of bi. You must choose one of n options for your fence; each
fence j costs cj dollars. You would like to withdraw from at most k of the bank accounts
to build the fence, and due to peculiar UC accounting rules, if you use a particular bank
account, you must use the whole balance (all bm dollars.)
Determine whether it is possible to exactly pay for some fence j; that is, whether there is
a j between 1 and n such that you can withdraw exactly cj dollars given the bank account
balances b1, . . . , bm, the fence costs c1, . . . , cn, and k, and if so return the corresponding choice
of fence and set of bank accounts that you withdraw from.
Prove that Public Funds is NP-Complete. Look at problems from the textbook for pos-
sible NP-Complete problems!
6 Dominating Set
A dominating set of a graph G = (V,E) is a subset D of V, such that every vertex not in D
is a neighbor of at least one vertex in D. Let the Minimum Dominating Set problem be the
task of determining whether there is a dominating set of size ≤ k. Show that the Minimum
Dominating Set problem is NP-Complete. You may assume that G is connected.
7 Reduction to 3-Coloring
Given a graph G = (V,E), a valid 3-coloring assigns each vertex in the graph a color from
{0, 1, 2} such that for any edge (u, v), u and v have different colors. In the 3-coloring problem,
our goal is to find a valid 3-coloring if one exists. In this problem, we will give a reduction
from 3-SAT to the 3-coloring problem, showing that 3-coloring is NP-hard.
In our reduction, the graph will start with three special vertices, labelled “True”, “False”,
and “Base”, and the edges (True, False), (True, Base), and (False, Base).
(a) For each variable xi in a 3-SAT formula, we will create a pair of vertices labeled xi and
¬xi. How should we add edges to the graph such that in any valid 3-coloring, one of
xi,¬xi is assigned the same color as True and the other is assigned the same color as
False?
(b) Consider the following graph, which we will call a “gadget”:
2
CS 170, Spring 2020 HW 12 A. Chiesa J. Nelson
Show that in any valid 3-coloring of this graph which does not assign the color 2 to any
of the gray vertices, the gray vertex on the right is assigned the color 1 only if one of the
gray vertices on the left is assigned the color 1.
(c) We observe the following about the graph we are creating in the reduction:
(i) For any vertex, if we have the edges (v, False) and (v, Base) in the graph, then in
any valid 3-coloring v will be assigned the same color as True.
(ii) Through brute force one can also show that in the gadget, for any assignment of
colors to gray vertices such that:
(1) All gray vertices are assigned the color 0 or 1
(2) The gray vertex on the right is assigned the color 1
(3) At least one gray vertex on the left is assigned the color 1
Then there is a valid coloring for the black vertices in the gadget.
Using these observations and your answers to the previous parts, give a reduction from
3-SAT to 3-coloring. Prove that your reduction is correct.
3