Introduction
Paired threshold graphs (PTGs) offer a sophisticated framework for modeling social and economic interactions where both total strength and mutual similarity are prerequisites for connection. While traditional threshold graphs assign weights to vertices and connect them if their sum exceeds a limit, PTGs add a second constraint: the difference between weights must be sufficiently small. This dual-threshold approach captures more realistic scenarios but introduces significant structural complexity. This paper provides a complete theoretical characterization of PTGs and introduces a linear-time recognition algorithm, a major improvement over the previous $O(n^6)$ complexity.
Structural Characterization and the Graph Hierarchy
A central contribution of this work is clarifying the relationship between PTGs and other well-known graph families. The authors prove that every paired threshold graph is an interval graph. This placement is crucial because interval graphs possess well-understood properties that facilitate efficient algorithmic processing.
As shown in the hierarchy, PTGs sit between interval graphs and threshold graphs. Interestingly, PTGs are structurally richer than $k$-nested interval graphs for any fixed $k$, as they can contain an arbitrary number of nested intervals.
Methodology: Broom Orderings and Clique Paths
To bridge the gap between numerical weights and geometric structure, the authors introduce the "broom ordering." This vertex ordering partitions a graph into a "handle" (an independent set) and a "brush" (a unit interval graph). The connectivity between these two components is strictly constrained: the neighborhoods of the independent set must be consecutive within the ordering of the unit interval graph.
By leveraging "clique paths"—a method of organizing the maximal cliques of a graph—the authors identify the specific structural signatures of a PTG. They also demonstrate that the two thresholds ($T_+$ for sum and $T_-$ for difference) can be mathematically normalized to be equal without altering the graph's topology, simplifying the underlying proofs.
Key Results and Algorithmic Breakthrough
The headline achievement is a recognition algorithm that determines if a graph is a PTG in $O(|V| + |E|)$ time. This linear-time performance is achieved by a pre-processing pipeline that removes universal and isolated vertices to isolate the core PTG structure.
Furthermore, the paper identifies minimal induced subgraphs that serve as obstacles to threshold graph properties.
The identification of these configurations ($2K_2$, $P_4$, and $C_4$) provides a foundation for the more complex structural analysis required to recognize PTGs.
Conclusion and Future Directions
While the paper focuses on the connected case, it notes that disconnected PTGs can have at most one component that is a non-unit interval graph. Future work remains in applying these findings to real-world datasets, particularly in social network analysis where "similarity-plus-strength" dynamics are prevalent. Additionally, while the recognition problem is solved, the inverse problem of optimally assigning weights and thresholds to a given PTG remains an area for further exploration.
Summary updated