30 Search Results for "Agrawal, Akanksha"


Document
Local Recurrent Problems in the SUPPORTED Model

Authors: Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [Schmid and Suomela, 2013], which generalizes the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply. recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds. Our main contribution is to expand the class of problems to which the SUPPORTED model applies, by handling also multiple recurring instances of the same problem that differ from each other by some problem specific input, and not only the subnetwork to which they apply. We illustrate this by considering two extended problem classes. The first class, denoted PCS, concerns problems where client nodes of the network need to be served, and each recurring instance applies to some Partial Client Set. The second class, denoted PFO, concerns situations where each recurrent instance of the problem includes a partially fixed output, which needs to be completed to a full consistent solution. Specifically, we propose some natural recurrent variants of the dominating set problem and the coloring problem that are of interest particularly in the distributed setting. For these problems, we show that information about the topology can be used to overcome locality-based lower bounds. We also categorize the round complexity of Locally Checkable Labellings in the SUPPORTED model for the simple case of paths. Finally we present some interesting open problems and some partial results towards resolving them.

Cite as

Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran. Local Recurrent Problems in the SUPPORTED Model. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.OPODIS.2023.22,
  author =	{Agrawal, Akanksha and Augustine, John and Peleg, David and Ramachandran, Srikkanth},
  title =	{{Local Recurrent Problems in the SUPPORTED Model}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.22},
  URN =		{urn:nbn:de:0030-drops-195124},
  doi =		{10.4230/LIPIcs.OPODIS.2023.22},
  annote =	{Keywords: Distributed Algorithms, LOCAL Model, SUPPORTED Model}
}
Document
Approximately Interpolating Between Uniformly and Non-Uniformly Polynomial Kernels

Authors: Akanksha Agrawal and M. S. Ramanujan

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)


Abstract
The problem of computing a minimum set of vertices intersecting a finite set of forbidden minors in a given graph is a fundamental graph problem in the area of kernelization with numerous well-studied special cases. A major breakthrough in this line of research was made by Fomin et al. [FOCS 2012], who showed that the ρ-Treewidth Modulator problem (delete minimum number of vertices to ensure that treewidth is at most ρ) has a polynomial kernel of size k^g(ρ) for some function g. A second standout result in this line is that of Giannapoulou et al. [ACM TALG 2017], who obtained an f(η)k^𝒪(1)-size kernel (for some function f) for the η-Treedepth Modulator problem (delete fewest number of vertices to make treedepth at most η) and showed that some dependence of the exponent of k on ρ in the result of Fomin et al. for the ρ-Treewidth Modulator problem is unavoidable under reasonable complexity hypotheses. In this work, we provide an approximate interpolation between these two results by giving, for every ε > 0, a (1+ε)-approximate kernel of size f'(η,ρ,1/ε)⋅ k^g'(ρ) (for some functions f' and g') for the problem of deciding whether k vertices can be deleted from a given graph to obtain a graph that has elimination distance at most η to the class of graphs that have treewidth at most ρ. Graphs of treedepth η are precisely the graphs with elimination distance at most η-1 to the graphs of treewidth 0 and graphs of treewidth ρ are simply graphs with elimination distance 0 to graphs of treewidth ρ. Consequently, our result "approximately" interpolates between these two major results in this active line of research.

Cite as

Akanksha Agrawal and M. S. Ramanujan. Approximately Interpolating Between Uniformly and Non-Uniformly Polynomial Kernels. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2023.36,
  author =	{Agrawal, Akanksha and Ramanujan, M. S.},
  title =	{{Approximately Interpolating Between Uniformly and Non-Uniformly Polynomial Kernels}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.36},
  URN =		{urn:nbn:de:0030-drops-194096},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.36},
  annote =	{Keywords: Lossy Kernelization, Treewidth Modulator, Vertex Deletion Problems}
}
Document
Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481)

Authors: Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, Oliver Schaudt, and Akanksha Agrawal

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22481 "Vertex Partitioning in Graphs: From Structure to Algorithms", which was held from 27 November to 2 December 2023. The report contains abstracts for presentations about recent structural and algorithmic developments for a variety of vertex partitioning problems. It also contains a collection of open problems which were posed during the seminar.

