math.CO — Combinatorics

A polynomial algorithm for general d-position in trees

Contributed by Daniel Adam Pyle

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 the nearest far endpoint of an ancestor-comparable selected pair. These distances characterize every forbidden triple created by joining child subtrees. The algorithm reconstructs an optimal set and extends to signed vertex weights and exact counting of optimal sets. It also computes the full cardinality generating polynomial in $O(n^2(D+2)^4)$ coefficient operations. Exhaustive comparisons with direct subset enumeration support the implementation independently of the proof.