TR-2008-02

A new approach to splitting-off

Attila Bernáth, Tamás Király

Published in:
Combinatorica 32 (2012), 373-401.



Abstract

A new approach to undirected splitting-off is presented in this paper. We study the behaviour of splitting-off algorithms when applied to the problem of covering a symmetric skew-supermodular set function by a graph. This hard problem is a natural generalization of many solved connectivity augmentation problems, such as local edge-connectivity augmentation of graphs, global arc-connectivity augmentation of mixed graphs with undirected edges, or the node-to-area connectivity augmentation problem in graphs. Using a simple lemma we characterize the situation when a splitting-off algorithm can be stuck. This characterization enables us to give very simple proofs for the classical results mentioned above. Finally we apply our observations in generalizations of the above problems: we consider three connectivity augmentation problems in hypergraphs with hyperedges of minimum total size without increasing the rank. The first is the local edge-connectivity augmentation of undirected hypergraphs. The second is global arc-connectivity augmentation of mixed hypergraphs with undirected hyperedges. The third is a hypergraphic generalization of the node-to-area connectivity augmentation problem. We show that a greedy approach works in (almost) all of these cases.


Older versions:

Bibtex entry:

@techreport{egres-08-02,
AUTHOR = {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s},
TITLE = {A new approach to splitting-off},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-02}
}


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