9 citations · 13 across the 16 of their papers we have counts for
7 papers · 1 filter
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,…