Covering and domination at distance

Various theoretical and practical motivations have led to generalizations of many classical graph optimization problems to their distance-based variants. Informally, this means that the adjacency property used to define a feasible solution to the problem is replaced with a relaxed property based on distances in graphs. We consider distance-based variants of four classical covering and domination problems in graphs: the dominating set, edge dominating set, vertex cover, and edge cover problems. We study the relationships between the optimal solution values of the  corresponding problems and the algorithmic complexity of their computation under certain restrictions. More precisely, we study the Distance-k Dominating Set, Distance-k Edge Dominating Set, Distance-k Vertex Cover, and Distance-k Edge Cover problems. For each k ≥ 1 and for each of the four problems, we completely characterize the family of graphs H such that the problem is solvable in polynomial time in the class of H-free graphs (under the assumption that P neq NP).

Joint work with Martin Milanič and Clément Dallard.

Our Math Research Seminar will only be broadcasted via Zoom.

We are looking forward to meeting at the video-conference.

Join the Zoom Meeting Here.

Everyone is welcome and encouraged to attend.