Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

A tight lower bound for planar steiner orientation

Tools
- Tools
+ Tools

Chitnis, Rajesh, Feldmann, Andreas Emil and Suchý, Ondřej (2019) A tight lower bound for planar steiner orientation. Algorithmica, 81 . pp. 3200-3216. doi:10.1007/s00453-019-00580-x ISSN 0178-4617.

[img]
Preview
PDF
WRAP-tight-lower-bound-planar-Steiner-Chitnis-2019.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (692Kb) | Preview
[img] PDF
WRAP-steiner-orientation.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (326Kb)
Official URL: https://doi.org/10.1007/s00453-019-00580-x

Request Changes to record.

Abstract

In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs T. The question is whether we can orient the undirected edges in a way such that there is a directed s⇝t path for each terminal pair (s,t)∈T. Arkin and Hassin [DAM’02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when k=2. From the viewpoint of exact algorithms, Cygan et al. [ESA’12, SIDMA’13] designed an XP algorithm running in nO(k) time for all k≥1. Pilipczuk and Wahlström [SODA’16, TOCT’18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS’01] the Steiner Orientation problem does not admit an f(k)⋅no(k/logk) algorithm for any computable function f. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan et al. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in f(k)⋅no(k) time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC’16] and Manurangsi and Raghavendra [ICALP’17], we are able to show that there is no constant ϑ>0 such that Planar Steiner Orientation admits an (1920+ϑ)-approximation in FPT time, i.e., no f(k)⋅no(k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k⋅(1920+ϑ) pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Algorithms
Journal or Publication Title: Algorithmica
Publisher: Springer Verlag
ISSN: 0178-4617
Official Date: 1 August 2019
Dates:
DateEvent
1 August 2019Published
4 May 2019Available
3 April 2019Accepted
Volume: 81
Page Range: pp. 3200-3216
DOI: 10.1007/s00453-019-00580-x
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access (Creative Commons)
Date of first compliant deposit: 22 May 2019
Date of first compliant Open Access: 22 May 2019
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
ERC-2014-CoG 647557European Research Councilhttp://viaf.org/viaf/130022607
#897/13Israel Science Foundationhttp://dx.doi.org/10.13039/501100003977
P202/12/G061Grantová Agentura České Republikyhttp://dx.doi.org/10.13039/501100001824
UNSPECIFIEDUniverzita Karlova v Prazehttp://dx.doi.org/10.13039/100007397
17-20065S Grantová Agentura České Republikyhttp://dx.doi.org/10.13039/501100001824

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us