Orientations
Contents
Problems in this category
- Acyclic orientation with connectivity prescriptions
- Acyclic orientation with parity constraints
- Characterization of graphs having a k-connected orientation
- Constructive characterization of dumpy graphs
- Deciding the validity of the score sequence of a soccer tournament
- Decomposition into two trees with orientation constraints
- Head-disjoint strongly connected orientations
- Highly element-connected orientation
- Maximum size of a source-sink reorientable set
- Orientation conjecture of Nash-Williams
- Orientation of nonideal clutters
- Orientation with shortest round trip
- Parity constrained strongly connected orientations
- Smooth well-balanced orientations with prescribed in-degrees
- Well-balanced orientations of hypergraphs
Introduction
An orientation of an undirected (or mixed) graph is obtained by assigning a direction to each (undirected) edge. The definition for orientation of hypergraphs may depend on which possible definition of directed hypergraph it refers to. We will usually use the definition where every hyperarc has one designated head-node in a directed hypergraph, and therefore an orientation of a hypergraph means the designation of a head node in each hyperedge.
The constraints that we consider when orienting a graph or hypergraph are usually related to connectivity, e.g. edge-connectivity, node-connectivity or element-connectivity. In some problems the requirements concern the indegrees and/or outdegrees of the nodes.
Edge-connectivity requirements
Nash-Williams' strong orientation theorem (1960)[1] states that every undirected graph admits a well-balanced orientation. This theorem and its proof technique is unique in the area, and only a few related results have been obtained since then. Some results show[2] that if we require a little more, e.g. degree-bounds at nodes, or we want to find a well-balanced orientation of minimum cost, then we get NP-complete problems. Not much is known about hypergraphic generalizations of Nash-Williams' theorem either, see Well-balanced orientations of hypergraphs.
On the other hand, orientations of graphs or hypergraphs with global arc-connectivity requirements are much better understood. This is due to the connection with polymatroids. We can decide when a graph has a (k,l)-arc-connected orientation with degree-bounds at the nodes, or we can find a minimum-cost (k,l)-arc-connected orientation of a graph in polynomial time, too. See [3] for a survey. For results about (k,l)-arc-connected orientation of hypergraphs, see [4].
We get interesing problems by combining edge-connectivity requirements with parity conditions. While the problem is solved for rooted edge-connectivity requirements [5][6], it is an intriguing open problem for global arc-connectivity requirements: see the problem of parity constrained strongly connected orientations.
Node- or element-connectivity requirements
Much less is known about orientations with node- or element-connectivity requirements. It is not even clear how to decide whether a given graph admits a k-connected orientation. Orientations with element-connectivity requirements are not well understood, either.
Requirements on the node-degrees
There is a well-known characterization for undirected graphs having an orientation with prescribed indegrees at its nodes. However, if edges are allowed to remain undirected and we prescribe both the indegree and the outdegree of each node (and thus the undirected degree, too) then we get an NP-complete problem as was shown by Pálvölgyi [7]. This is related to the open problem about deciding the validity of the score sequence of a soccer tournament, which corresponds to the special case when the original graph is complete.
References
- ↑ C. St. J. A. Nash-Williams, On orientations, connectivity and odd vertex pairings in finite graphs, Canad. J. Math. 12 (1960) 555-567, DOI link
- ↑ A. Bernáth, Hardness results for well-balanced orientations, EGRES Technical Report no. 2006-05.
- ↑ A. Frank Orientations of Graphs and Submodular Flows, Congressus Numerantium 113 (1996) (A.J.W. Hilton, ed.) 111-142, author link
- ↑ A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Applied Mathematics. 131 (2003) 385--400. DOI link. EGRES Technical Report no. 2001-06
- ↑ A. Frank, T. Jordán, Z. Szigeti, An orientation theorem with parity conditions, Discrete Applied Mathematics 115 (2001) 37--45. DOI link
- ↑ T. Király, J. Szabó, A note on parity constrained orientations, accepted to Combinatorica, EGRES Technical Report no. 2003-11
- ↑ D. Pálvölgyi: Deciding Soccer Scores and Partial Orientations of Graphs, in: Acta Universitatis Sapientiae, Mathematica, 1, 1 (2009) 35--42. EGRES Quick Proofs QP-2006-06.
