Algorithms for the Metric Dimension problem on directed graphs
Time: 14:00 -- Location: LRI, 445
summary: In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs, and has gained a lot of attention in recent years, mainly because of its difficulty: it is NP-complete and has a best polynomial-time approximation factor of log(n) even on very restricted graph classes. We focus our study on directed and oriented graphs (the difference is that directed graphs may contain 2-cycles, unlike oriented graphs), for which the Metric Dimension has been recently studied. We prove that Metric Dimension remains NP-hard, even on planar DAGs of maximum degree 6. However, we find linear-time algorithms solving the problem on directed trees (directed graphs whose underlying graph is a tree) and on orientations of unicyclic graphs. Finally, we give a fixed-parameter-tractable algorithm for directed graphs when parameterized by modular-width.