Using Ray-shooting Queries for Sublinear Algo- rithms for Dominating Sets in RDV Graphs
Therese Biedl, Prashant Gokhale · 2026
Read Using Ray-shooting Queries for Sublinear Algo- rithms for Dominating Sets in RDV Graphs by Therese Biedl, Prashant Gokhale (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04626.txt.
Introduction
Therese Biedl and Prashant Gokhale find a smallest set of guards for a special class of graphs without ever listing the edges, in a 2026 arXiv paper. RDV graphs arise as the intersection graphs of downward paths in a rooted tree, sitting between interval graphs and chordal graphs. Earlier work showed their adjacency questions reduce to whether horizontal and vertical segments cross, which yielded a fast maximum matching.
Adding a ray shooting data structure to that geometric kit, the authors compute a minimum dominating set. A smallest set of vertices such that every vertex is in it or next to one — in near-linear time, still without examining all edges. As a by-product, the same idea gives a new proof that interval graphs admit a minimum dominating set in strictly linear time. The results extend a programme of fast algorithms for graph problems whose inputs have compact geometric representations.
Catalog record
| CREATOR | Therese Biedl, Prashant Gokhale |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-04626
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Using Ray-shooting Queries for Sublinear Algo- rithms for Dominating Sets in RDV Graphs Thanks: Research of TB supported by NSERC, RGPIN-2020-03958. Research of PG supported by a MITACS Globalink Graduate Fellowship. The results also appeared as part of the second author’s Master’s thesis [ 17 ] at the University of Waterloo . Therese Biedl, Prashant Gokhale Abstract In this paper, we study the dominating set problem in RDV graphs , a graph class that lies between interval graphs and chordal graphs and defined as the v ertex-intersection graphs of d ownward paths in a r ooted tree. It was shown in a previous paper that adjacency queries in an RDV graph can be reduced to the question whether a horizontal segment intersects a vertical segment. This was then used to find a maximum matching in an n n -vertex RDV graph, using priority search trees, in O ( n log n ) O(n\log n) time, i.e., without even looking at all edges. In this paper, we show that if additionally we also use a ray shooting data structure, we can also find a minimum dominating set in an RDV graph O ( n log n ) O(n\log n) time (presuming a linear-sized representation of the graph is given). The same idea can also be used for a new proof to find a minimum dominating set in an interval graph in O ( n ) O(n) time. 1 Introduction In a graph G , a subset S of vertices is called dominating if every vertex in the graph is either included in S or adjacent to a vertex in S . Finding a minimum dominating set is one of the oldest problems in graph theory and graph algorithms, with applications in routing problems in wireless networks and facility location problems. Finding a minimum dominating set is \mathsf{NP} -hard in general [ 13 ] , as there exists a straightforward reduction from the set cover problem. On the other hand, an easy O(\log{n}) -approximation algorithm is well known [ 7 ] . In this paper, we study the problem of finding a minimum dominating set in graph classes whose structure makes it feasible to find a minimum dominating set very efficiently. The minimum dominating set problem remains \mathsf{NP} - h ard for chordal graphs [ 3 ] but polynomial time algorithms exist for permutation graphs [ 11 ] , cographs [ 8 ] , and strongly chordal graphs [ 12 ] . (Section 2 will review those definitions that are needed later again.) For more information about the complexity of minimum dominating set in various subclasses of perfect graphs, the interested reader can look at an overview paper by Corneil and Stewart [ 9 ] . This paper is concerned with finding sub-linear time algorithms for minimum dominating set, i.e., we are not even allowed to look at all edges. The main ingredient here is that the graph is given implicitly, typically via an intersection representation. For example in an interval graph (i.e., the intersection graph of n 1-dimensional intervals), a minimum dominating set can be found in O(n) time if a suitable interval representation is given, even though the graph may have \Theta(n^{2}) edges. 1 1 1 This result is attributed to [ 1 , 4 , 26 ] in [ 6 ] , but neither of these three papers claims an O(n) -time algorithm for dominating set in interval graphs. The closest is [ 1 ] , which states a run-time of O(n\log n) for the minimum-weight total dominating set problem. Nevertheless, it is easy to develop an O(n) -algorithm; see also Section 4 . Other problems can also be solved in sub-linear time in interval graphs, see e.g. [ 5 ] for path cover, Hamiltonian cycle and domatic partition, or [ 20 ] for maximum matching. Cheng, Kaminski, and Zaks [ 6 ] extended the algorithm for dominating set in interval graphs to a graph class slightly bigger than interval graphs, specifically, intersection graphs of downward paths in a spider (a tree consisting of multiple paths sharing a common node). In this paper, we study a graph class called RDV graphs , which strictly contains the graph class of Cheng, Kaminski and Zaks (and hence the interval graphs) . RDV graphs are the intersection graphs of downward paths in an arbitrary rooted tree. These are known to be strongly chordal graphs, and as such we can find a minimum dominating set in them in linear time [ 12 ] . In fact, this was known even earlier: Booth and Johnson showed that a straightforward linear-time greedy algorithm performs optimally if applied to an RDV graph [ 3 ] . The goal of this paper is to modify the greedy-algorithm by Booth and Johnson to achieve run-time O(|T|+n\log n) , where |T| is the size of the host-tree in a given intersection representation of the RDV graph. (We may assume that |T|\in O(n) [ 2 ] , and will therefore typically state the bound as O(n\log n) time.) While this is not quite as fast as the algorithm for interval graphs, it is still sublinear since RDV graphs may have quadratically many edges. The key ingredient is the insight (first published in a companion paper [ 2 ] ) that adjacency queries in an RDV graph can be reduced to an intersection problem between horizontal and vertical segments. In [ 2 ] , this insight was combined with range-minimum queries (implemented with a priority search tree) to obtain sublinear algorithms for maximum matching in RDV graphs. In this paper, we show that if we additionally also use a ray-shooting data structure, then more complicated neighbourhood queries can also be solved efficiently without looking at all edges, and use this to solve the minimum dominating set in sublinear time. (The technique should work more broadly; we briefly show that we can also find a minimum dominating set in an interval graph with it.) The paper is structured as follows. In Section 2 , after reviewing some definitions, we briefly explain results from the companion paper that we need. In Section 3 we give the greedy-algorithm and explain which of its operations cannot easily be sped up with the known techniques. Next we explain how to use a ray-shooting data structure to implement this operation. This gives us the faster run-time for the gree d y-algorithm for dominating set. We discuss an O(n) -time algorithm for dominating set in interval graphs in Section 4 and end in Section 5 with further thoughts. 2 Background We assume familiarity with graphs, and refer e.g. to Diestel’s book for basic terminology [ 10 ] . For a vertex z in a graph, we write N[z] for the closed neighbourhood , i.e., the vertex z and all its neighbours. Often we will fix a vertex order z_{1},\dots,z_{n} . We then write N_{\geq}[z_{i}] for those vertices z_{q} in the closed neighbourhood of z_{i} that satisfy q\geq i (and similarly define N_{<}[z_{i}],N_{\leq}[z_{i}],N_{>}[z_{i}] ). In this paper we only study a graph G that has a representation as a vertex-intersection graph of subtrees of a tree (or tree-intersection representation for short). This