CODEWITHSUNDEEP
algorithmgraph-algorithmnpnp-completenp-hard
CoderAmateur
CoderAmateur

Reputation: 45

Is it NP complete?

A decision problem: For a given graph G and numbers 'a','b' it is required to be answered whether there is a set of 'a' vertices which have a cumulative neighborhood of size at least 'b'. How do we show that this problem is NPC?

Upvotes: 2

Views: 133

Answers (1)

mcdowella
mcdowella

Reputation: 19601

I think that if you could solve this in polynomial time you could solve https://en.wikipedia.org/wiki/Maximum_cut in polynomial time. According to the article the decision problem in Max-Cut is "Given a graph G and an integer k, determine whether there is a cut of size at least k in G".

Given something that solves your a/b version of the problem I would solve the Max-Cut version by setting b=k and trying a=1,2,3..size of graph, which would still have cost polynomial in the input size. (or possibly b=k+a depending on the details of what you mean by neighborhood size).

(So yes, I think your problem is NP-complete).

Upvotes: 1

Related Questions