Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

We present a constrained version of the problem of enumerating all maximal directed acyclic subgraphs (DAG) of a graph G. In this version, we enumerate maximal DAGs whose sources and targets belong to a predefined subset of the nodes. We call such DAGs stories. We first show how to compute one story in polynomial-time, and then describe two different algorithms to tell all possible stories. (C) 2012 Elsevier B.V. All rights reserved.