Checking the admissibility of odd-vertex pairings is hard
From MaRDI portal
Publication:6361700
DOI10.1016/J.DAM.2022.04.004arXiv2103.00306MaRDI QIDQ6361700
Publication date: 27 February 2021
Abstract: 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.
This page was built for publication: Checking the admissibility of odd-vertex pairings is hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6361700)
