Problem is to decide whether g has a no 2-path set


The No 2-Path Problem is as follows. You are given a graph G = (V,E) and an integer k. For this problem, we will call a set I of V "No 2-Path Set" if, for any two nodes v, u in I, the edge (v, u) does not belong to E, and there is also no path of two edges from u to v, that is, there is no node w such that both (u,w) in E and (w, v) in E. The No 2-Path Problem is to decide whether G has a "No 2-Path Set" of size at least k. Prove that the No 2-Path Problem is NP-complete.

Request for Solution File

Ask an Expert for Answer!!
Data Structure & Algorithms: Problem is to decide whether g has a no 2-path set
Reference No:- TGS093119

Expected delivery within 24 Hours