Solve the following exercise by means of a reduction to
SAT:
- Given a network (an undirected graph) $G_1$ and a larger network
$G_2$, determine if we can find a bijective mapping from the nodes of
$G_1$ to a subset $S$ of the nodes of $G_2$ such that most of the edges
between nodes in $S$ are aligned to edges in $G_1$. In particular, no more
than $k$ edges can be not aligned. We say that an edge is aligned
if its adjacent nodes are image of two adjacent nodes in $G_1$.
The input of the exercise and the output with the solution (when the input is
solvable) are as follows: