Search Results

Documents authored by Verma, Shaily

Document
DOI: 10.4230/LIPIcs.ESA.2025.10
Connected Partitions via Connected Dominating Sets

Authors: Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, and Ziena Zeif

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The classical theorem due to Győri and Lovász states that any k-connected graph G admits a partition into k connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of G. However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for k = 5. We make progress towards an efficient constructive version of the Győri-Lovász theorem by considering a natural strengthening of the k-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if G contains k disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Győri-Lovász theorem: - On general graphs, a Győri-Lovász partition with k parts can be computed in polynomial time when the input graph has connectivity Ω(k ⋅ log² n); - On convex bipartite graphs, connectivity of 4k is sufficient; - On biconvex graphs and interval graphs, connectivity of k is sufficient, meaning that our algorithm gives a "true" constructive version of the theorem on these graph classes.
Cite as

Aikaterini Niklanovits, Kirill Simonov, Shaily Verma, and Ziena Zeif. Connected Partitions via Connected Dominating Sets. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{niklanovits_et_al:LIPIcs.ESA.2025.10,
  author =	{Niklanovits, Aikaterini and Simonov, Kirill and Verma, Shaily and Zeif, Ziena},
  title =	{{Connected Partitions via Connected Dominating Sets}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.10},
  URN =		{urn:nbn:de:0030-drops-244785},
  doi =		{10.4230/LIPIcs.ESA.2025.10},
  annote =	{Keywords: Gy\H{o}ri-Lov\'{a}sz theorem, connected dominating sets, graph classes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.5
Parameterized Saga of First-Fit and Last-Fit Coloring

Authors: Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Shaily Verma

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The classic greedy coloring algorithm considers the vertices of an input graph G in a given order and assigns the first available color to each vertex v in G. In the Grundy Coloring problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the Partial Grundy Coloring, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex v is a color previously used for another vertex if such a color is available. Whether Grundy Coloring and Partial Grundy Coloring admit fixed-parameter tractable (FPT) algorithms, algorithms with running time f(k)n^O(1), where k is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for Grundy Coloring in the negative by showing that the problem is W[1]-hard. For Partial Grundy Coloring, they obtain an FPT algorithm on graphs that do not contain K_{i,j} as a subgraph (a.k.a. K_{i,j}-free graphs). Aboulker et al. re-iterate the question of whether there exists an FPT algorithm for Partial Grundy Coloring on general graphs and also asks whether Grundy Coloring admits an FPT algorithm on K_{i,j}-free graphs. We give FPT algorithms for Partial Grundy Coloring on general graphs and for Grundy Coloring on K_{i,j}-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and "representative-family" like sets for K_{i,j}-free graphs that we use in obtaining our results may have wider algorithmic applications.
Cite as

Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Shaily Verma. Parameterized Saga of First-Fit and Last-Fit Coloring. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.STACS.2025.5,
  author =	{Agrawal, Akanksha and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Verma, Shaily},
  title =	{{Parameterized Saga of First-Fit and Last-Fit Coloring}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.5},
  URN =		{urn:nbn:de:0030-drops-228304},
  doi =		{10.4230/LIPIcs.STACS.2025.5},
  annote =	{Keywords: Grundy Coloring, Partial Grundy Coloring, FPT Algorithm, K\underline\{i,j\}-free 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.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.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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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