Minimum Transversals in Posi-modular Systems

Given a system (

V

,

f

,

d

) on a finite set

V

consisting of two set functions

$f:2^V\rightarrow{\mathbb R}$

and

$d:2^V\rightarrow{\mathbb R}$

, we consider the problem of finding a set

R

 ⊆ 

V

of the minimum cardinality such that

f

(

X

)≥

d

(

X

) for all

X

 ⊆ 

V

 − 

R

, 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

∈

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

∈

X

} for a function

$p:V \rightarrow{\mathbb R}_+$

or

d

(

X

)=max{

r

(

v

,

w

) |

v

∈

X

,

w

∈

V

–

X

} for a function

$r:V^2\rightarrow{\mathbb R}_+$

. 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

.