Subscribe to the weekly news from TrueShelf

## Direct reduction from Graph Homomorphism to SAT

The decision problem \(GraphHomo\) is defined as follows:

\(GraphHomo = \{\langle G, H\rangle \mid \text{there is a graph homomorphism from G to H}\}\)

Give a direct reduction from \(GraphHomo\) to \(SAT\). Do not use \(\mathsf{NP}\)-completeness of \(SAT\).

**Source:**designed by Kaveh