NP-Hardness

Question 1

Hitting Set definition

Answer 1

Given a set S={a,b,c,d,ef,g,h,….} and subset C of S –> C={(a,b,c), (b,c,e),(f,d),(a)….}; find a set H={…} of S of size <= k such that H intersect C is non empty.
For example here H={a,b}

Question 2

To prove X is NP-hard

Answer 2

Don’t think how to change X to graph of vertex cover or independent set ; instead take an instance(نموذج) of vertex cover/independent set and transform it to an instance(نموذج) of X

Question 3

How to write the proof

Answer 3

Consider an instance (G,V,E,K) of vertex cover , the instance (S,C,K’) of hitting set is constructed as follows:
S

Question 4

Do not forget to say that this reduction take a polynomial time

Answer 4

True

Question 5

Clique

Answer 5

Complete subgraph

Question 6

Subgraph Isomorphism

Answer 6

Given 2 graphs G1 and G2; G1 is subgraph Ismorphic to G2 –> G2 contains a subgraph Isomorphic (same) to G1.

Question 7

Prove NP-Hard for subgraph isomorhism

Answer 7

Consider an instance (G,K) of clique , an instance (G1,G2) of subgraph isomorphism is constructed as follows:
G1

Question 8

Prove NP-Hardness for Independent set

Answer 8

Done by 3 SAT

Question 9

Prove NP- Hardness for vertex cover

Answer 9

Consider an instance (G,K) of independent set , and instance (G,K’) of vertex cover is constructed as follows:
K’

Question 10

Graph complement or graph inverse

Answer 10

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G

Question 11

Prove of NP-completeness

Answer 11

Consider an instance (G,K) of Independent Set, an instance (G’,K’) of clique is constructed as follows:
G’