Algorithmique et structure des problèmes d'identification dans les graphes

Identification problems in graphs are those which, in general, deal with « separating » one vertex from another. To that end, one of the most well-studied formulations of such problems is by using dominating sets in graphs. A dominating set is a vertex subset S of a graph G such that any vertex not is S must have a neighbor in S. Using such sets as a combinatorial tool, pairs of vertices can be « separated » by finding a dominating set such that any two distinct vertices have distinct sets of neighbors in the set.In this thesis, we study such identification problems in graphs based on dominating and total-dominating sets (a stronger variant of dominating sets). Also varying the types of (distinct) neighborhoods by which the vertices are « separated », we look at four separating properties, one of which is newly introduced. In combination with the two dominating properties therefore, we study at eight separating-dominating sets (often called codes) in graphs. In short, we study X-codes of graphs, where X belongs to the set {LD, LTD, ID, ITD, OD, OTD, FD and FTD} of abbreviations of the original code names. The objective of such studies is to minimize the cardinalities of the codes and we call such a minimum cardinality to be a code number (or the X-number).The thesis has both structural and algorithmic results. In the structural part, we study general bounds on all the eight codes and compare pairwise their code numbers to provide a complete scheme of their relations. We also study several conjectures from the literature on bounds of code numbers. For a graph G, the upper bounds we study are of the form f(G).n, where n is the number of vertices of a graph and f(G) is some number that is a function of the graph G.On twin-free graphs, we study such an upper bound conjecture with f(G) = 1/2 for X=LD and with f(G) = 2/3 for X=LTD. For X=LD, we prove the conjecture to be true and tight for subcubic and block graphs. Moreover, for X=LTD, we prove the corresponding conjecture to be true and tight for split, cobipatite, block and subcubic graphs. For X=ID, we prove a tight upper bound conjecture on triangle-free graphs with f(G) = (d-1)/d, where d is the maximum degree of a graph G. For X=OTD, we prove an exact result for cycles with f(G) being about 2/3 ; and for four-cycle-free graphs, we prove a tight upper bound with f(G) = (2d-1)/d, where d is again the maximum degree of G. Moreover, for block graphs, we establish both upper bounds (including a conjecture) and lower bounds on X-numbers for X=LD, ID and OTD in terms of the number of vertices and blocks (maximal 2-connected subgraphs). For X=OD, we study and find exact values of the OD-numbers for several graph classes like half-graphs, headless spiders and suns. Finally, for X=FD and FTD, we again find the exact values of the respective code numbers for paths, cycles, half-graphs and headless spiders.In the algorithmic part of the thesis, we prove that for the newly introduced X-codes, that is for X=OD, FD and FTD, finding a minimum X-code is NP-complete. We also prove that, despite the OD- and the OTD-numbers (respectively, the FD- and the FTD-numbers) differing with each other by at most 1, it is in general NP-hard to decide if such a difference exists on a given graph. Finally, with the problem of finding a minimum LD-code being already known to be NP-complete, we look at the problem parameterized by some natural and structural parameters. We provide a tight lower bound on algorithmic running times in terms of the solution size and also prove an incompressibility result in terms of the order of the graph. With vertex cover number, twin-cover number and distance to clique, we provide algorithms running in slightly super-exponential times. Moreover, when parameterized by treewidth, we provide a double-exponential algorithm that is also tight under the ETH. With neighborhood diversity and feedback edge set number as parameters, we show that the problem has a linear kernel.