THE ARBORESCENCE-REALIZATION PROBLEM

A {0, 1}-matrix M is arborescence graphic if there exists an arboresce nce T such that the arcs of T are indexed on the rows of M and the col umns of M are the incidence vectors of the are sets of dipaths of T. I f such a T exists, then T is an arborescence realization for M. This p aper presents an almost-linear-time algorithm to determine whether a g iven {0, 1}-matrix is arborescence graphic and, if so, to construct an arborescence realization. The algorithm is then applied to recognize a subclass of the extended-Horn satisfiability problems introduced by Chandru and Hooker (1991).