Parametric maximum closure on precedence forests
Abstract
The Maximum Closure Problem asks for a maximum-weight closed subset of a precedence-constrained set of vertices; when vertex weights depend affinely on a scalar parameter λ, as in open-pit mine scheduling, the goal becomes computing the optimal closed set for every value of λ at once. We address this problem when the precedence graph is a directed forest. We present two algorithms (Peel-and-Contract, PaC, and its dual DPaC) that compute the full parametric solution -- a canonical sequence of disjoint closure layers inducing the nested optimal closures -- by iteratively aggregating vertices along precedence arcs, with time-complexity 𝒪(n2) for general forests and space-complexity 𝒪(n); heap-based implementations (HPaC, DHPaC) have a worse time-complexity of 𝒪(n2log n), but on random instances their computing times empirically grow as nlog n. When the forest is restricted to in-trees or out-trees, specialized heap-based variants (HIPaC, HOPaC) achieve time-complexity 𝒪(nlog n). We then present a further aggregation-based algorithm (Rake-and-Compress, RaC) with time- and space-complexity 𝒪(nlog n) also for general forests, which matches the Ω(nlog n) lower bound for comparison-based algorithms. Computational experiments on random and structured forests with up to 105 vertices characterize the practical behavior of the proposed algorithms, identify the topologies on which HPaC and RaC are preferable, and compare HPaC with the public implementation of the fully parametric pseudoflow algorithm, the state of the art for arbitrary precedence graphs, which it outperforms on forests by one to more than three orders of magnitude.
Related
- Approximation Algorithms for Maximum-Weight Degree-Bounded Forests
- On Combined Maximal Precedence–Exceedance Test with Application to HIV Clinical Trials
- PrecPack: An Efficient Open-Source Exact Solver for Bin Packing with Generalized Precedence Constraints
- Height and contour processes of Crump–Mode–Jagers forests (III): The binary, homogeneous universality class
- Unimodality of Independence Polynomials for Sufficiently Large Forests
BibTeX
@misc{dose2026parametric,
title = {{Parametric maximum closure on precedence forests}},
author = {Valerio Dose and Fabio Furini and Marco Locatelli},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.22018},
eprint = {2606.22018},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.22018},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Parametric maximum closure on precedence forests
AU - Valerio Dose
AU - Fabio Furini
AU - Marco Locatelli
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2606.22018
UR - https://arxiv.org/abs/2606.22018
AB - The Maximum Closure Problem asks for a maximum-weight closed subset of a precedence-constrained set of vertices; when vertex weights depend affinely on a scalar parameter λ, as in open-pit mine scheduling, the goal becomes computing the optimal closed set for every value of λ at once. We address this problem when the precedence graph is a directed forest. We present two algorithms (Peel-and-Contract, PaC, and its dual DPaC) that compute the full parametric solution -- a canonical sequence of disjoint closure layers inducing the nested optimal closures -- by iteratively aggregating vertices along precedence arcs, with time-complexity 𝒪(n^2) for general forests and space-complexity 𝒪(n); heap-based implementations (HPaC, DHPaC) have a worse time-complexity of 𝒪(n^2log n), but on random instances their computing times empirically grow as nlog n. When the forest is restricted to in-trees or out-trees, specialized heap-based variants (HIPaC, HOPaC) achieve time-complexity 𝒪(nlog n). We then present a further aggregation-based algorithm (Rake-and-Compress, RaC) with time- and space-complexity 𝒪(nlog n) also for general forests, which matches the Ω(nlog n) lower bound for comparison-based algorithms. Computational experiments on random and structured forests with up to 10^5 vertices characterize the practical behavior of the proposed algorithms, identify the topologies on which HPaC and RaC are preferable, and compare HPaC with the public implementation of the fully parametric pseudoflow algorithm, the state of the art for arbitrary precedence graphs, which it outperforms on forests by one to more than three orders of magnitude.
ER -