Splitting off edges between two subsets preserving the edge-connectivity of the graph. (Q1422410)

Splitting off a pair of edges \(su\), \(sv\) in a graph means replacing these two edges by a new edge \(uv\). Let \(G=(V+s,E)\) be a graph which is \(k\)-edge connected in \(V\) (i.e., there are at least \(k\) edge-disjoint paths between every pair of vertices of \(V\)) and suppose that the degree of \(s\) is even. \textit{L. Lovász} [Combinatorial problems and exercises (North-Holland, Amsterdam) (1993; Zbl 0785.05001)] proved that if \(k\geq 2\) then the edges incident with \(s\) can be split off in pairs preserving the \(k\)-edge connectivity in \(V\). In the paper under review, the authors study the following \((R,Q)\)-split completion problem: given a graph \(G=(V+s,E)\) which is \(k\)-edge connected in \(V\), disjoint subsets \(R\), \(Q\) of \(V\) and an integer \(k\geq2\), find a minimum cardinality set \(F\) of new edges incident with \(s\) such that in the new graph \(G+F\), all edges incident with \(s\) can be split off preserving the \(k\)-edge connectivity in \(V\) where every edge from \(s\) to \(R\) in \(G\) is split off with an edge from \(s\) to \(Q\). First, the problem of finding the longest possible sequence of ``admissible \((R,Q)\)-splits'' is solved. The length of such a sequence is characterized by certain ``obstacles'', i.e., substructures of \(G\) which preclude the existence of long admissible \((R,Q)\)-splitting sequences. An algorithm to find a longest sequence is given. Then this algorithm is used iteratively to solve the \((R,Q)\)-split completion problem when \(k\) is even. For odd \(k\), an almost optimal (at most two edges more than the optimum) solution is found.