# a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph

Suppose I have a set of small subgraphs $A=\{G_i\}$ of an original directed acyclic graph $G$, typically $|G_i| \ll |G|$, which together span the original graph

$$G= \bigcup_i G_i$$ My question is if I take a arbitrary subset of these graphs $A′ \subset A$, and a single subgraph from this graph, $a \in A′$, is there a simple way (or known algorithm) of reassembling the subgraph $G′ \subset G$ given by that portion of the union of $A′$ connected to $a$?

In words, this is rather like a jigsaw problem where $A$ is the total collection of pieces that originally came in the box, $A′$ is the subset left after half of them got lost and $a \in A′$ the random selected piece you put down the start the puzzle off. The question is then what is the largest connected graph (connected subset of pieces $x \in A'$) that you can lay down all on the board.

The actual application arises where each subgraph $G_i$ of A represents a rule and (e.g. $x \wedge y \Rightarrow z$) and the objective is to find the largest rule implied transitively from an initial seed rule $a \in A′$ and the remaining rules contained in thinned out subset $A′ \subset A$.

I suspect I maybe able to do something by brute force here but would be most interested in knowing if there is any area or known application of this problem elsewhere. I think similar things are possible in declarative language such as Prolog but I suspect that Prolog can actually do any more. Any good up-to-date reference on declarative programming languages would also be very useful.

I originally posted a version of this question on the Computational Science site but was advised that this forum could be better.

• At first glance, the complexity should not change if you pick $A' = A$, $G' = G$. Furthermore the problem seems NP-complete (you can use a reduction from one of the known tiling NP-complete problems, for example, the strong NPC problem of tiling a rectangle with $1 \times x_i$ pieces; see "Jigsaw Puzzles, Edge Matching, and Polyomino) Packing: Connections and Complexity" by Erik D. Demaine and Martin L. Demaine. – Vor Sep 30 '13 at 21:06
• @Vor Even so drw talks of a jigsaw problem, his problem seems more or less related to HORNSAT, which is P-complete. I'm not sure whether his problem allows to model HORNSAT directly (even so he obviously believes this), but it's quite possible that his problem is also P-complete. Even so the problem description could be clearer, none of the interpretations I see would lead to a NP-complete problem. – Thomas Klimpel Sep 30 '13 at 22:20
• @ThomasKlimpel: perhaps you are right, I thought of jigsaw puzzles having pieces with ambiguous mates ... – Vor Sep 30 '13 at 22:34
• If the vertices are distinguishable (i.e., if I can tell which vertices from $G$ are in each $A_i$), the problem seems very easy. If they're not, it seems to be ill-defined. In extremis, each $A_i$ is a single edge so, given $A'\subseteq A$, can't I build any graph with $|A'|$ edges by gluing them together however I please? If $G$ isn't part of the input, I can't even tell if the graph I'm building is a subgraph of $G$. – David Richerby Sep 30 '13 at 23:38
• Many thanks for these comments. Connected certainly is meant to directed and it might well be possible to do this is a straightforward way for small graphs. The references are very useful and I will follow them up to look for any further insights. Many thanks to every one who has contributed here. – drw Oct 1 '13 at 9:08

So we are probably interested in the subgraph reachable from a node in $a$. I looks like we can just work with the set of edges contained the graphs from $A'$. But then we end up with a problem which belongs to both 2-SAT and HORNSAT, and the unit-propagation algorithm for HORNSAT will solve it in linear time. As the problems also belongs to 2-SAT, we know that it is not P-complete.