Domination and Identification Games in Graphs

Fionn Mc Inerney 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this thesis, 2-player games on graphs and their algorithmic and structural aspects are studied. First, we investigate two dynamic dominating set games: the {\it eternal domination game} and its generalization, the {\it spy game}. In these two games, a team of guards pursue a fast attacker or spy in a graph with the objective of staying close to him eternally and one wants to calculate the {\it eternal domination number} ({\it guard number} in the spy game) which is the minimum number of guards needed to do this. Secondly, the {\it metric dimension} of digraphs and a sequential version of the metric dimension of graphs are then studied. These two problems are those of finding a minimum subset of vertices that uniquely identify all the vertices of the graph by their distances from the vertices in the subset. In particular, in the latter, one can probe a certain number of vertices per turn which return their distances to a hidden target and the goal is to minimize the number of turns in order to ensure locating the target. These games and problems are studied in particular graph classes and their computational complexities are also studied. Precisely, in Chapter 3, the NP-hardness of the spy game and the guard numbers of paths and cycles are first presented. Then, results for the spy game on trees and grids are presented. Notably, we show an equivalence between the fractional variant and the ``integral" version of the spy game in trees which allowed us to use Linear Programming to come up with what we believe to be the first exact algorithm using the fractional variant of a game to solve the ``integral" version. In Chapter 4, asymptotic bounds on the eternal domination number of strong grids are presented. In Chapter 5, results on the NP-completeness of the {\it Localization game} under different conditions (and a variant of it) and the game in trees are presented. Notably, we show that the problem is NP-complete in trees, but despite this, we come up with a polynomial-time (+1)-approximation algorithm in trees. We consider such an approximation to be rare as we are not aware of any other such approximation in games on graphs. Lastly, in Chapter 6, results on the metric dimension of oriented graphs are presented. In particular, the orientations which maximize the metric dimension are investigated for graphs of bounded degree, tori, and grids.
Complete list of metadatas

Cited literature [125 references]  Display  Hide  Download

https://hal.inria.fr/tel-02184625
Contributor : Fionn Mc Inerney <>
Submitted on : Tuesday, July 16, 2019 - 11:08:27 AM
Last modification on : Wednesday, July 17, 2019 - 1:31:20 AM

File

PhdThesis_Fionn.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02184625, version 1

Collections

Citation

Fionn Mc Inerney. Domination and Identification Games in Graphs. Computer Science [cs]. Université Côte D'Azur, 2019. English. ⟨tel-02184625⟩

Share

Metrics

Record views

131

Files downloads

381