Spanning tree congestion of proper interval graphs

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Yota Otachi
DOI: 10.48550/arxiv.2602.13756
Cited by: 0

Abstract

We show that the spanning tree congestion problem is NP-complete even on proper interval graphs with linear clique-width at most 4 and diameter 3. By slightly modifying the reduction, we also show that the problem is NP-complete on (general) graphs of diameter 2.

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs Graph Labeling and Dimension Problems

Publication details

Journal / source
arXiv (Cornell University)
Publication date
14 February 2026
Language
EN
Document type
Preprint