Subgraph of labeled DAG


Hello,

What is the computational complexity of

1) deciding whether a given labeled DAG H can be embedded as a subgraph
of another labeled DAG G (with the same set of labels).

2) finding such a concrete embedding when it exists.

Are these P or NP problems or even NP-complete ?

If the number of labels is 1 and the DAG G consists of the total order
on n Elements where n is the number of vertices of H then this amounts
to topological sorting which has very good behaviour in terms of
complexity (linear as far as I know)

If one generalizes this topological sorting to two dimensions, that is
a 2-labeled DAG with m*n Elements to be embedded into the DAG given as
the 2-labeled DAG of position relations (vertical/horizontal) of the
elements of an m*n matrix is there still an algorithm with polynomial
complexity ?

Is a general formula known for the generalization of the 2d problem of
the last paragraph do k dimensions and n1*n2*...*nk elements ?

I looked for several hours in the internet for information about these
problems but could not find anything appropriate enough. What would be a
good reading to get acquainted to this sort of problems (colored and
labeled trees and graphs, embedding problems of these) ?

Thanks in advance

Jürgen

-------------------------------------------------------------------------
Dipl.-Math. Jürgen Böhm e-mail: reverse: net dot gmx at jboehm
"At a time when so many scholars in the world are calculating, is it not
desirable that some, who can, dream ?" R. Thom

.