Sorry for the vague title. I'm hoping someone can identify this problem by name and point me in the right direction to solving it (I think ILP could be used to solve it).
Given a set of DAGs $\{G_1, G_2, ...\}$ where $G_i=(V,E,labels(V))$ and $labels: V \rightarrow \{A, B, C, D\}$ (each vertex has a label – A, B, C, or D), I want to compute a new graph $H=(V',E',labels(V'))$ s.t. $\{G_1, G_2, ...\}$ are subgraphs of $H$.
In other words, I want to merge each $G_i$ into a single graph, such that there exists a subgraph isomorphism between $H$ and each $G_i$.
If they are DAGs, just sort them topologically. As you label the vertices with a (small) fixed set, you can sort so that labels appear in one particular order, and then the matching between graphs is more of less finding longest common subsequences of the labels Might even try different label orders and see which one comes out best.