Requirements

This 6th assignment lets you get familiar with concepts of NP-completeness and how to prove the hardness of a problem. It is worth 5% of your total course marks.

There are 3 problems which are extracted from the previous COMPSCI 320 exams.  We hope that Assignment 6 will be a good preparation for the final exam.

Problem 1:   Recall that a Hamiltonian cycle in a digraph G = (V,E) is a permutation P = v0 ,v1 , . . . ,vn −1

of V with n nodes such that  (vi ,v(i+1)  mod  n ) ∈ E for all 0 ≤ i < n.  Let DHC be the problem of

deciding if a digraph has a Hamiltonian cycle.  Similarly, let 3DHC be the problem of deciding if a digraph has at least three different Hamiltonian cycles.  We assume digraphs are simple and do not contain loops or multi-edges.

1.  Show that 3DHC is in NP (1 mark).

2.  Show that DHC ≤P  3DHC (1 mark).

Problem 2:    Given a graph of n nodes, HamCycle is the problem that asks if we can find a cycle in a graph visiting all nodes.  Given a graph of n nodes, let k-HamCycle be the decision problem that asks if we can find a cycle visiting n − k nodes for some fixed constant 1 ≤ k  ≤ n − 3.  Show that HamCycle ≤P  k-HamCycle (1 mark).

Problem 3:    Given the following Graphical Steiner Tree problem.  We are given an undirected graph G = (V,E), a set X ⊆ V of special nodes (e.g.  terminal nodes), and a number k .  We want to decide whether there is a set E\  ⊆ E of at most k edges so that in the new subgraph G\ = (V\ ,E\ ) has the following properties:  (a) X ⊆ V\  (e.g. V\  contains X); (b) G\  is connected; and (c) |E\ | ≤ k .

An informal definition of Graphical Steiner Tree is that given a graph G = (V,E) with a set of special nodes X, you are asked to connected X using as few edges as possible.

In the graph below, the special nodes are in  blue, the edges you have to use to connect them are in black. Besides the special nodes, the subgraph might contain other nodes to be a connected component.

1.  Show that Graphical Steiner Tree is in NP (1 mark).

2.  Show that Vertex Cover ≤P  Graphical Steiner Tree (1 mark).