Search Results

Documents authored by Nutov, Zeev

Document
DOI: 10.4230/LIPIcs.ESA.2024.92
Parameterized Algorithms for Node Connectivity Augmentation Problems

Authors: Zeev Nutov

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A graph G is k-out-connected from its node s if it contains k internally disjoint sv-paths to every node v; G is k-connected if it is k-out-connected from every node. In connectivity augmentation problems, the goal is to augment a graph G₀ = (V,E₀) by a minimum costs edge set J such that G₀ ∪ J has higher connectivity than G₀. In the k-Out-Connectivity Augmentation ({k-OCA}) problem, G₀ is (k-1)-out-connected from s and G₀ ∪ J should be k-out-connected from s; in the k-Connectivity Augmentation ({k-CA}) problem G₀ is (k-1)-connected and G₀ ∪ J should be k-connected. The parameterized complexity status of these problems was open even for k = 3 and unit costs. We will show that {k-OCA} and 3-{CA} can be solved in time 9^p ⋅ n^{O(1)}, where p is the size of an optimal solution. Our paper is the first that shows fixed-parameter tractability of a k-node-connectivity augmentation problem with high values of k. We will also consider the (2,k)-Connectivity Augmentation ({(2,k)-CA}) problem where G₀ is (k-1)-edge-connected and G₀ ∪ J should be both k-edge-connected and 2-connected. We will show that this problem can be solved in time 9^p ⋅ n^{O(1)}, and for unit costs approximated within 1.892.
Cite as

