Fionn Mc Inerney
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Fionn Mc Inerney has a total of 74 co-authors. Here are the top co-authors by number of shared publications:
Julien Bensmail
9 shared publicationsNicolas Nisse
9 shared publicationsStéphane Pérennes
6 shared publications- Anthony Bonato
Toronto Metropolitan University
3 shared publications Foivos Fioravantes
3 shared publications- Nicolas Nisse
Université Côte D’Azur, Inria, CNRS, I3S
3 shared publications
Latest Publications
- 4 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Domination and identification games in graphs
Jeux de domination et d’identification dans les graphes: Dans cette thèse, les jeux à 2 joueurs dans les graphes et leurs aspects algorithmiques et structurels sont étudiés. Nous explorons tout d'abord le jeu de domination éternelle ainsi que sa généralisation, le jeu de l'espion, deux jeux qui reposent sur les ensembles dominants dynamiques. Dans ces deux jeux, une équipe de gardes poursuit un attaquant ou espion rapide dans un graphe, avec l'objectif de rester près de lui éternellement. Le but est de calculer le nombre de domination éternelle (nombre de gardes pour le jeu de l'espion) qui est le nombre minimum de gardes nécessaires pour réaliser l'objectif. La dimension métrique des digraphes et une version séquentielle de la dimension métrique des graphes sont aussi étudiées. Ces deux problèmes ont pour objectif de trouver un sous-ensemble de sommets de taille minimum tel que tous les sommets du graphe sont identifiés uniquement par leurs distances aux sommets du sous-ensemble. En particulier, dans ce dernier problème, on peut "interroger" un certain nombre de sommets par tour. Les sommets interrogés retournent leurs distances à une cible cachée. Le but est de minimiser le nombre de tours nécessaires pour localiser la cible. Ces jeux et problèmes sont étudiés pour des classes de graphe particulières et leurs complexités temporelles sont aussi étudiées. Précisément, dans le Chapitre 3, il est démontré que le jeu de l'espion est NP-difficile et les nombres de gardes des chemins et des cycles sont présentés. Ensuite, des résultats sur le jeu de l'espion dans les arbres et les grilles sont présentés. Notamment, nous démontrons une équivalence entre la variante fractionnaire et la variante "intégrale" du jeu de l'espion dans les arbres qui nous a permis d'utiliser la programmation linéaire pour concevoir ce que nous pensons être le premier algorithme exact qui utilise la variante fractionnaire d'un jeu pour résoudre sa variante "intégrale". Dans le Chapitre 4, des bornes asymptotiques sur le nombre de domination éternelle de la grille du roi sont présentées. Dans le Chapitre 5, des résultats sur la NP-complétude du jeu de Localisation sous différentes conditions (et une variante de ce jeu) sont présentés. Notamment, nous démontrons que le problème est NP-complet dans les arbres. Malgré cela, nous concevons un (+1)-algorithme d'approximation qui résout le problème en temps polynomial. Autant que nous sachions, il n'existe pas d'autres telles approximations pour les jeux dans les graphes. Finalement, dans le Chapitre 6, des résultats sur la dimension métrique des graphes orientés sont présentés. En particulier, les orientations qui maximisent la dimension métrique sont explorées pour les graphes de degré borné, les tores et les grilles.
- 4 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Domination and identification games in graphs
Jeux de domination et d’identification dans les graphes: Dans cette thèse, les jeux à 2 joueurs dans les graphes et leurs aspects algorithmiques et structurels sont étudiés. Nous explorons tout d'abord le jeu de domination éternelle ainsi que sa généralisation, le jeu de l'espion, deux jeux qui reposent sur les ensembles dominants dynamiques. Dans ces deux jeux, une équipe de gardes poursuit un attaquant ou espion rapide dans un graphe, avec l'objectif de rester près de lui éternellement. Le but est de calculer le nombre de domination éternelle (nombre de gardes pour le jeu de l'espion) qui est le nombre minimum de gardes nécessaires pour réaliser l'objectif. La dimension métrique des digraphes et une version séquentielle de la dimension métrique des graphes sont aussi étudiées. Ces deux problèmes ont pour objectif de trouver un sous-ensemble de sommets de taille minimum tel que tous les sommets du graphe sont identifiés uniquement par leurs distances aux sommets du sous-ensemble. En particulier, dans ce dernier problème, on peut "interroger" un certain nombre de sommets par tour. Les sommets interrogés retournent leurs distances à une cible cachée. Le but est de minimiser le nombre de tours nécessaires pour localiser la cible. Ces jeux et problèmes sont étudiés pour des classes de graphe particulières et leurs complexités temporelles sont aussi étudiées. Précisément, dans le Chapitre 3, il est démontré que le jeu de l'espion est NP-difficile et les nombres de gardes des chemins et des cycles sont présentés. Ensuite, des résultats sur le jeu de l'espion dans les arbres et les grilles sont présentés. Notamment, nous démontrons une équivalence entre la variante fractionnaire et la variante "intégrale" du jeu de l'espion dans les arbres qui nous a permis d'utiliser la programmation linéaire pour concevoir ce que nous pensons être le premier algorithme exact qui utilise la variante fractionnaire d'un jeu pour résoudre sa variante "intégrale". Dans le Chapitre 4, des bornes asymptotiques sur le nombre de domination éternelle de la grille du roi sont présentées. Dans le Chapitre 5, des résultats sur la NP-complétude du jeu de Localisation sous différentes conditions (et une variante de ce jeu) sont présentés. Notamment, nous démontrons que le problème est NP-complet dans les arbres. Malgré cela, nous concevons un (+1)-algorithme d'approximation qui résout le problème en temps polynomial. Autant que nous sachions, il n'existe pas d'autres telles approximations pour les jeux dans les graphes. Finalement, dans le Chapitre 6, des résultats sur la dimension métrique des graphes orientés sont présentés. En particulier, les orientations qui maximisent la dimension métrique sont explorées pour les graphes de degré borné, les tores et les grilles.
- Open Access
The Parameterized Complexity of Computing the VC-Dimension
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 results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a $1$-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a $2^{\mathcal{O}(\rm{tw}\cdot \log \rm{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\rm{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).Open AccessThe Parameterized Complexity of Computing the VC-Dimension
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 results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a $1$-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a $2^{\mathcal{O}(\rm{tw}\cdot \log \rm{tw})}\cdot |V|$-time algorithm for any graph $G=(V,E)$ of treewidth $\rm{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH). - Open Access
- 28 July 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (3) , 1-45
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs—Part I: Algorithmic Results
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\) -set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\) , and \(|N(\!\textit{v})\cap S|\in\rho\) for every \(\textit{v}\not\in S\) . The problem of finding a \((\sigma,\rho)\) -set (of a certain size) unifies standard problems, such as Independent Set , Dominating Set , Independent Dominating Set , and many others. For all pairs of finite or cofinite sets \((\sigma,\rho)\) , we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) (if a tree decomposition of width \(\textsf{tw}\) is given in the input). Let \(s_{{\rm top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{{\rm top}}\) is defined analogously for \(\rho\) . Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{{\rm top}}+r_{{\rm top}}+2\) achieved by existing algorithms. Toward defining \(c_{\sigma,\rho}\) , we say that \((\sigma,\rho)\) is \({\mathrm{m}}\) -structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod \({\mathrm{m}}\) , and every integer in \(\rho\) equals \(\beta\) mod \({\mathrm{m}}\) . Then, setting — \(c_{\sigma,\rho}=s_{{\rm top}}+r_{{\rm top}}+2\) if \((\sigma,\rho)\) is not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 2\) , — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 3\) , and \(s_{{\rm top}}=r_{{\rm top}}\) is even, and we count the number of edges between — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+1\) , otherwise, we provide algorithms counting \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) . For example, for the Exact Independent Dominating Set problem (also known as Perfect Code ) corresponding to \(\sigma=\{0\}\) and \(\rho=\{1\}\) , this improves the \(3^{\textsf{tw}}\cdot n^{O(1)}\) algorithm of van Rooij to \(2^{\textsf{tw}}\cdot n^{O(1)}\) . Despite the unusually delicate definition of \(c_{\sigma,\rho}\) , an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair \((\sigma,\rho)\) of finite or cofinite sets where the problem is non-trivial, and any \(\varepsilon > 0\) , a \((c_{\sigma,\rho}-\varepsilon)^{\textsf{tw}}\cdot n^{O(1)}\) -algorithm counting the number of \((\sigma,\rho)\) -sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets \(\sigma\) and \(\rho\) , these lower bounds also extend to the decision version, and hence, our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets.- 28 July 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (3) , 1-45
Open AccessTight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs—Part I: Algorithmic Results
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\) -set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\) , and \(|N(\!\textit{v})\cap S|\in\rho\) for every \(\textit{v}\not\in S\) . The problem of finding a \((\sigma,\rho)\) -set (of a certain size) unifies standard problems, such as Independent Set , Dominating Set , Independent Dominating Set , and many others. For all pairs of finite or cofinite sets \((\sigma,\rho)\) , we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) (if a tree decomposition of width \(\textsf{tw}\) is given in the input). Let \(s_{{\rm top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{{\rm top}}\) is defined analogously for \(\rho\) . Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{{\rm top}}+r_{{\rm top}}+2\) achieved by existing algorithms. Toward defining \(c_{\sigma,\rho}\) , we say that \((\sigma,\rho)\) is \({\mathrm{m}}\) -structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod \({\mathrm{m}}\) , and every integer in \(\rho\) equals \(\beta\) mod \({\mathrm{m}}\) . Then, setting — \(c_{\sigma,\rho}=s_{{\rm top}}+r_{{\rm top}}+2\) if \((\sigma,\rho)\) is not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 2\) , — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \({\mathrm{m}}\) -structured for any \({\mathrm{m}}\geq 3\) , and \(s_{{\rm top}}=r_{{\rm top}}\) is even, and we count the number of edges between — \(c_{\sigma,\rho}=\max\{s_{{\rm top}},r_{{\rm top}}\}+1\) , otherwise, we provide algorithms counting \((\sigma,\rho)\) -sets in time \(c_{\sigma,\rho}^{\textsf{tw}}\cdot n^{O(1)}\) . For example, for the Exact Independent Dominating Set problem (also known as Perfect Code ) corresponding to \(\sigma=\{0\}\) and \(\rho=\{1\}\) , this improves the \(3^{\textsf{tw}}\cdot n^{O(1)}\) algorithm of van Rooij to \(2^{\textsf{tw}}\cdot n^{O(1)}\) . Despite the unusually delicate definition of \(c_{\sigma,\rho}\) , an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair \((\sigma,\rho)\) of finite or cofinite sets where the problem is non-trivial, and any \(\varepsilon > 0\) , a \((c_{\sigma,\rho}-\varepsilon)^{\textsf{tw}}\cdot n^{O(1)}\) -algorithm counting the number of \((\sigma,\rho)\) -sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets \(\sigma\) and \(\rho\) , these lower bounds also extend to the decision version, and hence, our algorithms are optimal in this setting as well. In contrast, for many cofinite sets, we show that further significant improvements for the decision and optimization versions are possible using the technique of representative sets. - Open Access
- 25 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (2) , 1-101
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
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 integers, a (σ, ρ)-set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in \sigma\) for every u ∈ S , and \(|N(v)\cap S|\in \rho\) for every \(v\not\in S\) . The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set , Dominating Set , Independent Dominating Set , and many others. In an accompanying article, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time \((c_{\sigma ,\rho })^{\sf tw}\cdot n^{O(1)}\) (if a tree decomposition of width tw is given in the input). Here, ς, ρ is a constant with an intricate dependency on ς and ρ. Despite this intricacy, we show that the algorithms in the accompanying article are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ɛ > 0, a \((c_{\sigma ,\rho }-\varepsilon)^{\sf tw}\cdot n^{O(1)}\) -algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets ς and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well.- 25 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (2) , 1-101
Open AccessTight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
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 integers, a (σ, ρ)-set of a graph G is a set S of vertices such that \(|N(u)\cap S|\in \sigma\) for every u ∈ S , and \(|N(v)\cap S|\in \rho\) for every \(v\not\in S\) . The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set , Dominating Set , Independent Dominating Set , and many others. In an accompanying article, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time \((c_{\sigma ,\rho })^{\sf tw}\cdot n^{O(1)}\) (if a tree decomposition of width tw is given in the input). Here, ς, ρ is a constant with an intricate dependency on ς and ρ. Despite this intricacy, we show that the algorithms in the accompanying article are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ɛ > 0, a \((c_{\sigma ,\rho }-\varepsilon)^{\sf tw}\cdot n^{O(1)}\) -algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets ς and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well. - Open Access
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (11) , 11229-11237
Parameterized Complexity of Caching in Networks
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 importance to a variety of research areas - including not only content delivery, but also edge intelligence and inference - and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NP-hardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable.
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (11) , 11229-11237
Open AccessParameterized Complexity of Caching in Networks
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 importance to a variety of research areas - including not only content delivery, but also edge intelligence and inference - and the extensive body of work on empirical aspects of caching, very little is known about the exact boundaries of tractability for the problem beyond its general NP-hardness. We close this gap by performing a comprehensive complexity-theoretic analysis of the problem through the lens of the parameterized complexity paradigm, which is designed to provide more precise statements regarding algorithmic tractability than classical complexity. Our results include algorithmic lower and upper bounds which together establish the conditions under which the caching problem becomes tractable.
- 15 November 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 361, 502-522
Complexity of Maker–Breaker games on edge sets of graphs
- 15 November 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 361, 502-522
Complexity of Maker–Breaker games on edge sets of graphs
- Open Access
- 22 October 2024
- Published by Elsevier in Artificial Intelligence
- Vol. 338
The complexity of optimizing atomic congestion
- 22 October 2024
- Published by Elsevier in Artificial Intelligence
- Vol. 338
Open AccessThe complexity of optimizing atomic congestion
- Open Access
Sample compression schemes for balls in graphs
One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)$ of a graph $G=(V,E)$, a realizable sample for $B$ is a signed subset $X=(X^+,X^-)$ of $V$ such that $B$ contains $X^+$ and is disjoint from $X^-$. A proper sample compression scheme of size $k$ consists of a compressor and a reconstructor. The compressor maps any realizable sample $X$ to a subsample $X'$ of size at most $k$. The reconstructor maps each such subsample $X'$ to a ball $B'$ of $G$ such that $B'$ includes $X^+$ and is disjoint from $X^-$. For balls of arbitrary radius $r$, we design proper labeled sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size $2$ for trees and of size $4$ for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.Open AccessSample compression schemes for balls in graphs
One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)$ of a graph $G=(V,E)$, a realizable sample for $B$ is a signed subset $X=(X^+,X^-)$ of $V$ such that $B$ contains $X^+$ and is disjoint from $X^-$. A proper sample compression scheme of size $k$ consists of a compressor and a reconstructor. The compressor maps any realizable sample $X$ to a subsample $X'$ of size at most $k$. The reconstructor maps each such subsample $X'$ to a ball $B'$ of $G$ such that $B'$ includes $X^+$ and is disjoint from $X^-$. For balls of arbitrary radius $r$, we design proper labeled sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size $2$ for trees and of size $4$ for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs. - Open Access
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (18) , 20044-20052
The Complexity of Optimizing Atomic Congestion
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 application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies - that is, a centrally planned routing that minimizes the average cost of agents - is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (18) , 20044-20052
Open AccessThe Complexity of Optimizing Atomic Congestion
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 application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies - that is, a centrally planned routing that minimizes the average cost of agents - is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.
- Open Access
- 26 January 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 990
Smash and grab: The 0 ⋅ 6 scoring game on graphs
- 26 January 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 990
Open AccessSmash and grab: The 0 ⋅ 6 scoring game on graphs