Simplicity-Perserving Edge Splitting-off

Edge splitting-off is a popular technique to solve problems involving connectivity requirements. Splitting-off an edge pair (xu, xv) means removing edges xu, xv and adding a new edge uv. Applications of this technique include degree bounded network design problems and graph augmentation problems. For these problems, it is natural to take simplicity into consideration. This motivates the study of edge splitting-off with simplicity constraints. In this talk, we will discuss simplicity-preserving edge splitting-off, that is, the addition of new edge uv will not create new parallel edges. We will first introduce the sufficient conditions for the existences of such operation. And then see how to apply this technique in graph connectivity problems.