Campus Event Calendar

Event Entry

What and Who

Minimum Transversals in Posi-modular Systems

Kaz Makino
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS  
AG Audience

Date, Time and Location

Friday, 8 September 2006
-- Not specified --
E1 4


Given a system (V,f,d) on a finite set V consisting of two set functions f and d on 2^V, we consider the problem of finding a set R of minimum cardinality such that f(X) >= d(X) for all X subseteq 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 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.


Khaled Elbassioni
--email hidden
passcode not visible
logged in users only

Khaled Elbassioni, 09/04/2006 17:45
Khaled Elbassioni, 09/04/2006 17:44 -- Created document.