A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

DOI10.1007/978-3-319-13524-3_14zbMATH Open1364.68224arXiv1506.03760OpenAlexW196127575MaRDI QIDQ2946016FDOQ2946016

Authors: Rajesh Chitnis, H. Esfandiari, Rohit Khandekar, S. Seddighin, Mohammad T. Hajiaghayi, Guy Kortsarz 

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: Given an edge-weighted directed graph $G=(V,E)$ on $n$ vertices and a set $T=t_1,t_2,ldots,t_p$ of $p$ terminals, the objective of the scss ($p$-SCSS) problem is to find an edge set $HsubseteqE$ of minimum weight such that $G[H]$ contains an $t_{i}ightarrow{t}_j$ path for each $1leqieqjleqp$. In this paper, we investigate the computational complexity of a variant of $2$-SCSS where we have demands for the number of paths between each terminal pair. Formally, the sharinggeneral problem is defined as follows: given an edge-weighted directed graph $G=(V,E)$ with weight function $omega:Eightarrowmathbb{R}^{geq0}$, two terminal vertices $s,t$, and integers $k_1,k_2$ ; the objective is to find a set of $k_1$ paths $F_1,F_2,ldots,F_{k_1}$ from $sleadstot$ and $k_2$ paths $B_1,B_2,ldots,B_{k_2}$ from $tleadstos$ such that $su{m}_{einE}omega(e)cdotphi(e)$ is minimized, where $phi(e)=maxBig|iin[k_1]:ein{F}_i|,|jin[k_2]:ein{B}_j|Big$. For each $kgeq1$, we show the following: The sharing problem can be solved in $n^{O(k)}$ time. A matching lower bound for our algorithm: the sharing problem does not have an $f(k)cdot{n}^{o(k)}$ algorithm for any computable function $f$, unless the Exponential Time Hypothesis (ETH) fails. Our algorithm for sharing relies on a structural result regarding an optimal solution followed by using the idea of a "token game" similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the sharinggeneral problem if $min{k}_1,k_{2}geq2$. Therefore sharing is the most general problem one can attempt to solve with our techniques.

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

Recommendations

• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs
• Strong Formulations for 2-Node-Connected Steiner Network Problems
• Strong Steiner tree approximations in practice
• An approximation algorithm for the Steiner connectivity problem
• Tighter Bounds for Graph Steiner Tree Approximation
• On approximation algorithms for the terminal Steiner tree problem
• scientific article; zbMATH DE number 4049088

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Approximability of capacitated network design
• Title not available (Why is that?)
• Polylogarithmic inapproximability
• Approximation Algorithms for Directed Steiner Problems
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Strong computational lower bounds via parameterized complexity
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• A tight lower bound for planar multiway cut with fixed number of terminals
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

Cited In (4)

• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands

This page was built for publication: A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

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