Question

In the HITTING SET problem, we are given a family of sets $\left\{S_1,S_{2}K,S_n\right\}$and budget , and we wish to find a set H of size $\le$b which intersects every ${\mathit{S}}_{\mathbf{i}}$, if such an exists. In other words, we want $\mathit{H}\mathbf{\cap }{\mathit{S}}_{\mathbf{i}}\mathbf{\ne }\mathit{\varphi }$for all i.Show that HITTING SET is NP-complete.

Short answer

As Hitting Set trouble is both in NP and NP-difficult, for this reason, it's far NP-whole.

Step-by-step solution

Introduction

If any problem is NP entire, then it is in each NP hard and NP. Hence, to prove that HITTING Set trouble is NP-complete, show this is NP and NP-complete as good evidence that HITTING hassle is NP-difficult: enter: a hard and fast of elements, series of subsets of , and a fantastic integer okay and a finite set as a certificate.

A hard and fast subset is HITTING Set for the ‘s if it incorporates at least one detail of each , that is, if is a subset of , for every . The input is in language HITTING-SET if there exists a hitting set for ’s size okay.

First, show that HITTING-SET is in NP. The entrance is in HITTING-SET if and best if a hitting set exists, so a certificate may be defined to genuinely be a hitting set, a list of ok elements of .

Accept the certificate if it has length ok and consists of a minimum of one element of each . To check this we take each of the units and check every element to see whether it's far within the listing (until it haselement or runs out of elements).

It takes time, and considering the fact that is approximately equal as , we've got , that is polynomial.

For that reason, HITTING-SET trouble is in NP.

Proving HITTING SET is NP-Complete Problem

HITTING SET problem in NP-hard, if the NP-entire trouble Vertex cowl, may be reduced to Hitting Set.

Supplied an undirected graph of nodes and edges and a parameter okay, outline to be the set of nodes in , and to be the set of endpoints of the brink , and let the parameter okay as provided above.

Then, has a vertex cowl of size if and only if has a hitting set of length okay for the ’s, that is due to the fact a set of nodes in is a vertex cover if and handiest if it hits every of the rims.

This reduction is computable in polynomial time as it ought to simply listing the edges of in a specific format and accordingly want only O (m+n) time.

Considering the fact that reduction is feasible here, as a result Hitting hassle is in NP-hard.

As Hitting Set trouble is both in NP and NP-difficult, for this reason, it's far NP-whole.

Introduction

If any problem is NP entire, then it is in each NP hard and NP. Hence, to prove that HITTING Set trouble is NP-complete, show this is NP and NP-complete as good evidence that HITTING hassle is NP-difficult: enter: a hard and fast of elements, series of subsets of , and a fantastic integer okay and a finite set as a certificate.

A hard and fast subset is HITTING Set for the ‘s if it incorporates at least one detail of each , that is, if is a subset of , for every . The input is in language HITTING-SET if there exists a hitting set for ’s size okay.

First, show that HITTING-SET is in NP. The entrance is in HITTING-SET if and best if a hitting set exists, so a certificate may be defined to genuinely be a hitting set, a list of ok elements of .

Accept the certificate if it has length ok and consists of a minimum of one element of each . To check this we take each of the units and check every element to see whether it's far within the listing (until it haselement or runs out of elements).

It takes time, and considering the fact that is approximately equal as , we've got , that is polynomial.

For that reason, HITTING-SET trouble is in NP.

Proving HITTING SET is NP-Complete Problem

HITTING SET problem in NP-hard, if the NP-entire trouble Vertex cowl, may be reduced to Hitting Set.

Supplied an undirected graph of nodes and edges and a parameter okay, outline to be the set of nodes in , and to be the set of endpoints of the brink , and let the parameter okay as provided above.

Then, has a vertex cowl of size if and only if has a hitting set of length okay for the ’s, that is due to the fact a set of nodes in is a vertex cover if and handiest if it hits every of the rims.

This reduction is computable in polynomial time as it ought to simply listing the edges of in a specific format and accordingly want only O (m+n) time.

Considering the fact that reduction is feasible here, as a result Hitting hassle is in NP-hard.

As Hitting Set trouble is both in NP and NP-difficult, for this reason, it's far NP-whole.