Can the set v of vertices be partitioned into exactly k


Problem Partition-into-Hamiltonian-Subgraphs (PiHS):

Input:

A graph G= (V; E) and a positive integer k<=|V|

Question:

Can the set V of vertices be partitioned into exactly k disjoint sets V1; V2; V3.... Vk such that, for 1<=i<=k, the subgraph induced by subset Vi contains a Hamiltonian cycle?

(a) Give a new yes-instance of Problem PiHS.

(b) Give a new no-instance of Problem PiHS.

(c) Prove that Problem PiHS is in the class NP

Request for Solution File

Ask an Expert for Answer!!
Computer Engineering: Can the set v of vertices be partitioned into exactly k
Reference No:- TGS02898440

Expected delivery within 24 Hours