Characterization and Linear-time Recognition of Paired Threshold Graphs

Guozhen Rong, Yixin Cao, Jianxin Wang

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.

Hierarchy of graph classes showing the position of Paired Threshold graphs.

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.

Forbidden induced subgraphs: (a) 2K2, (b) P4, and (c) C4.

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

BibTeX
@inproceedings{rong2020characterization,
  author = {Guozhen Rong and Yixin Cao and Jianxin Wang},
  title = {{Characterization and Linear-time Recognition of Paired Threshold Graphs}},
  booktitle = {WG},
  year = {2020},
  doi = {10.1007/978-3-030-60440-0\_24},
}
Figure