Completing orientations of partially oriented graphs

Jørgen Bang-Jensen, Jing Huang, Xuding Zhu

Research output: Contribution to journalJournal articleResearchpeer-review

135 Downloads (Pure)

Abstract

We initiate a general study of what we call orientation completion problems. For a fixed class C of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in C by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k-arc-strong oriented graphs, k-strong oriented graphs, quasi-transitive-oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in-tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP-complete. We also show that some of the NP-complete problems become polynomial time solvable when the input-oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.

Original languageEnglish
JournalJournal of Graph Theory
Volume87
Issue number3
Pages (from-to)285-304
ISSN0364-9024
DOIs
Publication statusPublished - 2018

    Fingerprint

Keywords

  • NP-complete
  • friendly partial oriented graph
  • in-tournament
  • local tournament
  • locally transitive local tournament
  • orientation completion problem
  • partially oriented graph
  • polynomial time algorithm
  • proper circular arc graph
  • proper interval graph
  • recognition
  • representation extension

Cite this