9 citations · 20 across the 16 of their papers we have counts for
20 papers
Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
Sujoy Bhore, Liana Khazaliya, Fionn Mc Inerney
Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and proved that it is the most efficient batch machine teaching model satisfying the co…
Makespan Minimization in Split Learning: From Theory to Practice
Robert Ganian, Fionn Mc Inerney, Dimitra Tsigkari
Split learning recently emerged as a solution for distributed machine learning with heterogeneous IoT devices, where clients can offload part of their training to computationally-p…
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…
The Computational Complexity of Positive Non-Clashing Teaching in Graphs
Robert Ganian, Liana Khazaliya, Fionn Mc Inerney +1
We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per con…
Parameterized Complexity of Caching in Networks
Robert Ganian, Fionn Mc Inerney, Dimitra Tsigkari
The fundamental caching problem in networks asks to find an allocation of contents to a network of caches with the aim of maximizing the cache hit rate. Despite the problem's impor…
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
For a graph , a subset is called a resolving set of if, for any two vertices , there exists a vertex such that . T…
The Maker-Breaker Largest Connected Subgraph Game
Julien Bensmail, Foivos Fioravantes, Fionn Mc Inerney +2
Given a graph and , we introduce the following game played in . Each round, Alice colours an uncoloured vertex of red, and then Bob colours one blue (i…
A Structural Complexity Analysis of Hierarchical Task Network Planning
Cornelius Brand, Robert Ganian, Fionn Mc Inerney +1
We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network Planning: the verification of a provided plan, whether an…
The Complexity of Optimizing Atomic Congestion
Cornelius Brand, Robert Ganian, Subrahmanyam Kalyanasundaram +1
Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various a…
Non-Clashing Teaching Maps for Balls in Graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney +1
Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] introduced non-clashing teaching and showed it is the most efficient machine teaching model satisfying the Gol…
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets of non-negative…
Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
Valentin Bartier, Oscar Defrain, Fionn Mc Inerney
At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an -delay algorithm listing all minimal transversals of an -vertex…
Complexity of Maker-Breaker Games on Edge Sets of Graphs
Eric Duchêne, Valentin Gledel, Fionn Mc Inerney +4
We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the -game. Maker wins if s…
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
Jacob Focke, Dániel Marx, Fionn Mc Inerney +4
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets of non-negative integers, a -set o…
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Esther Galby, Liana Khazaliya, Fionn Mc Inerney +2
For a graph , a subset is called a \emph{resolving set} if for any two vertices , there exists a vertex such that …
Sample compression schemes for balls in graphs
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney +2
One of the open problems in machine learning is whether any set-family of VC-dimension admits a sample compression scheme of size . In this paper, we study this problem f…
The Game of Cops and Eternal Robbers
Anthony Bonato, Melissa Huggan, Trent Marbach +1
We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive int…
A method for eternally dominating strong grids
Alizée Gagnon, Alexander Hassler, Jerry Huang +5
In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to ad…
Hyperopic Cops and Robbers
A. Bonato, N. E. Clarke, D. Cox +3
We introduce a new variant of the game of Cops and Robbers played on graphs, where the robber is invisible unless outside the neighbor set of a cop. The hyperopic cop number is the…