2023/04/28 by Mühlenthaler, Moritz, Peyrille, Benjamin, Szigeti, Zoltán
#05C40 (Primary) 05C65 #05C85 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2304.14868
The orientation theorem of Nash-Williams states that an undirected graph admits a k-arc-connected orientation if and only if it is 2k-edge-connected. Recently, Ito et al. showed that any orientation of an undirected 2k-edge-connected graph can be transformed into a k-arc-connected orientation by reorienting one arc at a time without decreasing the arc-connectivity at any step, thus providing an algorithmic proof of Nash-Williams' theorem. We generalize their result to hypergraphs and therefore provide an algorithmic proof of the characterization of hypergraphs with a k-hyperarc-connected orientation originally given by Frank et al. We prove that any orientation of an undirected (k,k)-partition-connected hypergraph can be transformed into a k-hyperarc-connected orientation by reorienting one hyperarc at a time without decreasing the hyperarc-connectivity in any step. Furthermore, we provide a simple combinatorial algorithm for computing such a transformation in polynomial time.