Linear-Time Recognition of Double-Threshold Graphs

Abstract

A graph $G=(V,E)$ is a double-threshold graph if there exist a vertex-weight function $w:V\to \mathbb{R}$ and two real numbers $\mathtt{lb},\mathtt{ub}\in \mathbb{R}$ such that $uv\in E$ if and only if $\mathtt{lb}\le \mathtt{w}(u)+\mathtt{w}(v)\le \mathtt{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.

18 pages, 8 figures

References in corpus (1)

• Weakly threshold graphs

Cited by in corpus (1)

• Characterization and Linear-time Recognition of Paired Threshold Graphs