  Nash-Williams proved that every graph has a well-balanced orientation. A key
ingredient in his proof is admissible odd-vertex pairings. We show that for two
slightly different definitions of admissible odd-vertex pairings, deciding
whether a given odd-vertex pairing is admissible is co-NP-complete. This
resolves a question of Frank. We also show that deciding whether a given graph
has an orientation that satisfies arbitrary local arc-connectivity requirements
is NP-complete.
