Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph G, a distance bound L, and p pairs of vertices (s1, t1), . . . , (sp, tp), the objective is to find a minimum-cost subgraph G′ such that si and ti have distance at most L in G′ (for every i ∈ [p]). Our main result is on the fixed-parameter tractability of this problem with parameter p. We exactly characterize the demand structures that make the problem “easy”, and give FPT algorithms for those cases. In all other cases, we show that the problem is W[1]-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W[1]-hard even to approximate.

• Publication year

  2018

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  2018-02-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.ICALP.2018.104arXiv 1802.10566
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems

  2017cited by this paper
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

  2017cited by this paper
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms

  2017influential reference
• Timely, Reliable, and Cost-Effective Internet Transport Service Using Dissemination Graphs

  2017influential reference
• From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

  2017cited by this paper
• Approximating Spanners and Directed Steiner Forest

  2016cited by this paper
• On the Shallow-Light Steiner Tree Problem

  2014cited by this paper
• Steiner Tree Approximation via Iterative Randomized Rounding

  2013cited by this paper
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

  2009cited by this paper
• Set connectivity problems in undirected graphs and the directed Steiner network problem

  2008cited by this paper
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

  2006cited by this paper
• On directed Steiner trees

  2002cited by this paper
• A simple efficient approximation scheme for the restricted shortest path problem

  2001cited by this paper
• Improved Steiner tree approximation in graphs

  2000cited by this paper
• The Directed Steiner Network problem is tractable for a constant number of terminals

  1999cited by this paper
• Approximation algorithms for directed Steiner problems

  1999cited by this paper
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

  1998cited by this paper
• Improved approximations for shallow-light spanning trees

  1997cited by this paper
• Approximating shallow-light trees

  1997cited by this paper
• Better approximation bounds for the network and Euclidean Steiner tree problems

  1996cited by this paper
• Improved approximations for the Steiner tree problem

  1992cited by this paper
• Approximation Schemes for the Restricted Shortest Path Problem

  1992cited by this paper
• A general approximation technique for constrained forest problems

  1992cited by this paper
• When trees collide: an approximation algorithm for the generalized Steiner problem on networks

  1991cited by this paper
• A fast algorithm for Steiner trees

  1981cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• The steiner problem in graphs

  1971cited by this paper

• Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

  2018cites this paper