---
abstract: 'A graph $G = (V,E)$ is a *double-threshold graph* if there exist a vertex-weight function $w \colon 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 as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections 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 \[COCOON 2018\] ran in $O(n^6)$ time, where $n$ is the number of vertices.'
author:
- Yusuke Kobayashi
- Yoshio Okamoto
- Yota Otachi
- Yushi Uno
bibliography:
- 'dtg.bib'
title: 'Linear-Time Recognition of Double-Threshold Graphs'
---

Introduction {#sec:introduction}
============

A graph is a *threshold graph* if there exist a vertex-weight function and a real number called a weight lower bound such that two vertices are adjacent in the graph if and only if the associated vertex weight sum is at least the weight lower bound. Threshold graphs and their generalizations are well studied because of their beautiful 