2
$\begingroup$

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: undirected graph n0-n1-n2-n4-n3-n1

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: records overlaid

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

If I understand your problem accurately, it is NP-hard. As such, there is no efficient solution.

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:

gadget for reduction

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.

Finally, draw a query template that requires there to be a line between each of the two ovals of each gadget; and a line between the left oval of each gadget and the corresponding three ovals for the three variables occurring in the clause.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.