# Find all combinations of adjacent records matching a graph template

I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from each oval such that the blue edges between the blocks look like the edges in the first figure below. Find all possible such combinations.

The background to this problem is we want to allow a user to define an arbitrary undirected graph to serve as a query template, for example:

For every node, the user can define criteria that must be satisfied, and we then query multiple different APIs to get matching records, with each record being associated with one edge of the query template, as illustrated in the figure below:

An example of a record would be AC, with A matching the criteria specified for n0 and with C matching the criteria for n1. The line between A and C indicates the two of them together form a record.

We want to find every combination (unordered set of records) where every record within each combination meets these two conditions:

1. one record per query template edge, e.g., AC for e0, CF for e1, etc
2. records that share a query template node (like n1) must also share a corresponding record node (like C)

For the figure above, we should get the combinations below:

{ AC, CF, FK, KI, IC }
{ AC, CF, FK, KI, ID }
{ AC, CH, HK, KI, IC }
{ AC, CH, HK, KI, ID }
{ BC, CF, FK, KI, IC }
{ BC, CF, FK, KI, ID }
{ BC, CH, HK, KI, IC }
{ BC, CH, HK, KI, ID }
{ BD, DH, HK, KI, IC }
{ BD, DH, HK, KI, ID }


How would I properly describe this problem in graph theory or combinatorics terminology? Is there an optimal solution to finding the combinations of records, considering that we're trying to avoid limitations on the query template and the number of records per query template edge could be in the hundreds of thousands?

I will show a reduction from 3SAT. In particular, suppose we have a 3SAT formula $$\varphi$$ with variables $$x_1,\dots,x_m$$ and $$m$$ clauses. For each $$i$$, introduce an oval with two nodes inside it, one for $$x_i$$ and one for $$\overline{x_i}$$. For each clause, introduce two ovals, with the following shape:
Ddraw a blue line between $$A$$ and the node for the first literal in the clause; a blue line between $$B$$ and the node for the second literal in the clause; and a blue line between the $$C$$ and the node for the third literal in the clause. That is the record graph.
Now, if I understand your matching rules correctly, there is a satisfying assignment to $$\varphi$$ iff the query template has a match in the record graph.