14 Search Results for "Gahlawat, Harmender"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.53
Hardness and Approximation for Coloring Digraphs

Authors: Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, and Chaoliang Tang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The dichromatic number χ(D) of a digraph is the minimum number k such that V(D) can be partitioned into k subsets, each inducing an acyclic digraph. The acyclic number α(D) is the cardinality of a largest induced acyclic subdigraph of D. We study these problems from an approximation point of view. We begin with establishing that even when restricted to tournaments, approximating χ and α remain as challenging as their undirected counterparts on general graphs. Specifically, we establish that for every ε > 0, it is hard to approximate both α and χ up to a factor of n^{1-ε} even when restricted to tournaments. We next consider approximate coloring of digraphs in special cases. We begin with establishing that we can color 𝓁-dicolorable digraphs using at most 𝓁 ⋅ n^{1-1/(𝓁)} colors in time O(n^{2𝓁}); in particular, we can color 2-dicolorable digraphs with 2√n colors in polynomial time. We then focus on bounding the dichromatic number of dense digraphs as a function of the independence number α of the underlying graph. We consider two special cases in this regard: digraphs with χ(D) ≤ 2 and digraphs that do not contain any directed triangle. For these cases, we present algorithms which generalize and improve existing tools and results.
Cite as

Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, and Chaoliang Tang. Hardness and Approximation for Coloring Digraphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2026.53,
  author =	{Chalermsook, Parinya and Gahlawat, Harmender and Klingelhoefer, Felix and Newman, Alantha and Tang, Chaoliang},
  title =	{{Hardness and Approximation for Coloring Digraphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{53:1--53:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.53},
  URN =		{urn:nbn:de:0030-drops-264421},
  doi =		{10.4230/LIPIcs.ICALP.2026.53},
  annote =	{Keywords: Graph Algorithms, Hardness of Approximation, Polynomial Time Approximation Algorithms, Structural Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.4
The Closed Hull Game and the Closed Interval Game

Authors: Samuel N. Araújo, Fabrício Benevides, Nicolas Martins, Nicolas Nisse, and Rudini Sampaio

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Given a set S of vertices in a graph G, its geodesic interval is the set I(S) containing S and all vertices on a shortest path between vertices of S. A set S is convex if I(S) = S. Moreover, the convex hull ℋ(S) of S is the smallest convex set containing S. In 1984, Harary introduced convexity games where two players, Alice and Bob, alternately select vertices of a graph G = (V,E) such that, if the set of already selected vertices is S, the next player can only select a vertex in V ⧵ I(S) (closed interval game) or in V ⧵ ℋ(S) (closed hull game). Normal and misère versions of these games have been studied and here, we introduced the optimization variants of them. Formally, given a graph G and k ∈ ℕ, Alice wins if the game ends after at most k vertices have been selected and Bob wins otherwise. The corresponding problem consists of determining which player has a winning strategy. We prove that the closed interval optimization game is PSPACE-complete in graphs with diameter 4 and that the closed hull optimization game is NP-hard in bipartite graphs and in split graphs. On the positive side, we prove that both games can be solved in polynomial time in trees and that the closed hull optimization game can be solved in polynomial time in cobipartite graphs. We conjecture that the closed interval optimization game is NP-hard in cobipartite graphs and that the closed hull optimization game is PSPACE-complete in general graphs.
Cite as

Samuel N. Araújo, Fabrício Benevides, Nicolas Martins, Nicolas Nisse, and Rudini Sampaio. The Closed Hull Game and the Closed Interval Game. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.FUN.2026.4,
  author =	{Ara\'{u}jo, Samuel N. and Benevides, Fabr{\'\i}cio and Martins, Nicolas and Nisse, Nicolas and Sampaio, Rudini},
  title =	{{The Closed Hull Game and the Closed Interval Game}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.4},
  URN =		{urn:nbn:de:0030-drops-257232},
  doi =		{10.4230/LIPIcs.FUN.2026.4},
  annote =	{Keywords: Combinatorial games in graphs, graph convexity, PSPACE}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.10
A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths

Authors: Julien Baste, Lucas De Meyer, Ugo Giocanti, Etienne Objois, and Timothé Picavet

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Dumas, Foucaud, Perez and Todinca [SIAM J. Disc. Math., 2024] recently proved that every graph whose edge set can be covered by k shortest paths has pathwidth at most 3^k. In this paper, we improve this upper bound on the pathwidth to a polynomial bound; namely, we show that every graph whose edge set can be covered by k shortest paths has pathwidth O(k⁴), answering a question from the same paper. Moreover, we also prove that when k ≤ 3, every such graph has pathwidth at most k (and this bound is tight). Eventually, we show that even though there exist graphs with arbitrary large treewidth whose vertex set can be covered by 2 isometric trees, every graph whose set of edges can be covered by 2 isometric trees has treewidth at most 2.
Cite as

Julien Baste, Lucas De Meyer, Ugo Giocanti, Etienne Objois, and Timothé Picavet. A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baste_et_al:LIPIcs.STACS.2026.10,
  author =	{Baste, Julien and De Meyer, Lucas and Giocanti, Ugo and Objois, Etienne and Picavet, Timoth\'{e}},
  title =	{{A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.10},
  URN =		{urn:nbn:de:0030-drops-254999},
  doi =		{10.4230/LIPIcs.STACS.2026.10},
  annote =	{Keywords: Structural Graph Theory, Coverings, Metrics, Pathwidth, Treewdidth, Parameterized Algorithms, Layerings}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.3
Parameterized Maximum Node-Disjoint Paths

Authors: Michael Lampis and Manolis Vasilakis

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of the famous Node-Disjoint Paths problem, where we are given an undirected graph G, k (demand) pairs of vertices (s_i, t_i), and an integer 𝓁, and are asked whether there exist at least 𝓁 vertex-disjoint paths in G whose endpoints are given pairs. This problem has been intensely studied from both the approximation and parameterized complexity point of view and is notably known to be intractable by standard structural parameters, such as tree-depth, as well as the combined parameter 𝓁 plus pathwidth. We present several results improving and clarifying this state of the art, with an emphasis towards FPT approximation. Our main positive contribution is to show that the problem’s intractability can be overcome using approximation: We show that for several of the structural parameters for which the problem is hard, most notably tree-depth, the problem admits an efficient FPT approximation scheme, returning a (1-ε)-approximate solution in time f(td,ε)n^𝒪(1). We manage to obtain these results by comprehensively mapping out the structural parameters for which the problem is FPT if 𝓁 is also a parameter, hence showing that understanding 𝓁 as a parameter is key to the problem’s approximability. This, in turn, is a problem we are able to solve via a surprisingly simple color-coding algorithm, which relies on identifying an insightful problem-specific variant of the natural parameter, namely the number of vertices used in the solution. The results above are quite encouraging, as they indicate that in some situations where the problem does not admit an FPT algorithm, it is still solvable almost to optimality in FPT time. A natural question is whether the FPT approximation algorithm we devised for tree-depth can be extended to pathwidth. We resolve this negatively, showing that under the Parameterized Inapproximability Hypothesis no FPT approximation scheme for this parameter is possible, even in time f(pw,ε)n^g(ε). We thus precisely determine the parameter border where the problem transitions from "hard but approximable" to "inapproximable". Lastly, we strengthen existing lower bounds by replacing W[1]-hardness by XNLP-completeness for parameter pathwidth, and improving the n^o(√{td}) ETH-based lower bound for tree-depth to (the optimal) n^o(td).
Cite as

Michael Lampis and Manolis Vasilakis. Parameterized Maximum Node-Disjoint Paths. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.IPEC.2025.3,
  author =	{Lampis, Michael and Vasilakis, Manolis},
  title =	{{Parameterized Maximum Node-Disjoint Paths}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.3},
  URN =		{urn:nbn:de:0030-drops-251357},
  doi =		{10.4230/LIPIcs.IPEC.2025.3},
  annote =	{Keywords: ETH, Maximum Node-Disjoint Paths, Parameterized Complexity, PIH}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.29
Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division

Authors: Ajaykrishnan E S and Daniel Lokshtanov

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the problem of Envy-Free Incomplete Connected Fair Division, where exactly p vertices of an undirected graph must be allocated to agents such that each agent receives a connected share and does not envy another agent’s share. Focusing on agents with additive valuations, we show that the problem remains computationally hard when parameterized by p and the number of agents. This result holds even for star graphs and with the input numbers given in unary representation, thereby resolving an open problem posed by Gahlawat and Zehavi (FSTTCS 2023). In stark contrast, we show that if one is willing to tolerate even the slightest amount of envy, then the problem becomes efficient with respect to the natural parameters. Specifically, we design an Efficient Parameterized Approximation Scheme parameterized by p and the number of agent types. Our algorithm works on general graphs and remains efficient even when the input numbers are provided in binary representation.
Cite as

Ajaykrishnan E S and Daniel Lokshtanov. Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{es_et_al:LIPIcs.FSTTCS.2025.29,
  author =	{E S, Ajaykrishnan and Lokshtanov, Daniel},
  title =	{{Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.29},
  URN =		{urn:nbn:de:0030-drops-251101},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.29},
  annote =	{Keywords: Envy-Free Incomplete Connected Fair Division, Efficient Parameterized Approximation Scheme, W\lbrack1\rbrack-hardness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.82
(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs

Authors: Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, T-Cycle: given an undirected n-vertex graph G and a set of k vertices T ⊆ V(G) termed terminals, the objective is to determine whether G contains a simple cycle C through all the terminals. Our contribution is twofold: (i) We provide a 2^{O(√klog k)}⋅ n-time fixed-parameter deterministic algorithm for T-Cycle on planar graphs; (ii) We provide a k^{O(1)}⋅ n-time deterministic kernelization algorithm for T-Cycle on planar graphs where the produced instance is of size klog^{O(1)}k. Both of our algorithms are optimal in terms of both k and n up to (poly)logarithmic factors in k under the ETH. In fact, our algorithms are the first subexponential-time fixed-parameter algorithm for T-Cycle on planar graphs, as well as the first polynomial kernel for T-Cycle on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem.
Cite as

Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi. (Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.ICALP.2025.82,
  author =	{Gahlawat, Harmender and Rathod, Abhishek and Zehavi, Meirav},
  title =	{{(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{82:1--82:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.82},
  URN =		{urn:nbn:de:0030-drops-234593},
  doi =		{10.4230/LIPIcs.ICALP.2025.82},
  annote =	{Keywords: FPT Algorithms, Kernelization, T-Cycle, Subexponential Algorithmms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.54
Romeo and Juliet Is EXPTIME-Complete

Authors: Harmender Gahlawat, Jan Matyáš Křišťan, and Tomáš Valla

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Romeo and Juliet is a two player Rendezvous game played on graphs where one player controls two agents, Romeo (ℛ) and Juliet (𝒥) who aim to meet at a vertex against k adversaries, called dividers, controlled by the other player. The optimization in this game lies at deciding the minimum number of dividers sufficient to restrict ℛ and 𝒥 from meeting in a graph, called the dynamic separation number. We establish that Romeo and Juliet is EXPTIME-complete, settling a conjecture of Fomin, Golovach, and Thilikos [Inf. and Comp., 2023] positively. We also consider the game for directed graphs and establish that although the game is EXPTIME-complete for general directed graphs, it is PSPACE-complete and co-W[2]-hard for directed acyclic graphs.
Cite as

Harmender Gahlawat, Jan Matyáš Křišťan, and Tomáš Valla. Romeo and Juliet Is EXPTIME-Complete. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.MFCS.2024.54,
  author =	{Gahlawat, Harmender and K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Valla, Tom\'{a}\v{s}},
  title =	{{Romeo and Juliet Is EXPTIME-Complete}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.54},
  URN =		{urn:nbn:de:0030-drops-206106},
  doi =		{10.4230/LIPIcs.MFCS.2024.54},
  annote =	{Keywords: Rendezvous Games on graphs, EXPTIME-completeness, Dynamic Separators}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.10
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs

Authors: Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, and Meirav Zehavi

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Given an undirected graph G and a multiset of k terminal pairs 𝒳, the Vertex-Disjoint Paths (VDP) and Edge-Disjoint Paths (EDP) problems ask whether G has k pairwise internally vertex-disjoint paths and k pairwise edge-disjoint paths, respectively, connecting every terminal pair in 𝒳. In this paper, we study the kernelization complexity of VDP and EDP on subclasses of chordal graphs. For VDP, we design a 4k vertex kernel on split graphs and an 𝒪(k²) vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For EDP, we first prove that the problem is NP-complete on complete graphs. Then, we design an 𝒪(k^{2.75}) vertex kernel for EDP on split graphs, and improve it to a 7k+1 vertex kernel on threshold graphs. Lastly, we provide an 𝒪(k²) vertex kernel for EDP on block graphs and a 2k+1 vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al. [Theory Comput. Syst., 2015].
Cite as

Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, and Meirav Zehavi. Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chaudhary_et_al:LIPIcs.IPEC.2023.10,
  author =	{Chaudhary, Juhi and Gahlawat, Harmender and W{\l}odarczyk, Michal and Zehavi, Meirav},
  title =	{{Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.10},
  URN =		{urn:nbn:de:0030-drops-194296},
  doi =		{10.4230/LIPIcs.IPEC.2023.10},
  annote =	{Keywords: Kernelization, Parameterized Complexity, Vertex-Disjoint Paths Problem, Edge-Disjoint Paths Problem}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.14
Parameterized Complexity of Incomplete Connected Fair Division

Authors: Harmender Gahlawat and Meirav Zehavi

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

Abstract
Fair division of resources among competing agents is a fundamental problem in computational social choice and economic game theory. It has been intensively studied on various kinds of items (divisible and indivisible) and under various notions of fairness. We focus on Connected Fair Division (CFD), the variant of fair division on graphs, where the resources are modeled as an item graph. Here, each agent has to be assigned a connected subgraph of the item graph, and each item has to be assigned to some agent. We introduce a generalization of CFD, termed Incomplete CFD (ICFD), where exactly p vertices of the item graph should be assigned to the agents. This might be useful, in particular when the allocations are intended to be "economical" as well as fair. We consider four well-known notions of fairness: PROP, EF, EF1, EFX. First, we prove that EF-ICFD, EF1-ICFD, and EFX-ICFD are W[1]-hard parameterized by p plus the number of agents, even for graphs having constant vertex cover number (vcn). In contrast, we present a randomized FPT algorithm for PROP-ICFD parameterized only by p. Additionally, we prove both positive and negative results concerning the kernelization complexity of ICFD under all four fairness notions, parameterized by p, vcn, and the total number of different valuations in the item graph (val).
Cite as

Harmender Gahlawat and Meirav Zehavi. Parameterized Complexity of Incomplete Connected Fair Division. 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. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.FSTTCS.2023.14,
  author =	{Gahlawat, Harmender and Zehavi, Meirav},
  title =	{{Parameterized Complexity of Incomplete Connected Fair Division}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{14:1--14:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.14},
  URN =		{urn:nbn:de:0030-drops-193877},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.14},
  annote =	{Keywords: Fair Division, Kernelization, Connected Fair Allocation, Fixed parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.42
Recontamination Helps a Lot to Hunt a Rabbit

Authors: Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat, and Nicolas Nisse

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise. The hunter number h(G) of a graph G is the minimum integer k such that the Hunter player has a winning strategy (i.e., allowing him to win whatever be the strategy of the Rabbit player). This game has been studied in several graph classes, in particular in bipartite graphs (grids, trees, hypercubes...), but the computational complexity of computing h(G) remains open in general graphs and even in more restricted graph classes such as trees. To progress further in this study, we propose a notion of monotonicity (a well-studied and useful property in classical pursuit-evasion games such as Graph Searching games) for the Hunters and Rabbit game imposing that, roughly, a vertex that has already been shot "must not host the rabbit anymore". This allows us to obtain new results in various graph classes. More precisely, let the monotone hunter number mh(G) of a graph G be the minimum integer k such that the Hunter player has a monotone winning strategy. We show that pw(G) ≤ mh(G) ≤ pw(G)+1 for any graph G with pathwidth pw(G), which implies that computing mh(G), or even approximating mh(G) up to an additive constant, is NP-hard. Then, we show that mh(G) can be computed in polynomial time in split graphs, interval graphs, cographs and trees. These results go through structural characterisations which allow us to relate the monotone hunter number with the pathwidth in some of these graph classes. In all cases, this allows us to specify the hunter number or to show that there may be an arbitrary gap between h and mh, i.e., that monotonicity does not help. In particular, we show that, for every k ≥ 3, there exists a tree T with h(T) = 2 and mh(T) = k. We conclude by proving that computing h (resp., mh) is FPT parameterised by the minimum size of a vertex cover.
Cite as

Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat, and Nicolas Nisse. Recontamination Helps a Lot to Hunt a Rabbit. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dissaux_et_al:LIPIcs.MFCS.2023.42,
  author =	{Dissaux, Thomas and Fioravantes, Foivos and Gahlawat, Harmender and Nisse, Nicolas},
  title =	{{Recontamination Helps a Lot to Hunt a Rabbit}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.42},
  URN =		{urn:nbn:de:0030-drops-185763},
  doi =		{10.4230/LIPIcs.MFCS.2023.42},
  annote =	{Keywords: Hunter and Rabbit, Monotonicity, Graph Searching}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.49
Parameterized Analysis of the Cops and Robber Game

Authors: Harmender Gahlawat and Meirav Zehavi

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Pursuit-evasion games have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theory, distributed computing, and algorithmic theory. Cops and Robber (CnR) is one of the most well-known pursuit-evasion games played on graphs, where multiple cops pursue a single robber. The aim is to compute the cop number of a graph, k, which is the minimum number of cops that ensures the capture of the robber. From the viewpoint of parameterized complexity, CnR is W[2]-hard parameterized by k [Fomin et al., TCS, 2010]. Thus, we study structural parameters of the input graph. We begin with the vertex cover number (vcn). First, we establish that k ≤ vcn/3+1. Second, we prove that CnR parameterized by vcn is FPT by designing an exponential kernel. We complement this result by showing that it is unlikely for CnR parameterized by vcn to admit a polynomial compression. We extend our exponential kernels to the parameters cluster vertex deletion number and deletion to stars number, and design a linear vertex kernel for neighborhood diversity. Additionally, we extend all of our results to several well-studied variations of CnR.
Cite as

Harmender Gahlawat and Meirav Zehavi. Parameterized Analysis of the Cops and Robber Game. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 49:1-49:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.MFCS.2023.49,
  author =	{Gahlawat, Harmender and Zehavi, Meirav},
  title =	{{Parameterized Analysis of the Cops and Robber Game}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{49:1--49:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.49},
  URN =		{urn:nbn:de:0030-drops-185837},
  doi =		{10.4230/LIPIcs.MFCS.2023.49},
  annote =	{Keywords: Cops and Robber, Kernelization, Graph Searching, Fixed parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.12
Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond

Authors: Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh

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

Abstract
A path is isometric if it is a shortest path between its endpoints. In this article, we consider the graph covering problem Isometric Path Cover, where we want to cover all the vertices of the graph using a minimum-size set of isometric paths. Although this problem has been considered from a structural point of view (in particular, regarding applications to pursuit-evasion games), it is little studied from the algorithmic perspective. We consider Isometric Path Cover on chordal graphs, and show that the problem is NP-hard for this class. On the positive side, for chordal graphs, we design a 4-approximation algorithm and an FPT algorithm for the parameter solution size. The approximation algorithm is based on a reduction to the classic path covering problem on a suitable directed acyclic graph obtained from a breadth first search traversal of the graph. The approximation ratio of our algorithm is 3 for interval graphs and 2 for proper interval graphs. Moreover, we extend the analysis of our approximation algorithm to k-chordal graphs (graphs whose induced cycles have length at most k) by showing that it has an approximation ratio of k+7 for such graphs, and to graphs of treelength at most 𝓁, where the approximation ratio is at most 6𝓁+2.
Cite as

Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh. Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2022.12,
  author =	{Chakraborty, Dibyayan and Dailly, Antoine and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Ghosh, Subir Kumar},
  title =	{{Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{12:1--12:17},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.12},
  URN =		{urn:nbn:de:0030-drops-172974},
  doi =		{10.4230/LIPIcs.ISAAC.2022.12},
  annote =	{Keywords: Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.45
On the Cop Number of String Graphs

Authors: Sandip Das and Harmender Gahlawat

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

Abstract
Cops and Robber is a well-studied two-player pursuit-evasion game played on a graph, where a group of cops tries to capture the robber. The cop number of a graph is the minimum number of cops required to capture the robber. We show that the cop number of a string graph is at most 13, improving upon a result of Gavenčiak et al. [Eur. J. of Comb. 72, 45-69 (2018)]. Using similar techniques, we also show that four cops have a winning strategy for a variant of Cops and Robber, named Fully Active Cops and Robber, on planar graphs, addressing an open question of Gromovikov et al. [Austr. J. Comb. 76(2), 248-265 (2020)].
Cite as

Sandip Das and Harmender Gahlawat. On the Cop Number of String Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2022.45,
  author =	{Das, Sandip and Gahlawat, Harmender},
  title =	{{On the Cop Number of String Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{45:1--45:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.45},
  URN =		{urn:nbn:de:0030-drops-173308},
  doi =		{10.4230/LIPIcs.ISAAC.2022.45},
  annote =	{Keywords: Cop number, string graphs, intersection graphs, planar graphs, pursuit-evasion games}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.7
Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs

Authors: Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study the complexity of finding the geodetic number on subclasses of planar graphs and chordal graphs. A set S of vertices of a graph G is a geodetic set if every vertex of G lies in a shortest path between some pair of vertices of S. The Minimum Geodetic Set (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NP-hard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study MGS on restricted classes of planar graphs: we design a linear-time algorithm for MGS on solid grids, improving on a 3-approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that MGS remains NP-hard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that MGS is fixed parameter tractable for inputs of this class when parameterized by their treewidth (which equals the clique number minus one). This implies a linear-time algorithm for k-trees, for fixed k. Then, we show that MGS is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.
Cite as

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy. Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2020.7,
  author =	{Chakraborty, Dibyayan and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Lajou, Dimitri and Roy, Bodhayan},
  title =	{{Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.7},
  URN =		{urn:nbn:de:0030-drops-133516},
  doi =		{10.4230/LIPIcs.ISAAC.2020.7},
  annote =	{Keywords: Geodetic set, Planar graph, Chordal graph, Interval graph, FPT algorithm}
}
  • Refine by Type
  • 14 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 3 2025
  • 1 2024
  • 4 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 10 Gahlawat, Harmender
  • 4 Zehavi, Meirav
  • 3 Das, Sandip
  • 2 Chakraborty, Dibyayan
  • 2 Foucaud, Florent
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 8 Mathematics of computing → Graph algorithms
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 4 Kernelization
  • 2 Chordal graph
  • 2 FPT algorithm
  • 2 Fixed parameter tractability
  • 2 Graph Searching
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact