A patang is a graph on an even number of vertices


A patang is a graph on an even number of vertices, say 2n, in which n of the vertices form a clique and the remaining n vertices are connected in a "tail" that consists of a path joined to one of the vertices of the clique. Given a graph and a goal g, the Patang problem asks for a subgraph which is a patang and which contains 2g nodes. Prove that Patang is NP-complete.

Request for Solution File

Ask an Expert for Answer!!
Basic Computer Science: A patang is a graph on an even number of vertices
Reference No:- TGS093121

Expected delivery within 24 Hours