Skip to Main content Skip to Navigation

Graph domination and reconfiguration problems

Abstract : This object of this thesis is to study graph domination and reconfiguration problems. A dominating set of a graph is a subset of vertices such that every vertex of the graph either is in the set, or is a neighbor of at least one vertex in the set. As for reconfiguration problems, they consist in, given a source problem, determining if it is possible, and how, to go from a solution of this source problem to another by performing a sequence of elementary changes following a given rule and that maintain a solution all along. The first chapter is a general introduction, and the second chapter is a preliminary chapter. The third chapter is devoted to reconfiguration problems. We give the definitions that are essential to understand the reconfiguration problems exposed in the following chapters. These definitions are illustrated with several problems: the 15-puzzle game and its generalizations, the reconfiguration of independent sets and dominating sets in a graph, the reconfiguration of graph colorings, the reconfiguration of the satisfiability problem, as well as the reconfiguration of connected multigraphs with the same degree sequence. The fourth chapter focuses on this last problem. We give a polynomial approximation algorithm that outputs a reconfiguration sequence between two connected multigraphs that have the same degree sequence, of length at most 2.5 times the minimum length. The elementary operation consists in exchanging an extremity between two disjoint edges. The best ratio known so far was 4, and this improvement is due to the discover of a new upper bound. However, we keep the same lower bound, and we show that as long as a better lower bound is not found, the approximation ratio can not be drastically better than 2.5. The fifth chapter goes back to domination problems. We study the connectivity and diameter of the reconfiguration graph, when the elementary operation consists in the addition or removal of a vertex of the set. In other words, we search for sufficient conditions that guarantee the existence of a reconfiguration sequence between two dominating sets, and give an upper bound on the length of this sequence. In particular, we are interested in the maximum size of the dominating sets authorized in the sequence. We show that above a certain value, that depends on the independence number of the graph, the reconfiguration graph has linear diameter. We also give another upper bound, that depends on the treewidth of the graph, above which the reconfiguration graph is connected and has linear diameter. We also give two other upper bounds for planar graphs and for K_l-minor-free graphs. In the sixth chapter, we change the elementary operation, that then consists in sliding a token along an edge (a vertex is removed from the set, and one of its neighbors is added). We study the complexity of the reachability problem, which consists in determining if there exists a reconfiguration sequence between two given dominating sets. We show that the problem is PSPACE-complete in planar bipartite graphs, unit disk graphs, circle graphs and line graphs. We also give a polynomial algorithm for circular arc graphs. The seventh chapter is devoted to the eternal domination problem. We introduce a version of the problem on directed graphs. We give some bounds on the value of the eternal domination number in two versions of the problem, that generalize results on undirected graphs. We then introduce a new problem that consists in searching for the orientation of a graph that minimizes the two parameters. We show that in the first version, determining if the parameter is at most a given k is a coNP-hard problem. We also study the value of both parameters in several graph classes such as cycles, trees, complete and complete bipartite graphs, and different types of grids. We finally characterize the graphs for which the value of the second parameter is 2
Complete list of metadata
Contributor : Abes Star :  Contact
Submitted on : Monday, November 8, 2021 - 12:03:09 PM
Last modification on : Wednesday, November 24, 2021 - 9:38:14 AM


Version validated by the jury (STAR)


  • HAL Id : tel-03419113, version 1


Alice Joffard. Graph domination and reconfiguration problems. Data Structures and Algorithms [cs.DS]. Université de Lyon, 2020. English. ⟨NNT : 2020LYSE1216⟩. ⟨tel-03419113⟩



Les métriques sont temporairement indisponibles