The complexity of two graph orientation problems

DOI10.1016/J.DAM.2011.10.036MaRDI QIDQ412352zbMATH OpenOpenAlexFDO

Authors Nicole Eggemann, Steven D. Noble

Publication date 4 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2478

zbMATH Keywords

diametergraph minorsgraph orientationplanar graphapex graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38) Graph minors (05C83)

Abstract: We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-complete to decide whether a graph has an orientation such that the sum of all the shortest paths lengths is at most an integer specified in the input. The proof is a short reduction from a result of Chv'atal and Thomassen showing that it is NP-complete to decide whether a graph can be oriented so that its diameter is at most 2. In contrast, for each positive integer k, we describe a linear-time algorithm that decides for a planar graph G whether there is an orientation for which the diameter is at most k. We also extend this result from planar graphs to any minor-closed family not containing all apex graphs.

Recommendations

• The complexity of 2-vertex-connected orientation in mixed graphs
• Approximation algorithms and hardness results for shortest path based graph orientations
• The complexity of deciding whether a graph admits an orientation with fixed weak diameter
• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• NP-Completeness of st-Orientations for Plane Graphs
• On the orientation of graphs and hypergraphs
• Graph orientation and its total efficient domination
• NP-completeness of st-orientations for plane graphs
• The orientation number of two complete graphs with linkages
• Parameterized st-Orientations of Graphs: Algorithms and Experiments

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Bidimensional Parameters and Local Treewidth
• Complexity of approximating the oriented diameter of chordal graphs
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Digraphs
• Distances in orientations of graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Easy problems for tree-decomposable graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph minor theory
• Graph minors. III. Planar tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Linearity of grid minors in treewidth with applications through bidimensionality
• Minimizing the oriented diameter of a planar graph
• On orientations and shortest paths
• Optimal orientations of graphs and digraphs: A survey
• Quickly excluding a planar graph
• Separating systems and oriented graphs of diameter two
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. VIII: Orientations

Cited in

(17)

• Complexity dichotomy for oriented homomorphism of planar graphs with large girth
• Route-enabling graph orientation problems
• NP-completeness of st-orientations for plane graphs
• On the oriented diameter of planar triangulations
• Minimizing the oriented diameter of a planar graph
• Orientable burning number of graphs
• Bounds for the oriented diameter of planar triangulations
• Min-sum 2-paths problems
• Planar oriented graphs of diameter two
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Route-enabling graph orientation problems
• On orientations and shortest paths
• Min-sum 2-paths problems
• The complexity of the proper orientation number
• On the Query Complexity of Testing Orientations for Being Eulerian
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• The complexity of deciding whether a graph admits an orientation with fixed weak diameter

This page was built for publication: The complexity of two graph orientation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412352)