ALCOMFT-TR-02-17

Fedor V. Fomin, Mart\'\in Matamala and Ivan Rapaport
The complexity of approximating the oriented diameter of chordal graphs
Paderborn. Work package 4. May 2002.

Abstract: \beginabstract The oriented diameter of a (undirected) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We

• give a linear time algorithm such that, for a given chordal graph G, either concludes that there is no strongly connected orientation of G, or finds a strongly connected orientation of G with diameter at most twice the diameter of G plus one;
• prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs;
• show that unless P=NP, there is neither a polynomial-time absolute approximation algorithm nor an alpha-approximation (for every alpha<(3)/(2)) algorithm computing oriented diameter of a chordal graph.

Postscript file: ALCOMFT-TR-02-17.ps.gz (121 kb).