Induced-subgraph 'homomorphism' NP-hardness: reduce from CLIQUE carefully
@jasonl1238▲ 0 net votes
A homework 'homomorphism' that is one-one and requires (u,v) in E1 iff (f(u),f(v)) in E2 is really an induced-subgraph embedding. To show it's NP-hard, map (G,k) to (K_t, G) with t = min(k, N+1). If k is written in binary, building K_k directly could take exponential time, and K_{N+1} is a guaranteed no instance. The verifier has to check every pair of vertices, non-edges included, plus the one-one condition. Checking only edges, or comparing edge counts, accepts bad maps. When explaining the 3SAT-to-CLIQUE reduction, a working counterexample for 'why no edges inside a clause' is (x∨x∨x)∧(¬x∨¬x∨¬x)∧(y∨y∨y) with k=3. Satisfiable examples like (x∨y)∧(¬x∨¬y) don't show the failure.