Search Results

Documents authored by Chitnis, Rajesh

Document
DOI: 10.4230/LIPIcs.SoCG.2022.28
Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d

Authors: Rajesh Chitnis and Nitin Saurabh

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In the discrete k-Center problem, we are given a metric space (P,dist) where |P| = n and the goal is to select a set C ⊆ P of k centers which minimizes the maximum distance of a point in P from its nearest center. For any ε > 0, Agarwal and Procopiuc [SODA '98, Algorithmica '02] designed an (1+ε)-approximation algorithm for this problem in d-dimensional Euclidean space which runs in O(dn log k) + (k/ε)^{O (k^{1-1/d})}⋅ n^{O(1)} time. In this paper we show that their algorithm is essentially optimal: if for some d ≥ 2 and some computable function f, there is an f(k)⋅(1/ε)^{o (k^{1-1/d})} ⋅ n^{o (k^{1-1/d})} time algorithm for (1+ε)-approximating the discrete k-Center on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a d-dimensional constraint satisfaction problem (CSP) to discrete d-dimensional k-Center. This reduction has the property that there is a fixed value ε (depending on the CSP) such that the optimal radius of k-Center instances corresponding to satisfiable and unsatisfiable instances of the CSP is < 1 and ≥ (1+ε) respectively. Our claimed lower bound on the running time for approximating discrete k-Center in d-dimensions then follows from the lower bound due to Marx and Sidiropoulos [SoCG '14] for checking the satisfiability of the aforementioned d-dimensional CSP. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in n^{O (d⋅ k^{1-1/d})} time for discrete k-Center on n points in d-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some d ≥ 2 and some computable function f, there is an f(k)⋅n^{o (k^{1-1/d})} time exact algorithm for the discrete k-Center problem on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for d = 2 and was implicit in the work of Marx [IWPEC '06].
Cite as

Rajesh Chitnis and Nitin Saurabh. Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chitnis_et_al:LIPIcs.SoCG.2022.28,
  author =	{Chitnis, Rajesh and Saurabh, Nitin},
  title =	{{Tight Lower Bounds for Approximate \& Exact k-Center in \mathbb{R}^d}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.28},
  URN =		{urn:nbn:de:0030-drops-160365},
  doi =		{10.4230/LIPIcs.SoCG.2022.28},
  annote =	{Keywords: k-center, Euclidean space, Exponential Time Hypothesis (ETH), lower bound}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.7
Towards a Theory of Parameterized Streaming Algorithms

Authors: Rajesh Chitnis and Graham Cormode

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Parameterized complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we analyze the running time with respect to additional parameters. This approach has proven to be highly successful in delineating our understanding of NP-hard problems. Given this success with the TIME resource, it seems but natural to use this approach for dealing with the SPACE resource. First attempts in this direction have considered a few individual problems, with some success: Fafianie and Kratsch [MFCS'14] and Chitnis et al. [SODA'15] introduced the notions of streaming kernels and parameterized streaming algorithms respectively. For example, the latter shows how to refine the Omega(n^2) bit lower bound for finding a minimum Vertex Cover (VC) in the streaming setting by designing an algorithm for the parameterized k-VC problem which uses O(k^{2}log n) bits. In this paper, we initiate a systematic study of graph problems from the paradigm of parameterized streaming algorithms. We first define a natural hierarchy of space complexity classes of FPS, SubPS, SemiPS, SupPS and BrutePS, and then obtain tight classifications for several well-studied graph problems such as Longest Path, Feedback Vertex Set, Dominating Set, Girth, Treewidth, etc. into this hierarchy (see Figure 1 and Table 1). On the algorithmic side, our parameterized streaming algorithms use techniques from the FPT world such as bidimensionality, iterative compression and bounded-depth search trees. On the hardness side, we obtain lower bounds for the parameterized streaming complexity of various problems via novel reductions from problems in communication complexity. We also show a general (unconditional) lower bound for space complexity of parameterized streaming algorithms for a large class of problems inspired by the recently developed frameworks for showing (conditional) kernelization lower bounds. Parameterized algorithms and streaming algorithms are approaches to cope with TIME and SPACE intractability respectively. It is our hope that this work on parameterized streaming algorithms leads to two-way flow of ideas between these two previously separated areas of theoretical computer science.
Cite as