Cite as

Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, Oliver Schaudt, and Akanksha Agrawal. Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481). In Dagstuhl Reports, Volume 12, Issue 11, pp. 109-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{chudnovsky_et_al:DagRep.12.11.109,
  author =	{Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha},
  title =	{{Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481)}},
  pages =	{109--123},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.11.109},
  URN =		{urn:nbn:de:0030-drops-178384},
  doi =		{10.4230/DagRep.12.11.109},
  annote =	{Keywords: computational complexity, hereditary graph classes, parameterized algorithms, polynomial-time algorithms, vertex partitioning}
}
Document
On Finding Short Reconfiguration Sequences Between Independent Sets

Authors: Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
Assume we are given a graph G, two independent sets S and T in G of size k ≥ 1, and a positive integer 𝓁 ≥ 1. The goal is to decide whether there exists a sequence ⟨ I₀, I₁, ..., I_𝓁 ⟩ of independent sets such that for all j ∈ {0,…,𝓁-1} the set I_j is an independent set of size k, I₀ = S, I_𝓁 = T, and I_{j+1} is obtained from I_j by a predetermined reconfiguration rule. We consider two reconfiguration rules, namely token sliding and token jumping. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most 𝓁 steps that transforms S into T, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex (while maintaining independence). In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph (as long as we maintain independence). Both TSO and TJO are known to be fixed-parameter tractable when parameterized by 𝓁 on nowhere dense classes of graphs. In this work, we investigate the boundary of tractability for sparse classes of graphs. We show that both problems are fixed-parameter tractable for parameter k + 𝓁 + d on d-degenerate graphs as well as for parameter |M| + 𝓁 + Δ on graphs having a modulator M whose deletion leaves a graph of maximum degree Δ. We complement these result by showing that for parameter 𝓁 alone both problems become W[1]-hard already on 2-degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. [Daniel Lokshtanov et al., 2020]. Finally, we show as a side result that using such families we can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem (a.k.a. Token Jumping) parameterized by k on both degenerate and nowhere dense classes of graphs.

Cite as

Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. On Finding Short Reconfiguration Sequences Between Independent Sets. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2022.39,
  author =	{Agrawal, Akanksha and Hait, Soumita and Mouawad, Amer E.},
  title =	{{On Finding Short Reconfiguration Sequences Between Independent Sets}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.39},
  URN =		{urn:nbn:de:0030-drops-173244},
  doi =		{10.4230/LIPIcs.ISAAC.2022.39},
  annote =	{Keywords: Token sliding, token jumping, fixed-parameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}
Document
A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

Authors: Akanksha Agrawal, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)


Abstract
The Delaunay graph of a point set P ⊆ ℝ² is the plane graph with the vertex-set P and the edge-set that contains {p,p'} if there exists a disc whose intersection with P is exactly {p,p'}. Accordingly, a triangulated graph G is Delaunay realizable if there exists a triangulation of the Delaunay graph of some P ⊆ ℝ², called a Delaunay triangulation of P, that is isomorphic to G. The objective of Delaunay Realization is to compute a point set P ⊆ ℝ² that realizes a given graph G (if such a P exists). Known algorithms do not solve Delaunay Realization as they are non-constructive. Obtaining a constructive algorithm for Delaunay Realization was mentioned as an open problem by Hiroshima et al. [Hiroshima et al., 2000]. We design an n^𝒪(n)-time constructive algorithm for Delaunay Realization. In fact, our algorithm outputs sets of points with integer coordinates.

Cite as

Akanksha Agrawal, Saket Saurabh, and Meirav Zehavi. A Finite Algorithm for the Realizabilty of a Delaunay Triangulation. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2022.1,
  author =	{Agrawal, Akanksha and Saurabh, Saket and Zehavi, Meirav},
  title =	{{A Finite Algorithm for the Realizabilty of a Delaunay Triangulation}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.1},
  URN =		{urn:nbn:de:0030-drops-173573},
  doi =		{10.4230/LIPIcs.IPEC.2022.1},
  annote =	{Keywords: Delaunay Triangulation, Delaunay Realization, Finite Algorithm, Integer Coordinate Realization}
}
Document
Parameterized Complexity of Perfectly Matched Sets

Authors: Akanksha Agrawal, Sutanay Bhattacharjee, Satyabrata Jana, and Abhishek Sahu

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)


Abstract
For an undirected graph G, a pair of vertex disjoint subsets (A, B) is a pair of perfectly matched sets if each vertex in A (resp. B) has exactly one neighbor in B (resp. A). In the above, the size of the pair is |A| (= |B|). Given a graph G and a positive integer k, the Perfectly Matched Sets problem asks whether there exists a pair of perfectly matched sets of size at least k in G. This problem is known to be NP-hard on planar graphs and W[1]-hard on general graphs, when parameterized by k. However, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we study the problem parameterized by k, and design FPT algorithms for: i) apex-minor-free graphs running in time 2^O(√k)⋅ n^O(1), and ii) K_{b,b}-free graphs. We obtain a linear kernel for planar graphs and k^𝒪(d)-sized kernel for d-degenerate graphs. It is known that the problem is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k. We complement this hardness result by designing a polynomial-time algorithm for interval graphs.

