THE COMPLEXITY OF APPROXIMATING THE ORIENTED DIAMETER OF CHORDAL GRAPHS

Abstract

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; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.

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; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.

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; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.

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; we prove that the corresponding decision problem remains NP-complete even when restricted to a small subclass of chordal graphs called split graphs; we show that, unless P = NP, there is neither a polynomial-time absolute approximation algorithm nor an ?-approximation (for every ?<3 2) algorithm computing oriented diameter of a chordal graph.