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.
a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph
graph theory;graphs
One unclear point about the question is the meaning of connected. If we interpret it as weakly connected, then the orientation of the DAG is no longer important, and we could have worked with an undirected graphs in the first place. We should also not interpret it as strongly connected, since a DAG has no strongly connected subsets.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.