Cite as

Akanksha Agrawal, Sutanay Bhattacharjee, Satyabrata Jana, and Abhishek Sahu. Parameterized Complexity of Perfectly Matched Sets. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2022.2,
  author =	{Agrawal, Akanksha and Bhattacharjee, Sutanay and Jana, Satyabrata and Sahu, Abhishek},
  title =	{{Parameterized Complexity of Perfectly Matched Sets}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.2},
  URN =		{urn:nbn:de:0030-drops-173580},
  doi =		{10.4230/LIPIcs.IPEC.2022.2},
  annote =	{Keywords: Perfectly Matched Sets, Parameterized Complexity, Apex-minor-free graphs, d-degenerate graphs, Planar graphs, Interval Graphs}
}
Document
A Polynomial Kernel for Deletion to Ptolemaic Graphs

Authors: Akanksha Agrawal, Aditya Anand, and Saket Saurabh

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)


Abstract
For a family of graphs F, given a graph G and an integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in the family F. The F-Deletion problems for all non-trivial families F that satisfy the hereditary property on induced subgraphs are known to be NP-hard by a result of Yannakakis (STOC'78). Ptolemaic graphs are the graphs that satisfy the Ptolemy inequality, and they are the intersection of chordal graphs and distance-hereditary graphs. Equivalently, they form the set of graphs that do not contain any chordless cycles or a gem as an induced subgraph. (A gem is the graph on 5 vertices, where four vertices form an induced path, and the fifth vertex is adjacent to all the vertices of this induced path.) The Ptolemaic Deletion problem is the F-Deletion problem, where F is the family of Ptolemaic graphs. In this paper we study Ptolemaic Deletion from the viewpoint of Kernelization Complexity, and obtain a kernel with 𝒪(k⁶) vertices for the problem.

Cite as

Akanksha Agrawal, Aditya Anand, and Saket Saurabh. A Polynomial Kernel for Deletion to Ptolemaic Graphs. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2021.1,
  author =	{Agrawal, Akanksha and Anand, Aditya and Saurabh, Saket},
  title =	{{A Polynomial Kernel for Deletion to Ptolemaic Graphs}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.1},
  URN =		{urn:nbn:de:0030-drops-153840},
  doi =		{10.4230/LIPIcs.IPEC.2021.1},
  annote =	{Keywords: Ptolemaic Deletion, Kernelization, Parameterized Complexity, Gem-free chordal graphs}
}
Document
Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH

Authors: Akanksha Agrawal, Ravi Kiran Allumalla, and Varun Teja Dhanekula

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)


Abstract
In this article we study a well-known problem, called Bipartite Token Jumping and not-so-well known problem(s), which we call, Half (Induced-) Subgraph, and show that under Gap-ETH, these problems do not admit FPT algorithms. The problem Bipartite Token Jumping takes as input a bipartite graph G and two independent sets S,T in G, where |S| = |T| = k, and the objective is to test if there is a sequence of exactly k-sized independent sets ⟨ I₀, I₁,⋯, I_𝓁 ⟩ in G, such that: i) I₀ = S and I_𝓁 = T, and ii) for every j ∈ [𝓁], I_{j} is obtained from I_{j-1} by replacing a vertex in I_{j-1} by a vertex in V(G) ⧵ I_{j-1}. We show that, assuming Gap-ETH, Bipartite Token Jumping does not admit an FPT algorithm. We note that this result resolves one of the (two) open problems posed by Bartier et al. (ISAAC 2020), under Gap-ETH. Most of the known reductions related to Token Jumping exploit the property given by triangles (i.e., C₃s), to obtain the correctness, and our results refutes FPT algorithm for Bipartite Token Jumping, where the input graph cannot have any triangles. For an integer k ∈ ℕ, the half graph S_{k,k} is the graph with vertex set V(S_{k,k}) = A_k ∪ B_k, where A_k = {a₁,a₂,⋯, a_k} and B_k = {b₁,b₂,⋯, b_k}, and for i,j ∈ [k], {a_i,b_j} ∈ E(T_{k,k}) if and only if j ≥ i. We also study the Half (Induced-)Subgraph problem where we are given a graph G and an integer k, and the goal is to check if G contains S_{k,k} as an (induced-)subgraph. Again under Gap-ETH, we show that Half (Induced-)Subgraph does not admit an FPT algorithm, even when the input is a bipartite graph. We believe that the above problem (and its negative) result maybe of independent interest and could be useful obtaining new fixed parameter intractability results. There are very few reductions known in the literature which refute FPT algorithms for a parameterized problem based on assumptions like Gap-ETH. Thus our technique (and simple reductions) exhibits the potential of such conjectures in obtaining new (and possibly easier) proofs for refuting FPT algorithms for parameterized problems.

