RUTCOR Colloquia - March 22, 2007
Speaker: Kazuhisa Makino
Affiliation: Department of Mathematical Informatics, University of Tokyo, Tokyo, Japan
Title: Minimum Transversals in Posi-modular Systems
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Given a system (V,f,d) on a finite set V consisting of two set
functions f and d, we consider the problem of finding a set
R\subseteq V 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 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, 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)\mid v\in X \} for a function
p:V \to R_+ or d(X)=\max\{r(v,w)\mid v\in X, w\in V-X\}
for a function r:V^2\to 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\equiv 0.
This is a joint work with Mariko Sakashita, Hiroshi Nagamochi,
and Satoru Fujishige.
Back to Seminars Page.
Back to RUTCOR homepage.
| 
