Wataru

Доказательство по индукции. Для одной или двух вершин всегда будет 1 в D.

Пусть degree(v) - количество вершин, инцидентных v.
Лемма: В турнире с n вершинами будет хотя бы одна с degree() >= (n-1)/2. Иначе, просуммируем все degree().
С одной стороны, сумма будет равна количеству ребер, т.е. n(n-1)/2. С другой, эта сумма < n*(n-1)/2 по предполоджению. Противоречие, значит существует v: degree(v) >= (n-1)/2

Теперь докажем основное утверждение.
Рассмотрим турнир с n>2 вершинами. Там есть хотя бы одна v: degree(v) >= (n-1)/2. Включим ее в D. и удалим из графа ее и все, которым она инцедентна. Мы удалили из графа не меньше 1+(n-1)/2 вершин, фактически уполовинив количество вершин в графе. По индукционному предположению там надо log(n/2) вершин в доминирующем множестве. Иы добавили к ней 1. Поэтому в итоге нам надо log(n) вершин и для этого графа.

Это же доказательство можно использовать для построения D - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.

Утверждение: Рассмотрим какую-то вершину v. Допустим самый ранний момент, в который можно попасть в нее - t. Если эта вершина есть в кратчайшем пути из вершины a в вершину b, то обязательно есть путь, не длинее, в котором вершина v посещается как раз в момент t.
Такой путь можно получить конструктивно - начало взять из кратчайшего пути в v, а конец из кратчайшего пути из a в b, может придется подождать какое-то время в вершине, прежде чем продолжить путь.

С учетом этого утверждения становится понятно, что можно решать вашу задачу стандартным алгоритмом дейкстры для поиска самого быстрого пути во все вершины. Там при релаксации (пересчете минимального растояния) надо просто учитывать, в какое ближайшее к текущему веремни ребро станет доступно для прохождения.