Cite as

Akanksha Agrawal, Ravi Kiran Allumalla, and Varun Teja Dhanekula. Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2021.2,
  author =	{Agrawal, Akanksha and Allumalla, Ravi Kiran and Dhanekula, Varun Teja},
  title =	{{Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.2},
  URN =		{urn:nbn:de:0030-drops-153851},
  doi =		{10.4230/LIPIcs.IPEC.2021.2},
  annote =	{Keywords: Token Jumping, Bipartite Graphs, Fixed Parameter Intractability, Half Graphs, Gap-Exponential Time Hypothesis}
}
Document
An FPT Algorithm for Elimination Distance to Bounded Degree Graphs

Authors: Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. [MFCS 2020] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K₅-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

Cite as

Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. An FPT Algorithm for Elimination Distance to Bounded Degree Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 5:1-5:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2021.5,
  author =	{Agrawal, Akanksha and Kanesh, Lawqueen and Panolan, Fahad and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{An FPT Algorithm for Elimination Distance to Bounded Degree Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{5:1--5:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.5},
  URN =		{urn:nbn:de:0030-drops-136507},
  doi =		{10.4230/LIPIcs.STACS.2021.5},
  annote =	{Keywords: Elimination Distance, Fixed-parameter Tractability, Graph Modification}
}
Document
On the Parameterized Complexity of Clique Elimination Distance

Authors: Akanksha Agrawal and M. S. Ramanujan

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance in an effort to define new tractable parameterizations for graph problems and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. In this paper, we consider the problem of computing the elimination distance of a given graph to the class of cluster graphs and initiate the study of the parameterized complexity of a more general version - that of obtaining a modulator to such graphs. That is, we study the (η,Clq)-Elimination Deletion problem ((η,Clq)-ED Deletion) where, for a fixed η, one is given a graph G and k ∈ ℕ and the objective is to determine whether there is a set S ⊆ V(G) such that the graph G-S has elimination distance at most η to the class of cluster graphs. Our main result is a polynomial kernelization (parameterized by k) for this problem. As components in the proof of our main result, we develop a k^𝒪(η k + η²)n^𝒪(1)-time fixed-parameter algorithm for (η,Clq)-ED Deletion and a polynomial-time factor-min{𝒪(η⋅ opt⋅ log² n),opt^𝒪(1)} approximation algorithm for the same problem.

Cite as

Akanksha Agrawal and M. S. Ramanujan. On the Parameterized Complexity of Clique Elimination Distance. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.IPEC.2020.1,
  author =	{Agrawal, Akanksha and Ramanujan, M. S.},
  title =	{{On the Parameterized Complexity of Clique Elimination Distance}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{1:1--1:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.1},
  URN =		{urn:nbn:de:0030-drops-133043},
  doi =		{10.4230/LIPIcs.IPEC.2020.1},
  annote =	{Keywords: Elimination Distance, Cluster Graphs, Kernelization}
}
Document
Parameter Analysis for Guarding Terrains

Authors: Akanksha Agrawal, Sudeshna Kolay, and Meirav Zehavi

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)


Abstract
The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm.

Cite as

Akanksha Agrawal, Sudeshna Kolay, and Meirav Zehavi. Parameter Analysis for Guarding Terrains. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SWAT.2020.4,
  author =	{Agrawal, Akanksha and Kolay, Sudeshna and Zehavi, Meirav},
  title =	{{Parameter Analysis for Guarding Terrains}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.4},
  URN =		{urn:nbn:de:0030-drops-122514},
  doi =		{10.4230/LIPIcs.SWAT.2020.4},
  annote =	{Keywords: Terrain Guarding, Reflex Vertices, Terrain Minima, FPT Algorithm, XP Algorithm, Kernelization}
}
Document
The Parameterized Complexity of Guarding Almost Convex Polygons

