On recognition of threshold tolerance graphs and their complements.

A graph G = ( V , E ) is a threshold tolerance graph if each vertex v ∈ V can be assigned a weight w v and a tolerance t v such that two vertices x , y ∈ V are adjacent if w x + w y ≥ min ( t x , t y ) . Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an O ( n 4 ) runtime. We give an O ( n 2 ) algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy. [ABSTRACT FROM AUTHOR]