## Planar Steiner Orientation is NP-complete

2018
Kryven, Myroslav
Löffler, Andre
Preprint
Published
##### Abstract
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 and later W [1]-hard by Pilipczuk and Wahlström, parametrized by k. On the other hand, there is an XP algorithm by Cygan et al. and a polynomial time algorithm for graphs without directed edges by Hassin and Megiddo. Chitnis and Feldmann showed W [1]-hardness of the problem for graphs of genus 1. We consider a further restriction to planar graphs and show NP -completeness.
##### Subject (DDC)
004 Computer Science
##### Cite This
ISO 690BECK, Moritz, Johannes BLUM, Myroslav KRYVEN, Andre LÖFFLER, Johannes ZINK, 2018. Planar Steiner Orientation is NP-complete
BibTex
@unpublished{Beck2018-04-20T08:57:39ZPlana-44518,
year={2018},
title={Planar Steiner Orientation is NP-complete},
author={Beck, Moritz and Blum, Johannes and Kryven, Myroslav and Löffler, Andre and Zink, Johannes}
}

RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<dc:rights>terms-of-use</dc:rights>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:01:26Z</dcterms:available>
<dcterms:title>Planar Steiner Orientation is NP-complete</dcterms:title>
<dc:creator>Blum, Johannes</dc:creator>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44518"/>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Zink, Johannes</dc:contributor>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:01:26Z</dc:date>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44518/3/Beck_2-b4bo2o1xb2qr0.pdf"/>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44518/3/Beck_2-b4bo2o1xb2qr0.pdf"/>
<dc:creator>Zink, Johannes</dc:creator>
<dcterms:issued>2018-04-20T08:57:39Z</dcterms:issued>
<dc:creator>Löffler, Andre</dc:creator>
<dc:creator>Kryven, Myroslav</dc:creator>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:creator>Beck, Moritz</dc:creator>
<dc:language>eng</dc:language>
<dc:contributor>Löffler, Andre</dc:contributor>
<dcterms:abstract xml:lang="eng">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 and later W [1]-hard by Pilipczuk and Wahlström, parametrized by k. On the other hand, there is an XP algorithm by Cygan et al. and a polynomial time algorithm for graphs without directed edges by Hassin and Megiddo. Chitnis and Feldmann showed W [1]-hardness of the problem for graphs of genus 1. We consider a further restriction to planar graphs and show NP -completeness.</dcterms:abstract>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Blum, Johannes</dc:contributor>
<dc:contributor>Kryven, Myroslav</dc:contributor>
<dc:contributor>Beck, Moritz</dc:contributor>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
</rdf:Description>
</rdf:RDF>

Yes