## 1 Introduction  
The _Minimum-Cost Arborescence_ (MCA) problem asks to find a directed minimum-cost spanning tree (i.e., an arborescence) rooted at vertex \(r\)--the _root_ of the arborescence--in a directed graph. Chu and Liu [1] and Edmonds [2] proposed the same polynomial time algorithm to solve the problem, independently from each other. A faster implementation was later proposed by Gabow and Tarjan [3], and a different polynomial time algorithm [4] that operates directly on the cost matrix was introduced by Bock [5]. Several variations of the MCA problem were introduced in the literature since its introduction. Given a directed graph with a resource associated to each of its vertices, the _Resource-Constrained Minimum-Weight Arborescence problem_ aims at retrieving an arborescence with minimum total cost, with the additional constraint that outgoing arcs from each vertex have to have a cost at most equal to that of the resource of the vertex itself (Fischetti and Vigo [6]). Given a weighted directed graph \(G=(V,A)\) with a vertex \(r\in V\) identified as the root and an integer \(p\), the \(p\)_-Arborescence Star problem_ asks to identify a minimum-cost arborescence rooted at \(r\). The arborescence spans the set of vertices \(H\subseteq V\setminus\{r\}\) of size \(p\), and there must be an assignment between each vertex \(v\in V\setminus\{H\cup r\}\) and one of the vertices in \(H\) (Pereira et al. [7], Morais et al. [8], Hakimi [9]). Given a directed graph with a number assigned to each vertex, the _Restricted Fathers Tree problem_ seeks a minimum-cost arborescence, with the constraint that each path between a vertex and the root has to touch vertices with ranking not lower than the vertex (Guttmann-Beck and Hassin [10]). Given a directed graph with a vertex \(r\) designed as the root and a set \(A_{v}\subset V\) for every \(v\in V\setminus\{r\}\) such that \(r\in A_{v}\), the _Restricted Ancestors Tree problem_ aims at finding a minimum-cost arborescence rooted at \(r\), with the additional constraint that vertex \(i\) can be an ancestor of vertex \(j\) only when \(i\in A_{j}\) (Guttmann-Beck and Hassin [10]). The _Minimum Spanning Tree Problem with Conflict Pairs_ (Carrabs and Gaudioso [11]) is a variation of the classic _Minimum-Spanning Tree problem_ (Kruskal [12]), characterized by an undirected graph and a set containing conflicting pairs of conflicting edges. The objective is to retrieve a minimum-cost spanning tree with at most one edge from the pair in \(S\). The _Capacitated Minimum Spanning Tree problem_, introduced in Gouveia and Lopez (2013), is another variation, characterized by non-negative integer node demands \(q_{j}\) for each node \(j\in V\backslash\{r\}\) and a budget \(Q\) for the sum of the weights in any root-leaf path. Further related problems can be found in Frieze and Tkocz (2014), Fertin et al. (2015), Eswaran and Tarjan (2016), Li et al. (2017), Kawatra and Bricker (2018), Galbiati et al. (2019), Berczi et al. (2020), Bang-Jensen (2011), Yingshu et al. (2021), Carrabs et al. (2023), Darmann et al. (2014) and Viana and Campelo (2015). The _Sequential Ordering Problem_, introduced in Escudero (2016), is relevant to the present study and can be described as follows. Given a weighted graph and a set of precedence constraints between vertex pairs and start and end vertices, the goal is to find a Minimum-Cost Hamiltonian Path that respects the precedence constraints. Solving algorithms can be found in Moon et al. (2017), Balas et al. (2018), Hernadvolgyi (2019), Escudero et al. (2020), Gambardella and Dorigo (2011), Karan and Skorin-Kapov (2013), Ascheuer et al. (2013), Ascheuer et al. (2013), Ascheuer et al. (2013), Montemanni et al. (2015) and Fiala Timlin and Pulleyblank (2016). The _Precedence-Constrained Minimum-Cost Arborescence_ is an extension of the MCA problem first introduced in Dell'Amico et al. (2017). Precedence constraints have the following meaning. A precedence set \(R\) containing pairs of vertices is given.