Completing orientations of partially oriented graphs

DOI10.1002/JGT.22157MaRDI QIDQ4638628zbMATH OpenOpenAlexFDO

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

Publication date 27 April 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

friendly partial oriented graphin-tournamentlocal tournamentlocally transitive local tournamentNP-completenessorientation completion problempartially oriented graphpolynomial time algorithmproper circular arc graphproper interval graphrecognitionrepresentation extension

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Analysis of algorithms and problem complexity (68Q25)

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 (non-oriented) edges in P. Orien- tation 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 tournament, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in- tournaments, and oriented graphs which 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, which generalize a previous result.

Recommendations

• Full orientability of graphs
• Acyclic orientations of complete bipartite graphs
• On the semi-proper orientations of graphs
• Orientations of graphs
• Partial graph orientations and the Tutte polynomial
• On the orientation of graphs and hypergraphs
• A note on full orientability of a graph
• scientific article; zbMATH DE number 729744
• scientific article; zbMATH DE number 3957181
• The oriented graph complexes

Cited in

(17)

• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• Acyclic orientations of complete bipartite graphs
• Obstructions for acyclic local tournament orientation completions
• Enumerating \(k\)-arc-connected orientations
• Lexicographic orientation algorithms
• scientific article; zbMATH DE number 47434 (Why is no real title available?)
• Partial characterizations of 1-perfectly orientable graphs
• The complexity of 2-vertex-connected orientation in mixed graphs
• Coloring mixed and directional interval graphs
• Tournament completions of bipartite tournaments and their augmented directed cycles
• Forbidden tournaments and the orientation completion problem
• Minimal obstructions for partial representations of interval graphs
• Partial graph orientations and the Tutte polynomial
• Obstructions for local tournament orientation completions with cut-vertices
• Quasi-transitive mixed graphs and undirected squares of oriented graphs
• Edge-arc-disjoint paths in semicomplete mixed graphs
• On preserving full orientability of graphs

This page was built for publication: Completing orientations of partially oriented graphs

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