Existence of Graph Orientation

by Julien BENSMAIL, Romaric DUVIGNAU and Sergey KIRGIZOV

Definitions

Strong diameter is the greatest distance between any pair of vertices.

Weak diameter is the greatest weak distance between any pair of vertices.

Weak distance (one-way distance between u and v) equals to the length of the shortest directed path between u and v regardless of their order, i.e. weak distance = min ( |dipath(u,v)| , |dipath(v,u)| )

Note	In the case of directed graph, by distance we mean directed distance.

Formal Questions and Answers

Orientation with Weak Diameter k - k-OWD

Instance: A graph G.
Question: Does G admit a k-weak orientation?
Answer: This problem is very simple when k = 1, and NP-complete for any k ≥ 2 [BDK]

Orientation with Weak Diameter - OWD

Instance: A graph G.
Question: Does there exist an integer k such that G admits a k-weak orientation?
Answer: This problem is simple, i.e. P-complete. [SBD]

Orientation with Strong Diameter k - k-OSD

Instance: A graph G.
Question: Does G admit a k-strong orientation?
Partial Answer: The 1-OSD orientation is impossible. The 2-OSD problem is NP-complete. [CT]
Open problem: How difficult is this problem for k > 2?

Orientation with Strong Diameter - OSD

Instance: A graph G.
Question: Does there exist an integer k such that G admits a k-strong orientation?
Answer: This problem is very simple, i.e. can be solved in linear time.

Solution

By the Robbins' theorem [R] we have: graph has a bridge ⇔ it cannot be strongly orientable. So…
1) apply Tarjan’s algorithm to find all bridges;
2) if there are no bridges, find a good orientation using a simple algorithm from [R2].

References:

[CT] V. Chvátal and C. Thomassen, Distances in orientations of graphs. J. Combinatorial Theory Ser. B 24 (1978), no. 1, 61—75. 2

[R] H. E. Robbins, A theorem on graphs, with an application to a problem in traffic control. Amer. Math. Monthly 46 (1939), 281—283.

[BDK] J. Bensmail, R. Duvignau, S. Kirgizov, Complexity of a weak orientation of a graphThe complexity of deciding whether a graph admits an orientation with fixed weak diameter. 2013+
The paper: http://hal.archives-ouvertes.fr/hal-00824250,
and slides: http://www.labri.fr/perso/jbensmai/datas/talks/gt-14-06-13.pdf

[SBD] S. Kirgizov, J. Bensmail, R. Duvignau, Complexity of a “weak” orientation of a graph. 2013 (unpublished)
The paper: complexity-of-weak-oreintation.pdf

[Tarjan’s algorithm] http://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-finding_algorithm

[R2] http://en.wikipedia.org/wiki/Robbins%27_theorem#Algorithms_and_complexity