A polynomial algorithm for general d-position in trees
A vertex set is in general $d$-position if no three of its vertices lie on a shortest path of length at most $d$. We give an exact algorithm for an $n$-vertex tree in $O(n(D+2)^4)$ time and $O(n(D+2)^2)$ space, where $D=\min\{d,n-1\}$. In particular, the problem is polynomial-time solvable when the threshold is part of the input. This answers the tree-complexity question posed by Klav\v zar, Rall, and Yero in 2021 and retained in the August 2026 version of the general position survey. The dynamic program uses two truncated distances at each rooted boundary: the nearest selected vertex and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00448
curl -X POST /api/v1/records/hexagon/2610.00448/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00448/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'