9 citations · 13 across the 16 of their papers we have counts for
19 papers
Algorithms and complexity for geodetic sets on interval and chordal graphs
Dibyayan Chakraborty, Sandip Das, Florent Foucaud +2
We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set of vertices of a graph is a \textit{geodetic se…
Hardness and Approximation for Coloring Digraphs
Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer +2
The dichromatic number of a digraph is the minimum number such that can be partitioned into subsets, each inducing an acyclic digraph. The acyclic number…
Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences
Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos +1
Hedonic games are an archetypal problem in coalition formation, where a set of selfish agents want to partition themselves into stable coalitions. In this work, we focus on two nat…
The Parameterized Complexity of Computing the VC-Dimension
Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney +1
The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new re…
Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos
Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario i…
Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
Harmender Gahlawat, Meirav Zehavi
Decision trees are a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct ``small'' decision trees, by minimizing…
Pushing Cops and Robber on Graphs of Maximum Degree 4
Harmender Gahlawat
\textsc{Cops and Robber} is a game played on graphs where a set of \textit{cops} aim to \textit{capture} the position of a single \textit{robber}. The main parameter of interest in…
(Almost-)Optimal FPT Algorithm and Kernel for -Cycle on Planar Graphs
Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi
Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, \textsc{-Cycle}: given an und…
Hunting a rabbit: complexity, approximability and some characterizations
Walid Ben-Ameur, Harmender Gahlawat, Alessandro Maddaloni
In the Hunters and Rabbit game, hunters attempt to shoot an invisible rabbit on a given graph . In each round, the hunters select vertices to shoot at, while the rabbit…
Coarse cops and robber in graphs and groups
Louis Esperet, Harmender Gahlawat, Ugo Giocanti
(abstract shortened to meet arxiv's length requirements) We investigate two variants of the classical Cops and robber game in graphs, recently introduced by Lee, Martínez-Pedroza,…
The Closed Geodetic Game: algorithms and strategies
Antoine Dailly, Harmender Gahlawat, Zin Mar Myint
The geodetic closure of a set S of vertices of a graph is the set of all vertices in shortest paths between pairs of vertices of S. A set S of vertices in a graph is geodetic if it…
On the Cop Number of String Graphs
Sandip Das, Harmender Gahlawat
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 \emph{cop number} of a graph is the mini…
Parameterized Complexity of Incomplete Connected Fair Division
Harmender Gahlawat, Meirav Zehavi
\textit{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 vari…
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs
Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk +1
Given an undirected graph and a multiset of terminal pairs , the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether has p…
Further results on the Hunters and Rabbit game through monotonicity
Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat +1
Hunters and Rabbit game is played on a graph where the Hunter player shoots at vertices in every round while the Rabbit player occupies an unknown vertex and, if not shot,…
Parameterized Analysis of the Cops and Robber Problem
Harmender Gahlawat, Meirav Zehavi
\textit{Pursuit-evasion games} have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theo…
Cops and robber on variants of retracts and subdivisions of oriented graphs
Harmender Gahlawat, Zin Mar Myint, Sagnik Sen
\textsc{Cops and Robber} is one of the most studied two-player pursuit-evasion games played on graphs, where multiple \textit{cops}, controlled by one player, pursue a single \text…
Algorithms and complexity for geodetic sets on planar and chordal graphs
Dibyayan Chakraborty, Harmender Gahlawat, Bodhayan Roy
A set of vertices of a graph is a \emph{geodetic set} if every vertex of lies in a shortest path between some pair of vertices of . The \textsc{Minimum Geodetic Set…
Hardness and approximation for the geodetic set problem in some graph classes
Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat +2
In this paper, we study the computational complexity of finding the \emph{geodetic number} of graphs. A set of vertices of a graph is a \emph{geodetic set} if any vertex of…