2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vor Sep 30 '13 at 21:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Thomas Klimpel Sep 30 '13 at 22:20
  • $\begingroup$ @ThomasKlimpel: perhaps you are right, I thought of jigsaw puzzles having pieces with ambiguous mates ... $\endgroup$ – Vor Sep 30 '13 at 22:34
  • 1
    $\begingroup$ 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$. $\endgroup$ – David Richerby Sep 30 '13 at 23:38
  • $\begingroup$ 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. $\endgroup$ – drw Oct 1 '13 at 9:08
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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