Minimum Transversals in Posi-modular Systems

where the problem can be regarded as a natural generalization of the
source location problems and the external network problems
in (undirected) graphs and hypergraphs.
We give a structural characterization of minimal deficient
sets of (V,f,d) under certain conditions.
We show that all such sets form a tree hypergraph
if f is posi-modular and d is modulotone (i.e., each nonempty
subset X of V has an element v in X such that d(Y) >= d(X)
for all subsets Y of X that contain v), and that conversely
any tree hypergraph can be represented by minimal deficient sets
of (V,f,d) for a posi-modular function f and a modulotone function d.
By using this characterization, we present a polynomial-time algorithm
if, in addition, f is submodular and d is given by either
d(X)= max {p(v) | v in X } for a function p on V or
d(X)= max {r(v,w)| v in X, w in V-X} for a function r on V^2.
Our result provides first polynomial-time algorithms for the source
location problem in hypergraphs and the external network problems
in graphs and hypergraphs.
We also show that the problem is intractable, even if f is submodular and d=0.