Assignment 6

CS-GY 6033 INET Fall 2024

Due date: Dec 16th 2024, 11:55pm

Question 1:  Complexity classes

12 points

Short answers!

Consider the following problems.   For  each  problem,  determine  if  it  is  possible  that  there  exists  a polynomial-time algorithm for solving that problem.  Justify your answer using what is currently know about their complexity classes.

● Travelling salesman problem

● n × n chess

● The Halting Problem

● Vertex Cover

● Integer Factorization

● Given a set of n items, where each item has a specific weight, can we pack them onto K trucks where each truck can hold at most weight B .

Question 2

12 points

Below are a list of runtimes for decision problems.  For each runtime, determine if the corresponding problem is in P or EXP or both or neither.

1. T(n) = (log n)6

2. T(n) = log(n6 )

3. T(n) = (6n)6

4. T(n) = n + 1000

5. T(n) = nn

6. T(n) = 3n + n6

7. T(n) = 3n2 +6

Question 3

27 points

For each problem below, determine whether or not there is a known polynomial-time algorithm for solving the problem. You must justify why there is no known poly-time algorithm OR identify a poly-time procedure that solves the problem.

(a) Consider a the political meeting which has n participants.  There are m issues which are to be discussed at the meeting. Each participant must list exactly two issues that interest them.  The organisers would like select at most k issues, so that each person is interested in at least one of the selected issues.

(b) A graph G has n vertices and m edges.  The problem is to determine if G contains a simple cycle of length at least 3.

(c)  A graph G has n vertices and m edges. The problem is to determine if G contains a simple cycle of length at least k

(d) A directed graph G contains n vertices and m edges. The problem is to determine if there is path from vertex s to every other vertex in the graph.

(e) A directed graph G contains n vertices and m edges. The problem is to determine if there is path from vertex s to and from every other vertex in the graph.

(f) A directed graph G contains n vertices and m edges.  The graph is not weighted.  The problem is to determine if there is path from vertex s to every other vertex in the graph, where the number of edges in the path must be at most k.

(g) A directed graph contains n vertices and m edges. The problem is to determine if G is a DAG.

(h) An undirected graph has weighted edges.  The problem is determine if there is a path that starts at vertex s and travels to vertex t where the sum of the edge weights is less than k.

(j) An undirected graph has weighted edges.  The problem is determine if there is a path that starts at vertex s and visits all vertices exactly once, where the sum he edge weights is less than k.

Question 4

10 points

Prove that the following problem is NP-complete using a reduction from either :  Vertex Cover, Inde- pendent Set, Dominating Set, or Clique.  Recall the two steps that are necessary in order to show that a problem is NP complete.

A set of n people attend a political meeting, where m issues are to be discussed.  Each person attending has created a sublist of issues (selected from the main set of m issues) that they are most interested in. The organisers would like to select at most k issues so that each person is interested in at least one of the selected issues. The problem is to determine if it possible or not.

Question 5

10 points

Prove that the following problem is NP-complete using a reduction from either:  Vertex Cover, In- depednent Set, Dominating Set, Subset Sum, Hamiltonian cycle, or Clique. Recall the two steps that are necessary in order to show that a problem is NP complete.

A graph G consists of a set of n vertices and m edges. A specific vertex is labelled S.  The problem is to determine if there is a simple path that starts at vertex S and visits all other vertices in the graph.