CS170 -     HW 11 - Solved

1           Study Group
List the names and SIDs of the members in your study group. If you have no collaborators, write “none”.

2           A Reduction Warm-up
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.

3           Path TSP and Cycle TSP
In the Traveling Salesman Problem (TSP), we are given an undirected graph with nonnegative weights and asked to find a minimum weight cycle that contains each vertex exactly once.

In the s-t Traveling Salesman Problem (s-t TSP), we are given an undirected graph with non-negative weights, two vertices s and t, and are asked to find a minimum weight path that starts at s, visits all other vertices exactly once, and ends at t.

Show that if there is an algorithm to solve TSP, then you can use it to solve s-t TSP.

4           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.

5           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”:

 

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.