1 Suppose that A(G, s, t) is a polynomial-time algorithm that checks if there exists a Hamiltonian path from vertex s to vertex ¢ indirected graph G

Subject:WritingPrice:26.99 Bought3

Share With

1 Suppose that A(G, s, t) is a polynomial-time algorithm that checks if there exists a Hamiltonian path from vertex s to vertex ¢ indirected graph G. Show that, in this case, there is a polynomial-time algorithm B(G, s, t) that finds a Hamiltonian path from vertexs to vertex ¢ in directed graph G if such a path exists and reports that there is no such a path otherwise.

2. 

A field is divided into n beds each of which is divided into m cells. Beds are separated by fences, so that, from a bed, it is not possible to see what happens in another bed. There are no fences between cells of the same bed. In some cells, there are saucers with milk; in some others, there are pieces of cheese; the remaining cells are empty. Is it possible to place cats in milk cells and mice in cheese cells so that, for each  < m, the ith cell in at least one bed was occupied by a cat or a mouse, while no cat could see any mouse (i.e., there were no cat and mouse sharing a bed)?

Prove that this problem is NP-complete or give a polynomial-time algorithm that solves it.

3. 

Consider the following version of the Travelling Salesman problem:

Input: A complete undirected graph with at least four vertices and weighted edges.

Output: A minimum-weight cycle that visits every vertex exactly once.

In which of the following cases removing a vertex from the graph can lead to a solution of a greater cost (i.e., to a greater minimum weight of a cycle)?

 

1. All weights are negative numbers.

2. Every vertex is a point on a plane, and the weight of an edge is the Euclidean distance between the points it connects.

Explain your answer by giving an example when the solution's cost increases or proving that this cannot happen.
 

4. 

Given n items and their weights w1, we,..., Wn, we have to pack them into knapsacks each of which can carry items with the total weight of at most W. We have w; < W for all i. Let us take a knapsack and start packing it with items in an arbitrary order until we come across an item that no longer fits in the knapsack. Then we take another knapsack and pack it in the same manner. We continue like this until we have packed all the items.

(Assume that we have as many knapsacks as needed.)

Show that this algorithm may sometimes use more knapsacks than it is necessary. Is it true that the number of knapsacks used by the algorithm is never more than twice the minimal number of knapsacks needed to pack all the given items? Prove that this is the case or give a counterexample.

5. 

Let A(G, k) be a polynomial-time algorithm that, for arbitrary graph G and natural number k, with probability at least 1/2, returns 1

if G has a clique of size k and, with probability 1, returns 0 if G has no such a clique.

Let B(G, k) be a polynomial-time algorithm that, for arbitrary graph G and natural number k, with probability at least 1/2, returns 1

if G has an independent set of size & and, with probability 1, returns 0 if G has no such an independent set.

Describe a polynomial-time algorithm C(G, k, m) that, for arbitrary graph G and natural numbers k and m, with probability at least

1/2, returns 1 if G has a clique of size k and an independent set of size m and, with probability 1, returns 0 otherwise.