In interval graphs and many generalizations thereof, problems such as MATCHING, INDEPENDENT-SET and DOMINATING-SET can be solved with simple greedy-algorithms in linear (i.e., O(m+n) time. However, it is sometimes possible to improve on this runtime if a suitable intersection representation is given; for example it is possible to find a minimum dominating set in an interval graph in O(n) time. We study RDV graphs, a generalization of interval graphs, namely, the intersection graphs of directed paths in a rooted tree. It was known that the above three problems can be solved in O(n log n) time if a suitably small representation is given. In this paper, we reduce the runtime to O(n). Furthermore, while the previous results used non-trivial operations such as range-minimum queries and ray-shooting queries, we need nothing more complicated than lists and (for MATCHING) a Union-Find data structure.
Last update: October 22, 2026.