2018/04/20 by Moritz Beck, Beck, Moritz, Johannes Blum +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1804.07496
openalex publication_date 2018/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed graph G (having directed and undirected edges) and a set T of k terminal pairs in G, is there an orientation of the undirected edges in G such that there is a directed path for every terminal pair in T ? This problem was shown to be NP -complete by Arkin and Hassin [1] and later W [1]-hard by Pilipczuk and Wahlström [7], parametrized by k. On the other hand, there is an XP algorithm by Cygan et al. [3] and a polynomial time algorithm for graphs without directed edges by Hassin and Megiddo [5]. Chitnis and Feldmann [2] showed W [1]-hardness of the problem for graphs of genus 1. We consider a further restriction to planar graphs and show NP -completeness.