  In some applications of matching, the structural or hierarchical properties
of the two graphs being aligned must be maintained. The hierarchical properties
are induced by the direction of the edges in the two directed graphs. These
structural relationships defined by the hierarchy in the graphs act as a
constraint on the alignment. In this paper, we formalize the above problem as
the weighted alignment between two directed acyclic graphs. We prove that this
problem is NP-complete, show several upper bounds for approximating the
solution, and finally introduce polynomial time algorithms for sub-classes of
directed acyclic graphs.
