TR-2011-10

Special skew-supermodular functions and a generalization of Mader's splitting-off theorem

Attila Bernáth, Tamás Király, László Végh



Abstract

In this note we give a slight extension of Mader's undirected splitting-off theorem with a simple proof, and we investigate some related questions. Frank used Mader's theorem for solving the local edge-connectivity augmentation problem which is the following: given a graph $G_0=(V,E_0)$ and a symmetric function $r:V \times V \to \Zset_+$, find a graph $G=(V,E)$ with a minimum number of edges such that $\lambda_{G_0+G}(u,v) \geq r(u,v)$ for every pair of nodes $u,v$. In the solution Frank introduces the set function $R_r(X)=\max\{r(x,y):x\in X,y\in V-X\}$ for any $X\subseteq V$ and he reproves Mader's theorem using the following three properties of this function: (i) symmetry, (ii) skew-supermodularity and (iii) $R_r(X\cup Y)\le \max\{R_r(X),R_r(Y)\}$ for every pair of sets $X,Y\subseteq V$. We give a proof where (iii) is only required for disjoint pairs of sets $X,Y\subseteq V$, and we show examples of functions satisfying Properties (i)-(ii) and this weaker form of (iii).


Bibtex entry:

@techreport{egres-11-10,
AUTHOR = {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s and V{\'e}gh, L{\'a}szl{\'o}},
TITLE = {Special skew-supermodular functions and a generalization of Mader's splitting-off theorem},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {TR-2011-10}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!