Domination and total domination on asteroidal triple-free graphs (Q1962038)

An asteroidal triple (AT) of an undirected graph \(G\) is a set of three vertices of \(G\) such that there is a path between any two of them avoiding the neighborhood of the third one. A graph is AT-free if it contains no AT. The structure and algorithmic properties of AT-free graphs have been studied extensively---AT-free graphs generalize well-known graph classes such as interval, permutation, trapezoid and cocomparability graphs. This paper presents polynomial time algorithms for solving the problems DOMINATING SET and TOTAL DOMINATING SET restricted to AT-free graphs. These algorithms even work in polynomial time on graphs with dominating shortest path---a generalization of AT-free graphs. The key idea of the algorithms is to compute a certain type of dominating set by dynamic programming through the levels of a BFS-tree.