Well-balanced orientations of hypergraphs

When can we characterize hypergraphs that have an orientation satisfying a prescribed symmetric local edge-connectivity requirement? Special case: can we characterize hypergraphs that have an orientation which is k-edge-connected within a specified subset of nodes?

Hörsch and Szigeti showed that deciding the existence of an orientation satisfying local edge-connectivity requirements is NP-complete in the following two cases (here orientation means choosing a head node from each hyperedge):

• Given a node set S, find an orientation where any two vertices in S are mutually reachable from each other
• Given a node r and a node set S, find an orientation where every node of S is reachable from r.

For the second problem, they also give a polynomial-time algorithm when the size of S is constant. However, the first problem remains open in the case of constant-sized S.

Remarks

Frank, Király and Király proved an extension of Nash-Williams' weak orientation theorem by characterizing hypergraphs which have a k-edge-connected orientation. In this result "orienting a hypergraph" means picking a head node from each hyperedge.

For the same definition of hypergraph orientation, Király and Lau proved that if a hypergraph H is 2k-edge-connected within a subset T of nodes, then for any [math]r \in T[/math] it has an orientation where from any node of T there are k edge-disjoint paths to r.

To extend the strong orientation theorem of Nash-Williams to hypergraphs, one may need a different definition of hypergraph orientation. This may be related to the open problem on Highly element-connected orientation of graphs.