Linear-Time Recognition of Double-Threshold Graphs

A graph G = (V, E) is a double-threshold graph if there exist a vertex-weight function w: V -> R and two real numbers lb, ub. R such that uv is an element of E if and only if lb <= w(u) + w(v) <= ub. In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in O(n(3)m) time, where n and m are the numbers of vertices and edges, respectively.