Dichotomy study of the Steiner tree problem in split-like graphs
Jyothish S, N Sadagopan · 2026
Read Dichotomy study of the Steiner tree problem in split-like graphs by Jyothish S, N Sadagopan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29540.txt.
Description
Jyothish S and Sadagopan Narasimhan study the Steiner tree problem across split-like graphs unifying bipartite, split, and bisplit graphs. Through reductions, they draw boundaries. On bipartite graphs free of large stars, the problem is tractable to star size three and hard from size four. On star-free bisplit graphs it stays tractable from star size three up. Bisplit graphs of diameter two admit solutions, but diameters three and four turn hard, and star convexity helps only on the clique side, with chordal bipartite and split cases hard.
Catalog record
| CREATOR | Jyothish S, N Sadagopan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38504 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.29540