Department of Applied Mathematics & Physics, Kyoto Univiversity
Technical Report #98014 (August, 1998)
Polyhedral Structure of Submodular and Posi-modular Systems
by Hiroshi Nagamochi and Toshihide Ibaraki
Let $V$ be a finite set, and $\Re$ be the set of reals.
A set function $f:2^V\mapsto \Re$ is called
intersecting submodular
if $f(X)+f(Y)\geq f(X\cap Y)+f(Y\cup X)$ for all intersecting $X,Y\subset V$,
and intersecting posi-modular
if $f(X)+f(Y)\geq f(X-Y)+f(Y-X)$ for all intersecting $X,Y\subset V$,
where $X$ and $Y$ intersecting if $X\cap Y\neq\emptyset$,
$X-Y\neq\emptyset$ and $Y-X\neq\emptyset$ hold.
We consider the polyhedron
$P=\{z\in \Re_-^V \mid z(X)\leq f(X),~ \forall X\in 2^V\}$
for a system $(V,f)$ with an intersecting submodular
and posi-modular set function $f:2^V\mapsto \Re$,
where $\Re_-^V$ denotes the set of $|V|$-dimensional nonpositive vectors
and $z(X)$ for a $z\in \Re_-^V$ and $X\subseteq V$ is defined by
$\sum_{i\in X}z(i)$.
We first prove that
there is a laminar (i.e., nonintersecting)
family ${\cal X}\subseteq 2^V-\{\emptyset,V\}$ such that
$P$ is characterized by
$\{z\in \Re_-^V \mid z(X)\leq f(X),~ \forall X\in {\cal X}\}$.
Based on this, we can solve in polynomial time
the edge-connectivity augmentation problem
with an additional constraint that
the number of vertices to which new edges are incident is minimized.