COMP 3170 Winter 2024 Assignment 2
Due by: Friday February 2, 2024 4:30 pm. on Crowdmark
Instructions for Students
• Please answer each question.
• Provide sufficient detail in your answers and do not give your proof in point form (that is, use complete sentences instead).
• Hand in your assignment by the due date and time. No late assignments accepted.
• Make sure your solution is legible and not blurred.
• Ensure that your submission is legible and correctly oriented in Crowdmark.
(Question1): Consider the following two decision problems (Note: The optimization versions of these problems are much more common).
Consider the following two decision problems (Note: The optimization versions of these problems are much more common).
Problem A: Given a complete graph G = (V, E), a cost function c : E → Z+ and a positive integer k, the problem is to decide whether there is a path P that contains every vertex of V such that the costofP (thesumofthecostsofalltheedgesinP)isatmostk.
Problem B : Given a complete graph G = (V, E), a cost function c : E → Z+ and a positive integer k, the problem is to decide whether there is a cycle C that contains every vertex of V such that the cost of C (which is the sum of the costs of all the edges in C) is at most k.
Give a (polynomial-time) reduction from Problem A to Problem B and prove that it is a reduction. That is, you must specify the construction f unambigously and prove the the following:
(a) Computing f(I) takes polynomial time, for any instance I of Problem A,
(b) If I is a yes instance of Problem A, the f(I) is a yes instance of Problem B, and
(c) If f(I) is a yes instance of Problem B, then I is a yes instance of Problem A. Notation
• The symbol Z+ denotes the set of positive integers.
• A graph G = (V, E) is *complete* if there is an edge between any two vertices u, v ∈ V . That is,
uv ∈ E for every distinct u, v ∈ V .
(Question2): Consider the following two problems:
Problem A: Given a graph G = (V,E), the problem is to decide if G contains a path that contains every vertex.
Problem B: Given a graph G = (V, E) and an integer k, the problem is to decide if G has a spanning tree T with maximum degree at most k.
Give a (polynomial-time) reduction from Problem A to Problem B and prove that it is a reduction. That is, you must specify the construction f unambigously and prove the the following:
(a) Computing f(I) takes polynomial time, for any instance I of Problem A, 1
(Question3):
(b) If I is a yes instance of Problem A, the f(I) is a yes instance of Problem B, and (c) If f(I) is a yes instance of Problem B, then I is a yes instance of Problem A.
Suppose you have an algorithm A(G, k) that solves the decision version of the independent set problem for input graph G = (V,E) and positive integer k in time O(f(n)), where n denotes the number of vertices in the input graph instance.
Give an algorithm (using pseudocode) that solves the optimization of the independent set problem in time O(f(n) × log2 n). Ensure you justify why your algorithm has the stated running time. Your algorithm only needs to return the size of a largest independent set (that is, it doesn’t need to return an independent set of largest size).
