Séminaire de Dipayan Chakraborty

A vertex subset S of a graph G = (V(G),E(G)) is called a “locating set” of G if, for each pair u,v of distinct vertices in V(G) \ S, the neighborhood of u in S (i.e. N(u) \cap S) is different from the neighborhood of v in S (i.e. N(v) \cap S). Moreover a vertex subset S of G is called a “locating dominating set” (or “LD set” for short) if S is both a dominating set and a locating set of G. LD sets had been first introduced by Peter Slater in 1988 and are useful in modeling monitoring / surveillance systems in networks and facilities. The problem of finding a minimum LD set in a graph is in general an NP-complete problem. As a result, over time, the problem has been studied under the lens of parameterized complexity with respect to several natural and structural graph parameters. In my recent work with my collaborators, we look at the problem of LD sets under several parameters like solution size, tree width, vertex cover number, twin-cover number, neighborhood diversity, distance to clique, feedback edge set number and so on. Our work includes establishing FPT algorithms for solving the problem of LD sets with respect to the above-mentioned parameters; it also includes establishing (tight) running-time lower bounds on algorithms solving LD sets under well-established hypotheses like the Exponential Time Hypothesis (ETH). In the talk, I will look to present some of our results along with an overview of how all of them tie in together.