English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Survivable Network Design for Group Connectivity in Low-Treewidth Graphs

Chalermsook, P., Das, S., Even, G., Laekhanukit, B., & Vaz, D. (2018). Survivable Network Design for Group Connectivity in Low-Treewidth Graphs. Retrieved from http://arxiv.org/abs/1802.10403.

Item is

Files

show Files
hide Files
:
arXiv:1802.10403.pdf (Preprint), 813KB
Name:
arXiv:1802.10403.pdf
Description:
File downloaded from arXiv at 2018-12-12 09:54
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Chalermsook, Parinya1, Author           
Das, Syamantak1, Author
Even, Guy1, Author
Laekhanukit, Bundit2, Author           
Vaz, Daniel2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM
 Abstract: In the Group Steiner Tree problem (GST), we are given a (vertex or
edge)-weighted graph $G=(V,E)$ on $n$ vertices, a root vertex $r$ and a
collection of groups $\{S_i\}_{i\in[h]}: S_i\subseteq V(G)$. The goal is to
find a min-cost subgraph $H$ that connects the root to every group. We consider
a fault-tolerant variant of GST, which we call Restricted (Rooted) Group SNDP.
In this setting, each group $S_i$ has a demand $k_i\in[k],k\in\mathbb N$, and
we wish to find a min-cost $H\subseteq G$ such that, for each group $S_i$,
there is a vertex in $S_i$ connected to the root via $k_i$ (vertex or edge)
disjoint paths.
While GST admits $O(\log^2 n\log h)$ approximation, its high connectivity
variants are Label-Cover hard, and for the vertex-weighted version, the
hardness holds even when $k=2$. Previously, positive results were known only
for the edge-weighted version when $k=2$ [Gupta et al., SODA 2010; Khandekar et
al., Theor. Comput. Sci., 2012] and for a relaxed variant where the disjoint
paths may end at different vertices in a group [Chalermsook et al., SODA 2015].
Our main result is an $O(\log n\log h)$ approximation for Restricted Group
SNDP that runs in time $n^{f(k, w)}$, where $w$ is the treewidth of $G$. This
nearly matches the lower bound when $k$ and $w$ are constant. The key to
achieving this result is a non-trivial extension of the framework in
[Chalermsook et al., SODA 2017], which embeds all feasible solutions to the
problem into a dynamic program (DP) table. However, finding the optimal
solution in the DP table remains intractable. We formulate a linear program
relaxation for the DP and obtain an approximate solution via randomized
rounding. This framework also allows us to systematically construct DP tables
for high-connectivity problems. As a result, we present new exact algorithms
for several variants of survivable network design problems in low-treewidth
graphs.

Details

show
hide
Language(s): eng - English
 Dates: 2018-02-282018
 Publication Status: Published online
 Pages: 28 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1802.10403
URI: http://arxiv.org/abs/1802.10403
BibTex Citekey: Chalermsook_arXiv1802.10403
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show