A unifying approach to splitting-off (Q2448935): Difference between revisions

A symmetric skrew-supermodular set function \(p\) is covered by a hypergraph \(H\) if each subset \(X\) of the vertex set \(V\) is introduced by at least \(p(X)\) hyperedges. In case of a degree specification \(m(v)\) for \(v\) from \(V\), the question is whether a hypergraph \(G\) covering \(p\) exists such that the degree of each vertex \(v\) in \(G\) equals \(m(v)\). If there is a solution then there is also a solution to the minimum version in which the sum of the sizes of the hyperedges is minimized because of \(p\) being skrew-supermodular. The problem with specified degrees generalizes many connectivity augmentation problems. The minimum version and therefore the degree-specified version are \(NP\)-complete but special cases are polynomially solvable. The idea bases on a technique called splitting-off: first find a set of graph edges covering \(p\) of minimum cardinality and incident to a new vertex \(s\), then split off pairs of to \(s\) incident edges.