Thesis of Nour Dyab

A New Graph Protection Model: Eternal and m-Eternal Feedback Vertex Sets

Defense date: 24/10/2023

Advisor: Hamamache Kheddouci


This thesis aims to develop a model for graph protection using mobile guards, specifically focusing on the concept of eternal feedback vertex sets. The problem of protecting a graph using mobile guards has been extensively studied in the literature. This problem involves defending the vertices, as well as edges, of a graph G against any attack using defence units, called guards, stationed at the vertices of G. Our primary interest lies in protecting graphs against infinite sequences of attacks, where each attack is executed one at a time.  A protection problem can be modelled by a two-player game between a defender and an attacker. In this game, the defender selects the initial configuration of guards in the first turn and must defend all vertices of G against any attack by reconfiguring the guards at each subsequent turn. On the other hand, the attacker chooses the location of each attack at each turn. An attack is considered defended if a guard can be moved to the attacked vertex via an edge. The defender wins the game if they successfully defend the graph against every sequence of attacks, while the attacker wins if he manages to breach the defence. Importantly, the sequence of attacks can be of infinite length.  In this thesis, we introduce two new variants of the graph protection problem, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). The two variants are modelled in the same way using a two-player game, with the specific condition that the set of vertices chosen by the defender to receive guards must simultaneously form a feedback vertex set and a dominating set in each turn. In other words, the Eternal Feedback Vertex Set on a graph can be seen as an infinite game between a defender and an attacker, where the defender chooses a set of guards Fi at each turn i, i ≥ 1. At turn i, the attacker chooses a vertex ri, called an attack, in V \Fi-1 and the defender must defend the attack by moving to ri a guard from a vertex vj adjacent to ri. The new guards configuration is Fi = Fi−1 ∪ {ri} \ {vj}. The sets Fi, for any i ≥ 1, must be dominating and feedback vertex sets. In the case where the defender protects vertices by moving more than one guard, we talk about the m-Eternal Feedback Vertex Sets.   Our primary focus in this study is to propose a new protective model that utilizes mobile guards to protect the vertices of a graph.  We provide formal definitions of our new models of graph protection, namely the Eternal Feedback vertex set and Eternal Feedback vertex set. Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. Then, we compare the two parameters; the eternal and m-eternal numbers, F and Fm, corresponding to the smallest eternal (m- eternal) feedback set of the graph, with known graph parameters. Consequently, we deduce some inequalities for F and Fm on cycles, complete graphs and complete bipartite graphs. Also, we provide a detailed study of both variants on grids, distance and circulant graphs. Also, we consider the class of interval graphs, we prove that the eternal feedback vertex number F(G) on an interval graph G depends on the F of cliques in G. And we develop a linear algorithm for finding the eternal feedback vertex set on G, which utilizes a graph partitioning method as a prepossessing step, and then selects the guards from each partition independently. Finally, we explore strategies for constructing an EFVS and determining the eternal feedback vertex number on various classes of graphs, including k-dimensional graphs, wheel graphs, and fan graphs. We also develop a linear algorithm for finding the eternal feedback vertex set in k-spiral graphs. Finally, we conclude the thesis by providing a comprehensive summary of the presented work and highlighting intriguing open problems for further investigation.

Pr. Olivier TogniProfesseur(e)Université de BourgogneRapporteur(e)
Pr. Abdallah MakhoulProfesseur(e)Université de Franche-ComtéRapporteur(e)
Pr. Salima BenbernouProfesseur(e)Université Paris CitéExaminateur​(trice)
Dr. Maidoun MortadaMaître de conférenceUniversité libanaiseExaminateur​(trice)
Dr. Nora FaciMaître de conférenceUniversité Lyon 1Examinateur​(trice)
Dr. Mohamed LalouMaître de conférenceUniversité de BourgogneExaminateur​(trice)
Pr. Hamamache KheddouciProfesseur(e)Université Lyon 1Directeur(trice) de thèse