Faster solutions for path intersection problems in tree graphs

Solving problems in RDV Graphs faster and easier

Data Structures and Algorithms

Summary

Some computer problems that involve matching and grouping items can be solved quickly on simple graphs. This paper looks at a more complex kind of graph formed by directed paths in trees, called RDV graphs. The authors find ways to solve these problems even faster, improving the speed from something that took longer (n log n steps) to something closer to the fastest possible (just n steps). They also simplify the techniques required to do this, using basic data structures instead of complicated ones.

What this means in practice

  • For network engineers: Optimize resource assignment in communication networks modeled by rooted tree path intersections using faster minimum dominating set calculations.
  • For bioinformatics analysts: Analyze biological pathways represented as directed paths in rooted trees more efficiently for pattern matching and clustering tasks.

Authors

Therese Biedl, Günter Rote

Abstract

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 representation as intersection graph 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.