Tree Containment Parameterized by Scanwidth

Leo van Iersel, Mark Jones, Mathias Weller · 2026

Read Tree Containment Parameterized by Scanwidth by Leo van Iersel, Mark Jones, Mathias Weller (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-31071.txt.

Description

Van Iersel, Jones and Weller ask whether a given evolutionary tree fits inside a proposed network, measured by scanwidth, a gauge of how tree-like the network is. They give a method whose running time grows with that width and prove no much faster method exists under a standard hardness assumption, even for binary networks. The upper and lower bounds match, pinning down the problem's difficulty in terms of scanwidth.

Catalog record

CREATORLeo van Iersel, Mark Jones, Mathias Weller
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79009
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.31071

Browse the full library · About the Tower of Babel