Rajesh Chitnis and Graham Cormode. Towards a Theory of Parameterized Streaming Algorithms. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chitnis_et_al:LIPIcs.IPEC.2019.7,
  author =	{Chitnis, Rajesh and Cormode, Graham},
  title =	{{Towards a Theory of Parameterized Streaming Algorithms}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.7},
  URN =		{urn:nbn:de:0030-drops-114682},
  doi =		{10.4230/LIPIcs.IPEC.2019.7},
  annote =	{Keywords: Parameterized Algorithms, Streaming Algorithms, Kernels}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.8
FPT Inapproximability of Directed Cut and Connectivity Problems

Authors: Rajesh Chitnis and Andreas Emil Feldmann

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a series of papers over the last decade, we now have (almost) tight bounds for the running time of several standard variants of these problems parameterized by two parameters: the number k of terminals and the size p of the solution. When there is evidence of FPT intractability, then the next natural alternative is to consider FPT approximations. In this paper, we show two types of results for directed cut and connectivity problems, building on existing results from the literature: first is to circumvent the hardness results for these problems by designing FPT approximation algorithms, or alternatively strengthen the existing hardness results by creating "gap-instances" under stronger hypotheses such as the (Gap-)Exponential Time Hypothesis (ETH). Formally, we show the following results: Cutting paths between a set of terminal pairs, i.e., Directed Multicut: Pilipczuk and Wahlstrom [TOCT '18] showed that Directed Multicut is W[1]-hard when parameterized by p if k=4. We complement this by showing the following two results: - Directed Multicut has a k/2-approximation in 2^{O(p^2)}* n^{O(1)} time (i.e., a 2-approximation if k=4), - Under Gap-ETH, Directed Multicut does not admit an (59/58-epsilon)-approximation in f(p)* n^{O(1)} time, for any computable function f, even if k=4. Connecting a set of terminal pairs, i.e., Directed Steiner Network (DSN): The DSN problem on general graphs is known to be W[1]-hard parameterized by p+k due to Guo et al. [SIDMA '11]. Dinur and Manurangsi [ITCS '18] further showed that there is no FPT k^{1/4-o(1)}-approximation algorithm parameterized by k, under Gap-ETH. Chitnis et al. [SODA '14] considered the restriction to special graph classes, but unfortunately this does not lead to FPT algorithms either: DSN on planar graphs is W[1]-hard parameterized by k. In this paper we consider the DSN_Planar problem which is an intermediate version: the graph is general, but we want to find a solution whose cost is at most that of an optimal planar solution (if one exists). We show the following lower bounds for DSN_Planar: - DSN_Planar has no (2-epsilon)-approximation in FPT time parameterized by k, under Gap-ETH. This answers in the negative a question of Chitnis et al. [ESA '18]. - DSN_Planar is W[1]-hard parameterized by k+p. Moreover, under ETH, there is no (1+epsilon)-approximation for DSN_Planar in f(k,p,epsilon)* n^{o(k+sqrt{p+1/epsilon})} time for any computable function f. Pairwise connecting a set of terminals, i.e., Strongly Connected Steiner Subgraph (SCSS): Guo et al. [SIDMA '11] showed that SCSS is W[1]-hard parameterized by p+k, while Chitnis et al. [SODA '14] showed that SCSS remains W[1]-hard parameterized by p, even if the input graph is planar. In this paper we consider the SCSS_Planar problem which is an intermediate version: the graph is general, but we want to find a solution whose cost is at most that of an optimal planar solution (if one exists). We show the following lower bounds for SCSS_Planar: - SCSS_Planar is W[1]-hard parameterized by k+p. Moreover, under ETH, there is no (1+epsilon)-approximation for SCSS_Planar in f(k,p,epsilon)* n^{o(sqrt{k+p+1/epsilon})} time for any computable function f. Previously, the only known FPT approximation results for SCSS applied to general graphs parameterized by k: a 2-approximation by Chitnis et al. [IPEC '13], and a matching (2-epsilon)-hardness under Gap-ETH by Chitnis et al. [ESA '18].
Cite as

Rajesh Chitnis and Andreas Emil Feldmann. FPT Inapproximability of Directed Cut and Connectivity Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chitnis_et_al:LIPIcs.IPEC.2019.8,
  author =	{Chitnis, Rajesh and Feldmann, Andreas Emil},
  title =	{{FPT Inapproximability of Directed Cut and Connectivity Problems}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.8},
  URN =		{urn:nbn:de:0030-drops-114692},
  doi =		{10.4230/LIPIcs.IPEC.2019.8},
  annote =	{Keywords: Directed graphs, cuts, connectivity, Steiner problems, FPT inapproximability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.20
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

Authors: Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph G=(V,E) and a set {D}subseteq V x V of k demand pairs. The aim is to compute the cheapest network N subseteq G for which there is an s -> t path for each (s,t)in {D}. It is known that this problem is notoriously hard as there is no k^{1/4-o(1)}-approximation algorithm under Gap-ETH, even when parameterizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k. For the bi-DSN_Planar problem, the aim is to compute a planar optimum solution N subseteq G in a bidirected graph G, i.e. for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of bi-DSN_Planar, unless FPT=W[1]. Additionally we study several generalizations of bi-DSN_Planar and obtain upper and lower bounds on obtainable runtimes parameterized by k. One important special case of DSN is the Strongly Connected Steiner Subgraph (SCSS) problem, for which the solution network N subseteq G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under Gap-ETH there is no (2-{epsilon})-approximation algorithm parameterized by k (for any epsilon>0). To the best of our knowledge, this is the first example of a W[1]-hard problem admitting a non-trivial parameterized approximation factor which is also known to be tight! Additionally we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k.
Cite as

Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chitnis_et_al:LIPIcs.ESA.2018.20,
  author =	{Chitnis, Rajesh and Feldmann, Andreas Emil and Manurangsi, Pasin},
  title =	{{Parameterized Approximation Algorithms for Bidirected Steiner Network Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.20},
  URN =		{urn:nbn:de:0030-drops-94833},
  doi =		{10.4230/LIPIcs.ESA.2018.20},
  annote =	{Keywords: Directed Steiner Network, Strongly Connected Steiner Subgraph, Parameterized Approximations, Bidirected Graphs, Planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.79
Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs

Authors: Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach

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

Abstract
We consider the Directed Anchored k-Core problem, where the task is for a given directed graph G and integers b, k and p, to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k. For undirected graphs, this problem was introduced by Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012]. We undertake a systematic analysis of the computational complexity of Directed Anchored k-Core and show that: - The decision version of the problem is NP-complete for every k>=1 even if the input graph is restricted to be a planar directed acyclic graph of maximum degree at most k+2. - The problem is fixed parameter tractable (FPT) parameterized by the size of the core p for k=1, and W[1]-hard for k>=2. - When the maximum degree of the graph is at most Delta, the problem is FPT parameterized by p+Delta if k>=Delta/2.
Cite as

Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 79-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chitnis_et_al:LIPIcs.FSTTCS.2013.79,
  author =	{Chitnis, Rajesh and Fomin, Fedor V. and Golovach, Petr A.},
  title =	{{Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{79--90},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.79},
  URN =		{urn:nbn:de:0030-drops-43636},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.79},
  annote =	{Keywords: Parameterized complexity, directed graphs, anchored \$k\$-core}
}
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