Transversals of subtree hypergraphs and the source location problem in digraphs

A hypergraph H = ( V , E ) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T . Since the number of edges of a subtree hypergraph can be exponential in n = | V |, one can not always expect to be able to find a minimum size transversal in time polynomial in n . In this paper, we show that if it is possible to decide if a set of vertices W ⊆ V is a transversal in time S ( n ) (where n = | V |), then it is possible to find a minimum size transversal in O ( n 3 S ( n )). This result provides a polynomial algorithm for the Source Location Problem: a set of ( k , l )‐sources for a digraph D = ( V , A ) is a subset S of V such that for any v ∈ V there are k arc‐disjoint paths that each join a vertex of S to v and l arc‐disjoint paths that each join v to S . The Source Location Problem is to find a minimum size set of ( k , l )‐sources. We show that this is a case of finding a transversal of a subtree hypergraph, and that in this case S ( n ) is polynomial. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008