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.