CSC363 UTM Winter 2024 Assignment 3 Due Wednesday March 27
You are not allowed to post the assignment questions anywhere; however, you are allowed to search the internet (just cite your resources if you find any). You are also allowed to bounce ideas off classmates and TAs, but at the end, you must write your own solutions.
Q1. Let f(n) = aknk + . . . + a1n + a0. Prove that f(n) = O(nk). In other words, show that there exists n0,M natural numbers such that ∀n > n0,|f(n)| ≤ Mnk.
Hint: Use the triangle inequality and the fact that nj ≥ ni for all natural n when j > i.
Q2. Let L be some decision problem (you can think of it as a subset of N, or as a subset of {0, 1}∗).
Prove that, there exists a polynomial time decider for L iff L ∈ Sk∈N TIME(nk).
Q3. A Hamiltonian path is a path in the graph between two vertices which visits each vertex exactly once. A Hamiltonian cycle starts and ends at the same vertex and visits every vertex exactly once.
Define the following languages
HAMPATH = {(G,s,t): G is an undirected graph with a Hamiltonian path from s to t} HAMCY CLE = {G: G is an undirected graph with a Hamiltonian cycle }
Prove that HAMPATH ≡p HAMCY CLE.
Q4. The 3-colouring problem is the following: Given a map consisting of connected countries, assign each country one of three colours (say red, blue, and green) so that no two bordering countries share the same colour.
The set of 3-colourable maps can be abstracted as the following language:
3C ={G : G = (V, E) is an undirected loop-free graph and there is a function f : V → {0, 1, 2}
suchthat(∀v1,v2 ∈V)[(v1,v2)∈E⇒f(v1)̸=f(v2)].} Prove that 3C is NP-complete.
Q5. A graph isomorphism between two (undirected) graphs G1 = (V1, E1) and G2 = (V2, E2) is a bijective function f : V1 → V2 such that for all vertices u, v ∈ V1,
(u,v) ∈ E1 ⇐⇒ (f(u),f(v)) ∈ E2
If such an isomorphism exists, then we say that G1 and G2 are isomorphic. Intuitively, two
graphs are isomorphic if they “look the same” after moving around the vertices. We will define the Graph Isomorphism problem as
Iso = {(G,H) : G and H are isomorphic (undirected) graphs } Prove that Iso is NP. Is Iso NP-complete?
Computer Science Tutoring
CSC363 UTM Winter 2024 Assignment 3 Due Wednesday March 27
Q6. Define the Subgraph Isomorphism problem as
SubIso = {(G, H) : G and H are (undirected) graphs, and
H is isomorphic to some subgraph of G} Prove that SubIso is NP-complete.
Q7. (Bonus) On the topic of graph isomorphsim, consider the following special case of the graph isomorphism problem:
TIsor = {(T1,T2): T1 and T2 are ismoprhic trees of height at most r}.
We say that a tree graph has height at most r if there is no path (branch) in the tree that
contains more than r edges. Assume that our trees can be infinite.
(a) Prove that TIso1 is a Π02 problem. (b) Prove that TIso2 is a Π04 problem.
(c) Can you think of an oracle capable of deciding, for any two given trees of height 2, whether they are isomorphic or not?
Code Help