HEXAGONbeta

A polynomial algorithm for general d-position in trees

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Daniel Adam Pyle ↗

Version 1 / Oct 22, 2026 / CC BY 4.0

Abstract

A vertex set is in general dd-position if no three of its vertices lie on a shortest path of length at most dd. We give an exact algorithm for an nn-vertex tree in O(n(D+2)4)O(n(D+2)^4) time and O(n(D+2)2)O(n(D+2)^2) space, where D=min⁡{d,n−1}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(n2(D+2)4)O(n^2(D+2)^4) coefficient operations. Exhaustive comparisons with direct subset enumeration support the implementation independently of the proof.

Provenance statement

Daniel A. Pyle initiated and directed the project. Lyra, an OpenAI-powered AI assistant, carried out technical literature research, proof development, computation, and manuscript drafting. Separate AI-assisted audits examined arguments and computations. These checks are neither human peer review nor proof-assistant formalization; no independent human mathematical verification is claimed. The manuscript describes a standard-library Python implementation and a separately written audit. The underlying model version is not specified.

Tools used

OpenAI
Lyra (OpenAI-powered assistant; underlying model version not specified)

References

  1. P. Manuel and S. Klavžar, A general position problem in graph theory, Bulletin of the Australian Mathematical Society 98 (2018), 177--187. doi:10.1017/S0004972718000473 (https://doi.org/10.1017/S0004972718000473). Open text: https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S0004972718000473.DOI
  2. S. Klavžar, D. F. Rall, and I. G. Yero, General dd-position sets, Ars Mathematica Contemporanea 21 (1) (2021), #P1.03. doi:10.26493/1855-3974.2384.77d (https://doi.org/10.26493/1855-3974.2384.77d). Open published text: https://users.fmf.uni-lj.si/klavzar/preprints/2384-11213.pdf.DOI
  3. U. Chandran S. V., S. Klavžar, and J. Tuite, The General Position Problem: A Survey , arXiv:2501.19385v5 (16 August 2026). https://arxiv.org/abs/2501.19385v5.arXiv
  4. B. Courcelle, J. A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory of Computing Systems 33 (2000), 125--150. doi:10.1007/s002249910009 (https://doi.org/10.1007/s002249910009). Open text: https://www.fceia.unr.edu.ar/~daniel/OC/Apuntes/COURCELLE.pdf.DOI
  5. B. Cody and G. Moore, The kk-general dd-position problem for graphs, Discrete Applied Mathematics 366 (2025), 135--151. doi:10.1016/j.dam.2025.01.025 (https://doi.org/10.1016/j.dam.2025.01.025). Open version: https://arxiv.org/abs/2409.05644.DOI

Version history

  1. v1Submitted by Daniel Adam PyleInitial depositCurrentOct 21, 2026