Zeev Nutov. Parameterized Algorithms for Node Connectivity Augmentation Problems. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 92:1-92:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{nutov:LIPIcs.ESA.2024.92,
  author =	{Nutov, Zeev},
  title =	{{Parameterized Algorithms for Node Connectivity Augmentation Problems}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{92:1--92:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.92},
  URN =		{urn:nbn:de:0030-drops-211639},
  doi =		{10.4230/LIPIcs.ESA.2024.92},
  annote =	{Keywords: node connectivity augmentation, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.82
Data Structures for Node Connectivity Queries

Authors: Zeev Nutov

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Let κ(s,t) denote the maximum number of internally disjoint st-paths in an undirected graph G. We consider designing a data structure that includes a list of cuts, and answers the following query: given s,t ∈ V, determine whether κ(s,t) ≤ k, and if so, return a pointer to an st-cut of size ≤ k (or to a minimum st-cut) in the list. A trivial data structure that includes a list of n(n-1)/2 cuts and requires Θ(kn²) space can answer each query in O(1) time. We obtain the following results. - In the case when G is k-connected, we show that 2n cuts suffice, and that these cuts can be partitioned into 2k+1 laminar families. Thus using space O(kn) we can answers each min-cut query in O(1) time, slightly improving and substantially simplifying the proof of a recent result of Pettie and Yin [S. Pettie and L. Yin, 2021]. We then extend this data structure to subset k-connectivity. - In the general case we show that (2k+1)n cuts suffice to return an st-cut of size ≤ k, and a list of size k(k+2)n contains a minimum st-cut for every s,t ∈ V. Combining our subset k-connectivity data structure with the data structure of Hsu and Lu [T-H. Hsu and H-I. Lu, 2009] for checking k-connectivity, we give an O(k² n) space data structure that returns an st-cut of size ≤ k in O(log k) time, while O(k³ n) space enables to return a minimum st-cut.
Cite as

Zeev Nutov. Data Structures for Node Connectivity Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 82:1-82:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nutov:LIPIcs.ESA.2022.82,
  author =	{Nutov, Zeev},
  title =	{{Data Structures for Node Connectivity Queries}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{82:1--82:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.82},
  URN =		{urn:nbn:de:0030-drops-170205},
  doi =		{10.4230/LIPIcs.ESA.2022.82},
  annote =	{Keywords: node connectivity, minimum cuts, data structure, connectivity queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.73
Approximating k-Connected m-Dominating Sets

Authors: Zeev Nutov

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
A subset S of nodes in a graph G is a k-connected m-dominating set ((k,m)-cds) if the subgraph G[S] induced by S is k-connected and every v ∈ V⧵S has at least m neighbors in S. In the k-Connected m-Dominating Set ((k,m)-CDS) problem the goal is to find a minimum weight (k,m)-cds in a node-weighted graph. For m ≥ k we obtain the following approximation ratios. For general graphs our ratio O(k ln n) improves the previous best ratio O(k² ln n) of [Z. Nutov, 2018] and matches the best known ratio for unit weights of [Z. Zhang et al., 2018]. For unit disk graphs we improve the ratio O(k ln k) of [Z. Nutov, 2018] to min{m/(m-k),k^{2/3}} ⋅ O(ln² k) - this is the first sublinear ratio for the problem, and the first polylogarithmic ratio O(ln² k)/ε when m ≥ (1+ε)k; furthermore, we obtain ratio min{m/(m-k), √k} ⋅ O(ln² k) for uniform weights. These results are obtained by showing the same ratios for the Subset k-Connectivity problem when the set of terminals is an m-dominating set.
Cite as

Zeev Nutov. Approximating k-Connected m-Dominating Sets. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nutov:LIPIcs.ESA.2020.73,
  author =	{Nutov, Zeev},
  title =	{{Approximating k-Connected m-Dominating Sets}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.73},
  URN =		{urn:nbn:de:0030-drops-129392},
  doi =		{10.4230/LIPIcs.ESA.2020.73},
  annote =	{Keywords: k-connected graph, m-dominating set, approximation algorithm, rooted subset k-connectivity, subset k-connectivity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.20
Approximating Activation Edge-Cover and Facility Location Problems

Authors: Zeev Nutov, Guy Kortsarz, and Eli Shalom

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V,E), a set R subseteq V of terminals, and thresholds {t^e_u,t^e_v} for each uv-edge e in E. The goal is to find an assignment a={a_v:v in V} to the nodes minimizing sum_{v in V} a_v, such that the edge set E_a={e=uv: a_u >= t^e_u, a_v >= t^e_v} activated by a covers R. We obtain ratio 1+max_{x>=1}(ln x)/(1+x/theta)~= ln theta - ln ln theta for the problem, where theta is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of {Facility Location}. If for each facility all service costs are identical then we show a better ratio 1+max_{k in N}(H_k-1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [Calinescu et al, 2019] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73/60~=1.217 of [Calinescu et al, 2019] to 1555/1347~=1.155.
Cite as

Zeev Nutov, Guy Kortsarz, and Eli Shalom. Approximating Activation Edge-Cover and Facility Location Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{nutov_et_al:LIPIcs.MFCS.2019.20,
  author =	{Nutov, Zeev and Kortsarz, Guy and Shalom, Eli},
  title =	{{Approximating Activation Edge-Cover and Facility Location Problems}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.20},
  URN =		{urn:nbn:de:0030-drops-109642},
  doi =		{10.4230/LIPIcs.MFCS.2019.20},
  annote =	{Keywords: generalized min-covering problem, activation edge-cover, facility location, minimum power, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.61
On the Tree Augmentation Problem

Authors: Zeev Nutov

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
In the Tree Augmentation problem we are given a tree T=(V,F) and a set E of edges with positive integer costs {c_e:e in E}. The goal is to augment T by a minimum cost edge set J subseteq E such that T cup J is 2-edge-connected. We obtain the following results. Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost M of an edge in E is bounded by a constant; his algorithm computes a 1.96418+epsilon approximate solution in time n^{{(M/epsilon^2)}^{O(1)}}. Using a simpler LP, we achieve ratio 12/7+epsilon in time ^{O(M/epsilon^2)}. This also gives ratio better than 2 for logarithmic costs, and not only for constant costs. In addition, we will show that (for arbitrary costs) the problem admits ratio 3/2 for trees of diameter <= 7. One of the oldest open questions for the problem is whether for unit costs (when M=1) the standard LP-relaxation, so called Cut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most 28/15=2-2/15. In addition, we will suggest another natural LP-relaxation that is much simpler than the ones in previous work, and prove that it has integrality gap at most 7/4.
Cite as

Zeev Nutov. On the Tree Augmentation Problem. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{nutov:LIPIcs.ESA.2017.61,
  author =	{Nutov, Zeev},
  title =	{{On the Tree Augmentation Problem}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.61},
  URN =		{urn:nbn:de:0030-drops-78345},
  doi =		{10.4230/LIPIcs.ESA.2017.61},
  annote =	{Keywords: Tree augmentation, Logarithmic costs, Approximation algorithm, Half-integral extreme points, Integrality gap}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.13
LP-Relaxations for Tree Augmentation

Authors: Guy Kortsarz and Zeev Nutov

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7/4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case.
Cite as

Guy Kortsarz and Zeev Nutov. LP-Relaxations for Tree Augmentation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kortsarz_et_al:LIPIcs.APPROX-RANDOM.2016.13,
  author =	{Kortsarz, Guy and Nutov, Zeev},
  title =	{{LP-Relaxations for Tree Augmentation}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.13},
  URN =		{urn:nbn:de:0030-drops-66366},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.13},
  annote =	{Keywords: Tree Augmentation; LP-relaxation; Laminar family; Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.115
Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights

Authors: Michael Dinitz, Guy Kortsarz, and Zeev Nutov

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
In the Steiner k-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer k \leq |D|. The goal is to find a minimum cost subgraph that connects at least k pairs. The best known ratio for this problem is min{O(sqrt{n}),O(sqrt{k})} [Gupta et al., 2008]. In [Gupta et al., 2008] it is also shown that ratio rho for Steiner k-Forest implies ratio O(rho log^2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most k objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [Gupta et al., 2008], has ratio O(sqrt{n}) [Charikar and Raghavachari, 1998]. We obtain ratio n^{0.448} for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O(sqrt{n}) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(n^{epsilon}), then one can achieve ratio O(n^{(1+epsilon) 0.448}), which is less than sqrt{n} if epsilon is small enough. To prove our main result we consider the following generalization of the Minimum k-Edge Subgraph (Mk-ES) problem, which we call Min-Cost l-Edge-Profit Subgraph (MCl-EPS): Given a graph G=(V,E) with edge-profits p={p_e: e in E} and node-costs c={c_v: v in V}, and a lower profit bound l, find a minimum node-cost subgraph of G of edge profit at least l. The Mk-ES problem is a special case of MCl-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n^{3-2*sqrt{2} + epsilon} (note that 3-2*sqrt{2} < 0.1716). We extend this ratio to MCl-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.
Cite as

Michael Dinitz, Guy Kortsarz, and Zeev Nutov. Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 115-127, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.APPROX-RANDOM.2014.115,
  author =	{Dinitz, Michael and Kortsarz, Guy and Nutov, Zeev},
  title =	{{Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{115--127},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.115},
  URN =		{urn:nbn:de:0030-drops-46925},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.115},
  annote =	{Keywords: k-Steiner Forest; Uniform weights; Densest k-Subgraph; Approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.09511.4
Approximating minimum cost connectivity problems

Authors: Guy Kortsarz and Zeev Nutov

Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)

Abstract
We survey approximation algorithms of connectivity problems. The survey presented describing various techniques. In the talk the following techniques and results are presented. 1)Outconnectivity: Its well known that there exists a polynomial time algorithm to solve the problems of finding an edge k-outconnected from r subgraph [EDMONDS] and a vertex k-outconnectivity subgraph from r [Frank-Tardos] . We show how to use this to obtain a ratio 2 approximation for the min cost edge k-connectivity problem. 2)The critical cycle theorem of Mader: We state a fundamental theorem of Mader and use it to provide a 1+(k-1)/n ratio approximation for the min cost vertex k-connected subgraph, in the metric case. We also show results for the min power vertex k-connected problem using this lemma. We show that the min power is equivalent to the min-cost case with respect to approximation. 3)Laminarity and uncrossing: We use the well known laminarity of a BFS solution and show a simple new proof due to Ravi et al for Jain's 2 approximation for Steiner network.
Cite as

Guy Kortsarz and Zeev Nutov. Approximating minimum cost connectivity problems. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kortsarz_et_al:DagSemProc.09511.4,
  author =	{Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating minimum cost connectivity problems}},
  booktitle =	{Parameterized complexity and approximation algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9511},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.4},
  URN =		{urn:nbn:de:0030-drops-24975},
  doi =		{10.4230/DagSemProc.09511.4},
  annote =	{Keywords: Connectivity, laminar, uncrossing, Mader's Theorem, power problems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2324
Approximating Fault-Tolerant Group-Steiner Problems

Authors: Rohit Khandekar, Guy Kortsarz, and Zeev Nutov

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf Fault-Tolerant Group-Steiner} problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e.g., edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and $2$-connecting from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an {\em uncros\-sable} set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and $2$-connecting a carefully chosen single vertex. To handle large group-sizes, we use a $p$-Steiner tree algorithm to identify the ``correct'' pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.
Cite as

Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. Approximating Fault-Tolerant Group-Steiner Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 263-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2009.2324,
  author =	{Khandekar, Rohit and Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating Fault-Tolerant Group-Steiner Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{263--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2324},
  URN =		{urn:nbn:de:0030-drops-23243},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2324},
  annote =	{Keywords: Fault-tolerance, group Steiner problem, edge-disjointness, vertex-disjointness, approximation, connectivity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact