6 Search Results for "Sahu, Abhishek"

Document
DOI: 10.4230/LIPIcs.IPEC.2022.2
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
DOI: 10.4230/LIPIcs.MFCS.2022.78
An Exact Algorithm for Knot-Free Vertex Deletion

Authors: M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, and Shaily Verma

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u,v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time 𝒪^⋆(1.576ⁿ), where n is the size of the vertex set in D.
Cite as

M. S. Ramanujan, Abhishek Sahu, Saket Saurabh, and Shaily Verma. An Exact Algorithm for Knot-Free Vertex Deletion. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ramanujan_et_al:LIPIcs.MFCS.2022.78,
  author =	{Ramanujan, M. S. and Sahu, Abhishek and Saurabh, Saket and Verma, Shaily},
  title =	{{An Exact Algorithm for Knot-Free Vertex Deletion}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{78:1--78:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.78},
  URN =		{urn:nbn:de:0030-drops-168769},
  doi =		{10.4230/LIPIcs.MFCS.2022.78},
  annote =	{Keywords: exact algorithm, knot-free graphs, branching algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.39
Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

Authors: Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c-1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by Fox et al. [ICALP `18 and SICOMP `20]. Koana et al. [ESA `20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k+c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable w.r.t. the parameter k+cl(G), whereas Partial Dominating Set, parameterized by k is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/poly.
Cite as

Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh. Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kanesh_et_al:LIPIcs.STACS.2022.39,
  author =	{Kanesh, Lawqueen and Madathil, Jayakrishnan and Roy, Sanjukta and Sahu, Abhishek and Saurabh, Saket},
  title =	{{Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{39:1--39:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra 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.2022.39},
  URN =		{urn:nbn:de:0030-drops-158494},
  doi =		{10.4230/LIPIcs.STACS.2022.39},
  annote =	{Keywords: c-closed graphs, domination problems, perfect code, connected dominating set, fixed-parameter tractable, polynomial kernel}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.23
A Polynomial Kernel for Bipartite Permutation Vertex Deletion

Authors: Lawqueen Kanesh, Jayakrishnan Madathil, Abhishek Sahu, Saket Saurabh, and Shaily Verma

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

Abstract
In a permutation graph, vertices represent the elements of a permutation, and edges represent pairs of elements that are reversed by the permutation. In the Permutation Vertex Deletion problem, given an undirected graph G and an integer k, the objective is to test whether there exists a vertex subset S ⊆ V(G) such that |S| ≤ k and G-S is a permutation graph. The parameterized complexity of Permutation Vertex Deletion is a well-known open problem. Bożyk et al. [IPEC 2020] initiated a study towards this problem by requiring that G-S be a bipartite permutation graph (a permutation graph that is bipartite). They called this the Bipartite Permutation Vertex Deletion (BPVD) problem. They showed that the problem admits a factor 9-approximation algorithm as well as a fixed parameter tractable (FPT) algorithm running in time 𝒪(9^k |V(G)|⁹). And they posed the question {whether BPVD admits a polynomial kernel.} We resolve this question in the affirmative by designing a polynomial kernel for BPVD. In particular, we obtain the following: Given an instance (G,k) of BPVD, in polynomial time we obtain an equivalent instance (G',k') of BPVD such that k' ≤ k, and |V(G')|+|E(G')| ≤ k^{𝒪(1)}.
Cite as

Lawqueen Kanesh, Jayakrishnan Madathil, Abhishek Sahu, Saket Saurabh, and Shaily Verma. A Polynomial Kernel for Bipartite Permutation Vertex Deletion. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kanesh_et_al:LIPIcs.IPEC.2021.23,
  author =	{Kanesh, Lawqueen and Madathil, Jayakrishnan and Sahu, Abhishek and Saurabh, Saket and Verma, Shaily},
  title =	{{A Polynomial Kernel for Bipartite Permutation Vertex Deletion}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{23:1--23:18},
  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.23},
  URN =		{urn:nbn:de:0030-drops-154065},
  doi =		{10.4230/LIPIcs.IPEC.2021.23},
  annote =	{Keywords: kernelization, bipartite permutation graph, bicliques}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.27
Packing Arc-Disjoint Cycles in Tournaments

Authors: Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi

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

Abstract
A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, they can be solved in 2^{O(k log k)} n^{O(1)} time and 2^{O(k)} n^{O(1)} time respectively. Moreover, they both admit a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2^{o(sqrt{k})} n^{O(1)} time under the Exponential-Time Hypothesis.
Cite as

Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi. Packing Arc-Disjoint Cycles in Tournaments. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.MFCS.2019.27,
  author =	{Bessy, St\'{e}phane and Bougeret, Marin and Krithika, R. and Sahu, Abhishek and Saurabh, Saket and Thiebaut, Jocelyn and Zehavi, Meirav},
  title =	{{Packing Arc-Disjoint Cycles in Tournaments}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{27:1--27: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.27},
  URN =		{urn:nbn:de:0030-drops-109714},
  doi =		{10.4230/LIPIcs.MFCS.2019.27},
  annote =	{Keywords: arc-disjoint cycle packing, tournaments, parameterized algorithms, kernelization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.19
Dynamic Parameterized Problems

Authors: R. Krithika, Abhishek Sahu, and Prafullkumar Tale

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
In this work, we study the parameterized complexity of various classical graph-theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties that are of interest to us. In real-world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size k of the symmetric difference of the edge sets of the two graphs (on n vertices) and the size r of the symmetric difference of the two solutions. We study the Dynamic Pi-Deletion problem which is the dynamic variant of the Pi-Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of Dynamic Pi-Deletion such as Dynamic Vertex Cover and Dynamic Feedback Vertex Set, we describe improved FPT algorithms and give linear kernels. Specifically, we show that Dynamic Vertex Cover admits algorithms with running times 1.1740^k*n^{O(1)} (polynomial space) and 1.1277^k*n^{O(1)} (exponential space). Then, we show that Dynamic Feedback Vertex Set admits a randomized algorithm with 1.6667^k*n^{O(1)} running time. Finally, we consider Dynamic Connected Vertex Cover, Dynamic Dominating Set and Dynamic Connected Dominating Set and describe algorithms with 2^k*n^{O(1)} running time improving over the known running time bounds for these problems. Additionally, for Dynamic Dominating Set and Dynamic Connected Dominating Set, we show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture.
Cite as

R. Krithika, Abhishek Sahu, and Prafullkumar Tale. Dynamic Parameterized Problems. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{krithika_et_al:LIPIcs.IPEC.2016.19,
  author =	{Krithika, R. and Sahu, Abhishek and Tale, Prafullkumar},
  title =	{{Dynamic Parameterized Problems}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.19},
  URN =		{urn:nbn:de:0030-drops-69366},
  doi =		{10.4230/LIPIcs.IPEC.2016.19},
  annote =	{Keywords: dynamic problems, fixed-parameter tractability, kernelization}
}
  • Refine by Author
  • 6 Sahu, Abhishek
  • 4 Saurabh, Saket
  • 2 Kanesh, Lawqueen
  • 2 Krithika, R.
  • 2 Madathil, Jayakrishnan
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Fixed parameter tractability
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 3 kernelization
  • 1 Apex-minor-free graphs
  • 1 Interval Graphs
  • 1 Parameterized Complexity
  • 1 Perfectly Matched Sets
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2022
  • 1 2017
  • 1 2019
  • 1 2021

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