Prof. Avraham Melkman

We are given: a directed graph G = (V, E); for each vertex v ∈ V, a collection P (v) of sets of predecessors of v; and a target vertex t. Define a subset C of vertices to be complete if for each v ∈ C there is some set Q ∈ P (v) such that Q ⊆ C. We say that C is complete for t if in addition t ∈ C. The problem is to find a parsimonious (minimal with respect to set-inclusion) set that is complete for t. This paper presents efficient algorithms for solving the problem, for general graphs and for acyclic ones. In the special case where G is acyclic, and has bounded in-degree, the algorithm presented has time complexity O(|V|).