Checking the admissibility of odd-vertex pairings is hard. (English) Zbl 07533120
Summary: 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.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C40 | Connectivity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Bernáth, A.; Iwata, S.; Király, T.; Király, Z.; Szigeti, Z., Recent results on well-balanced orientations, Discrete Optim., 5, 663-676 (2008) · Zbl 1161.05322 |
| [2] | Ford, L. R.; Fulkerson, D. R., Flows in Networks (1962), Princeton Univ. Press: Princeton Univ. Press PrincetonNJ · Zbl 0106.34802 |
| [3] | Frank, A., Connections in Combinatorial Optimization (2011), Oxford University Press · Zbl 1228.90001 |
| [4] | Garey, M.; Johnson, D., Computers and Intractability: a Guide to the Theory Of NP-Completeness (1979), W.H. Freeman · Zbl 0411.68039 |
| [5] | Király, Z.; Szigeti, Z., Simultaneous well-balanced orientations of graphs, J. Combin. Theory Ser. B, 96, 5, 684-692 (2006) · Zbl 1098.05048 |
| [6] | Menger, K., Zur allgemeinen Kurventheorie, Fund. Math., 10, 96-155 (1927) · JFM 53.0561.01 |
| [7] | Nash-Williams, C. St. J.A., On orientations, connectivity, and odd-vertex pairings in finite graphs, Canad. J. Math., 12, 555-567 (1960) · Zbl 0096.38002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