Authors: Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ℝ-complete [Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time r^O(r²)n^O(1). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.

Cite as

Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.SoCG.2020.3,
  author =	{Agrawal, Akanksha and Knudsen, Kristine V. K. and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{The Parameterized Complexity of Guarding Almost Convex Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.3},
  URN =		{urn:nbn:de:0030-drops-121614},
  doi =		{10.4230/LIPIcs.SoCG.2020.3},
  annote =	{Keywords: Art Gallery, Reflex vertices, Monotone 2-CSP, Parameterized Complexity, Fixed Parameter Tractability}
}
Document
Parameterized Streaming Algorithms for Min-Ones d-SAT

Authors: Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)


Abstract
In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).

Cite as

Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2019.8,
  author =	{Agrawal, Akanksha and Biswas, Arindam and Bonnet, \'{E}douard and Brettell, Nick and Curticapean, Radu and Marx, D\'{a}niel and Miltzow, Tillmann and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Parameterized Streaming Algorithms for Min-Ones d-SAT}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.8},
  URN =		{urn:nbn:de:0030-drops-115708},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.8},
  annote =	{Keywords: min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter}
}
Document
Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices

Authors: Akanksha Agrawal, Sudeshna Kolay, Jayakrishnan Madathil, and Saket Saurabh

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, say, V_1, V_2, ..., V_l such that for each i,j in {1,2,...,l}, (i) if m_{i,j}=0 then for any u in V_i and v in V_j, uv not in E(G), (ii) if m_{i,j}=1 then for any (distinct) u in V_i and v in V_j, uv in E(G), (iii) for each v in V(G), if v in V_i then i in L(v). We consider the Deletion to List M-Partition problem that takes as input a graph G, a list function L:V(G) - > 2^[l] and a positive integer k. The aim is to determine whether there is a k-sized set S subseteq V(G) such that G-S has a list M-partition. Many important problems like Vertex Cover, Odd Cycle Transversal, Split Vertex Deletion, Multiway Cut and Deletion to List Homomorphism are special cases of the Deletion to List M-Partition problem. In this paper, we provide a classification of the parameterized complexity of Deletion to List M-Partition, parameterized by k, (a) when M is of order at most 3, and (b) when M is of order 4 with all diagonal entries belonging to {0,1}.

Cite as

Akanksha Agrawal, Sudeshna Kolay, Jayakrishnan Madathil, and Saket Saurabh. Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2019.41,
  author =	{Agrawal, Akanksha and Kolay, Sudeshna and Madathil, Jayakrishnan and Saurabh, Saket},
  title =	{{Parameterized Complexity Classification of Deletion to List Matrix-Partition for Low-Order Matrices}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.41},
  URN =		{urn:nbn:de:0030-drops-115372},
  doi =		{10.4230/LIPIcs.ISAAC.2019.41},
  annote =	{Keywords: list matrix partitions, parameterized classification, Almost 2-SAT, important separators, iterative compression}
}
Document
Parameterized Complexity of Conflict-Free Matchings and Paths

Authors: Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh

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


Abstract
An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) is a solution to I in Gamma, which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Matching (CF-Matching) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-Matching and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-Matching holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-Matching when the conflict graph is chordal. Also, we give FPT algorithms for both CF-Matching and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-Matching and CF-SP, where the conflicting conditions are given by a (representable) matroid.

Cite as

Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2019.35,
  author =	{Agrawal, Akanksha and Jain, Pallavi and Kanesh, Lawqueen and Saurabh, Saket},
  title =	{{Parameterized Complexity of Conflict-Free Matchings and Paths}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{35:1--35:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.35},
  URN =		{urn:nbn:de:0030-drops-109798},
  doi =		{10.4230/LIPIcs.MFCS.2019.35},
  annote =	{Keywords: Conflict-free, Matching, Shortest Path, FPT algorithm, W\lbrack1\rbrack-hard, Matroid}
}
  • Refine by Author
  • 30 Agrawal, Akanksha
  • 20 Saurabh, Saket
  • 9 Lokshtanov, Daniel
  • 9 Zehavi, Meirav
  • 4 Kanesh, Lawqueen
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Fixed parameter tractability
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 5 Parameterized Complexity
  • 5 parameterized complexity
  • 4 Kernelization
  • 3 FPT algorithm
  • 3 kernelization
  • Show More...

  • Refine by Type
  • 30 document

  • Refine by Publication Year
  • 6 2019
  • 5 2018
  • 4 2016
  • 3 2017
  • 3 2020
  • Show More...

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