Luiz Alberto
email: luizalberto@crateus.ufc.br

Carmo Viana

Manoel Campêlo
email: mcampelo@lia.ufc.br

Ignasi Sau
email: ignasi.sau@lirmm.fr

Ana Silva
email: anasilva@mat.ufc.br

A Unifying Model for Locally Constrained Spanning Tree Problems

Given a graph G and a digraph D whose vertices are the edges of G, we investigate the problem of finding a spanning tree of G that satisfies the constraints imposed by D. The restrictions to add an edge in the tree depend on its neighborhood in D. Here, we generalize previously investigated problems by also considering as input functions ℓ and u on E(G) that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by G-DCST, while the optimization problem is denoted by G-DCMST. We show that G-DCST is NP-complete even under strong assumptions on the structures of G and D, as well as on functions ℓ and u. On the positive side, we prove two polynomial results, one for G-DCST and another for G-DCMST, and also give a simple exponentialtime algorithm along with a proof that it is asymptotically optimal under the ETH. Finally, we prove that other previously studied constrained spanning tree (CST) problems can be modeled within our framework, namely, the Conflict CST, the Forcing CST, the At Least One/All Dependency CST, the Maximum Degree CST, the Minimum Degree CST, and the Fixed-Leaves Minimum Degree CST.

Introduction

Let G be a graph and D be a (directed or undirected) graph whose vertices are the edges of G. In other terms, D defines a relation on the edge set of G. The dependencies of an edge e ∈ E(G) are given by its (in-)neighborhood in D, i.e., by the set dep D (e) = {e ′ ∈ 1 E(G) | (e ′ , e) ∈ E(D)}. We omit the subscript D in dep D (e) whenever the dependency graph is clear from the context.

Many problems have been investigated under the light of dependencies between pairs of objects, such as the knapsack problem [START_REF] Gurski | Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width[END_REF], bin-packing [START_REF] Epstein | Online variable-sized bin packing with conflicts[END_REF], maximum flow [START_REF] Pferschy | The maximum flow problem with disjunctive constraints[END_REF], scheduling problems [START_REF] Hans | On the complexity of scheduling incompatible jobs with unit-times[END_REF], maximum matchings [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], shortest paths [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], or maximum acyclic subgraphs [START_REF] Maria | On the maximum acyclic subgraph problem under disjunctive constraints[END_REF]. Generally, the dependency problems defined on graphs can be described as the problem of finding a subgraph H of G satisfying the dependency constraints imposed by D.

However, the notion of dependency itself may vary. For example, every (e, e ′ ) in D could mean that, whenever e ′ is chosen (not chosen), we get that e cannot (must) be chosen, thus expressing a conflict constraint (forcing constraint), with D being the conflict graph (forcing graph). In this paper, we introduce a generalization of dependency constrained problems, and investigate this generalization for spanning trees. In particular, our model generalizes many of the constrained spanning tree problems that have been investigated in the literature.

Our contribution. For the generalized version of dependency constrained problems, together with graph G and (di)graph D, we also consider functions ℓ and u that assign, to each e ∈ E(G), a lower and an upper bound on the number of dependencies that must be ensured for e. This means that a subgraph H ⊆ G satisfies the imposed constraints if and only if the number of edges in E(H) ∩ dep(e) is at least ℓ(e) and at most u(e), for every e ∈ E(G) 1 ; we then say that H (ℓ, u)-satisfies D. When H is asked to be a spanning tree, we call the problem the Generalized Dependency Constrained Spanning Tree problem, and denote it by G-DCST. Also, sometimes we deal with the related optimization problem by considering weights on the edges of G; this is called the Generalized Dependency Constrained Minimum Spanning Tree problem, and is denoted by G-DCMST. Let us observe that when ℓ(e) = 0 and u(e) ≥ |dep(e)|, for all e ∈ E(G), then G-DCST is equivalent to deciding whether G is connected, and G-DCMST corresponds to the classical Minimum Spanning Tree problem.

Clearly, the feasibility problem G-DCST is a particular case of the optimization problem G-DCMST, where the weight of each edge is equal to one. This is why, whenever possible, we give preference to prove NP-completeness results for the feasibility problem, and get polynomial results for the optimization problem. We use reductions from (3, 2, 2)-SAT to prove our main NP-completeness results, whereas our polynomial results arise as consequences of the Matroid Intersection Theorem [START_REF] Edmonds | Matroid intersection[END_REF] (cf. Section 2).

Considering the generalized version of the spanning tree problem, given a graph G, a digraph D = (E(G), A), and functions ℓ, u, we prove that deciding whether G has a spanning tree that (ℓ, u)-satisfies D is NP-complete in the following cases: (ii) When ℓ, u are constant functions, for every pair of constant values such that ℓ ≤ u;

(iii) When ℓ(e) = 0, and u(e) = |dep(e)| -1, for every e ∈ E(G).

On the positive side, we prove the following: It is worth observing that (a) and (i) define a dichotomy between polynomial and hard cases for G-DCST when regarding D as a family of oriented paths. It can be solved in polynomial time if length of the longest path in the underlying graph of D is at most one, and it is NP-Complete otherwise.

We also prove that many of the constrained spanning tree (CST) problems that have been investigated in the literature can be modeled with our general problem, namely the Conflict CST [START_REF] Darmann | Minimum spanning trees with conflict graphs[END_REF], the Forcing CST [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], the At Least One/All Dependency CST [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF], the Maximum Degree CST [START_REF] Deo | The shortest generalized Hamiltonian tree[END_REF], the Minimum Degree CST [START_REF] Almeida | Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[END_REF], and the Fixed-Leaves Minimum Degree CST [START_REF] Fabio | Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity, properties and formulations[END_REF]. All our reductions preserve the value of the solutions, which means that also the optimization version of these problems can be modeled within our framework.

Notice that the previously mentioned CST problems impose (vertex-wise or edge-wise) local constraints to describe their set of feasible spanning trees. This contrasts with Maximum Diameter CST [START_REF] Camerini | Complexity of spanning tree problems: Part I[END_REF][START_REF] Camerini | On the complexity of finding multi-constrained spanning trees[END_REF], Minimum Diameter CST [START_REF] Hassin | On the minimum diameter spanning tree problem[END_REF][START_REF] Ho | Minimum diameter spanning trees and related problems[END_REF] (with variations [START_REF] Baste | Parameterized complexity of finding a spanning tree with minimum reload cost diameter[END_REF][START_REF] Könemann | Approximating the degreebounded minimum diameter spanning tree problem[END_REF]) and Maximum Leaves CST [START_REF] Garey | Computers and intractability[END_REF][START_REF] Lu | The power of local optimization: Approximation algorithms for maximum-leaf spanning tree[END_REF], examples of NP-hard problems that impose constraints on global tree parameters. In [START_REF] Deo | Computation of constrained spanning trees: A unified approach[END_REF], the authors propose an approach that includes also these global constraints, but from a practical point of view.

Related work.

In what follows, we talk sometimes about the feasibility version of the problems, and sometimes about the optimization version, where also a weight function on the edges of the input graph is given. Also, when ℓ and/or u are constant functions, we write directly the constant value inside the parenthesis when saying whether a spanning tree (ℓ, u)-satisfies D.

strained spanning tree problem (and therefore, as a special case of G-DCST) is the so-called Angular Constrained Spanning Tree problem [START_REF] Aschner | Bounded-angle spanning tree: Modeling networks with angular constraints[END_REF]. In this problem, we are given a set V of points on the plane, a graph G = (V, E), and an angle α. A spanning tree T is called an α-spanning tree if, for every point v ∈ V , there is an angle on v of size smaller than α containing all the edges (line segments) of T incident to v. Observe that, if we let D contain an arc (vu, vw) whenever the smaller angle formed by vu and vw is bigger than α, then an α-spanning tree T also (0, 0)-satisfies D, and vice-versa. Besides, the conflicts in this case are forbidden transitions. In [START_REF] Aschner | Bounded-angle spanning tree: Modeling networks with angular constraints[END_REF], one can find references on the decision version of the problem, while the optimization version is investigated in [START_REF] Salles | Modeling and solving the angular constrained minimum spanning tree problem[END_REF].

Forcing constraints: Recall that, in the Forcing Constrained (Minimum) Spanning Tree problem, we are given a pair of graphs G and D such that V (D) = E(G), and we want to know whether there exists a spanning tree (find a minimum spanning tree) T of G such that E(T ) ∩ {u, v} = ∅ for every uv ∈ E(D). We denote the feasibility problem by FCST and the optimization problem by FCMST.

This problem was introduced in [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], where the authors prove that FCST is NP-complete even if the conflict graph is a forest of paths of length at most two. To the best of our knowledge, this is the only existing paper that investigates this problem. Here, we show a reduction from FCST(G, D) to G-DCST(G ′ , D ′ , ℓ, u), where ℓ(e) ∈ {0, 1} and u(e) = |dep(e)| for every e ∈ E(G ′ ), and the maximum in-degree of D ′ is 2. If weights are being considered, such a reduction can be made to preserve the value of the solutions, and therefore it also applies to the optimization problem.

At least one/all dependency constraints:

The following two dependency constrained problems are introduced in [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF]. Given a graph G and a digraph D such that V (D) = E(G), one wants to know whether there exists a spanning tree T of G such that: E(T )∩dep(e) = ∅ for every e ∈ E(T ) with dep(e) = ∅, called the At Least One Dependency Constrained Spanning Tree problem; or dep(e) ⊆ E(T ) for every e ∈ E(T ), called the All Dependency Constrained Spanning Tree problem. We denote these problems by L-DCST and A-DCST, and the related optimization problems by L-DCMST and A-DCMST, respectively. Note that these are special cases of our problem.

In [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF], it is proved that both L-DCST and A-DCST are NPcomplete, even if G is a planar chordal graph with diameter two or maximum degree three, and D is the disjoint union of arborescences of height two. Here, we strengthen the constraints on D, while also getting a lower bound on the running time of exponential algorithms for these problems (result (i)). Observe that this result comprises cases where the maximum in-degree of D is one, and so the generalized problem coincides with both L-DCST and A-DCST.

Still in [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF], the authors prove that L-DCMST and A-DCMST are W[2]-hard when parameterized by the weight of a solution, and that, unless P = NP, they cannot be approximated with a ratio of ln |V (G)| even if: G is bipartite; the dependency relations occur only between adjacent edges of G; and each weak component of D has diameter one. One can notice that the weight of a solution in their W[2]-hardness reduction is O(n), where n = |V (G)|. This means that there is no FPT algorithm for L-DCMST and A-DCMST parameterized by n, unless FPT = W [START_REF] Akgün | Min-degree constrained minimum spanning tree problem: New formulation via Miller-Tucker-Zemlin constraints[END_REF]. This contrasts with the decision problem, which can be solved in time

O(2 m • (n + m)) = O(2 n 2 • n 2 ), where m = |E(G)| (result (c)).
Maximum degree constraints: Given a graph G = (V, E), and a positive integer k, the Maximum Degree Constrained Spanning Tree problem consists in deciding whether G has a spanning tree T such that d T (v) ≤ k for every v ∈ V (G), where d T (v) is the degree of v in T . This problem was introduced in [START_REF] Deo | The shortest generalized Hamiltonian tree[END_REF]. Observe that it is NP-complete, even for k = 2, since this case generalizes the Hamiltonian path problem [START_REF] Garey | Computers and intractability[END_REF]. In [START_REF] Papadimitriou | On two geometric problems related to the travelling salesman problem[END_REF], it is proved to be NP-complete even for grid graphs of maximum degree three. Also, [START_REF] Papadimitriou | On two geometric problems related to the travelling salesman problem[END_REF] tackles the Euclidean optimization version of the problem (i.e., vertices are points on the plane, and edges are weighted according to the Euclidean distance). The Euclidean optimization version remains NP-hard when k ≤ 3, and is polynomial-time solvable when k ≥ 5, remaining open for k = 4. Several heuristic, approximation, and exact approaches have been proposed for the problem (see [START_REF] Luis | Branch-andcut-and-price algorithms for the degree constrained minimum spanning tree problem[END_REF][START_REF] Krishnamoorthy | Comparison of algorithms for the degree constrained minimum spanning tree[END_REF][START_REF] Singh | Approximating minimum bounded degree spanning trees to within one of optimal[END_REF] and references therein).

Here, we denote the feasibility version of this problem by MDST, and the optimization version by MDMST. We present a reduction from MDST(G, k) to G-DCST(G ′ , D, 0, u) where u(e) ∈ {0, k} for every e ∈ E(G ′ ). The reduction also applies to the optimization problem since it preserves the value of the solutions.

Minimum degree constraints: Given a graph G = (V, E), and a positive integer k, the Minimum Degree Constrained Spanning Tree problem consists in deciding whether G has a spanning tree T such that d T (v) ≥ k for every non-leaf vertex v of T . Here, we denote the feasibility version of this problem by mDST, and the optimization version by mDMST. This problem was introduced in [START_REF] Almeida | Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[END_REF], where it is shown to be NP-hard for every

k ∈ {4, • • • , |V (G)|
2 }. On the other hand, [START_REF] Almeida | Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[END_REF] proves that the problem can be solved (by inspection) for degree bounds between |V (G)| 2 + 1 and |V (G)| -1. In [START_REF] Almeida | md-MST is NP-hard for d ≥ 3[END_REF], the problem was shown to be NP-hard for k = 3. The case k ≤ 2 is equivalent to the classical spanning tree problem. Integer linear programs and solution methods were proposed in [START_REF] Akgün | Min-degree constrained minimum spanning tree problem: New formulation via Miller-Tucker-Zemlin constraints[END_REF][START_REF] Almeida | Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[END_REF][START_REF] Conegundes | The min-degree constrained minimum spanning tree problem: Formulations and branch-and-cut algorithm[END_REF].

An interesting variation of mDST is obtained when the set of leaves is fixed in the input. More formally, given a graph G, a subset C ⊆ V , and a positive integer k, it consists in finding a spanning tree T of G such that d T (v) ≥ k, for every v ∈ C, and d T (v) = 1, for every v ∈ V \ C. We denote the feasibility version of this problem by FmDST, and the optimization version by FmDMST. This problem was introduced in [START_REF] Fabio | Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: Complexity, properties and formulations[END_REF], where the authors prove that FmDST is NP-complete for k ≥ 2, and FmDMST is NP-hard even for complete graphs. Also, some necessary and sufficient conditions are given for feasibility.

Here, we present a reduction from both mDST(G, k) and FmDST(G, C, k) to G-DCST(G ′ , D, ℓ, u) where ℓ(e) ∈ {0, 1, k} and u(e) ∈ {1, |dep(e)|} for every e ∈ E(G).

Again, our reduction preserves the values of the solutions and therefore works for the optimization version as well.

Applications. As G-DCST generalizes all these problems, it inherits their applications, such as design of wind farm networks [START_REF] Carrabs | A multiethnic genetic approach for the minimum conflict weighted spanning tree problem[END_REF], VLSI global routing [START_REF] Robins | Low-degree minimum spanning trees[END_REF], or low-traffic communication networks [START_REF] Conegundes | The min-degree constrained minimum spanning tree problem: Formulations and branch-and-cut algorithm[END_REF]. In particular, dependency relations can model communication systems with protocol conversion restrictions [START_REF] Luiz | Árvore geradora com dependências mínima[END_REF]. Besides, we can get unified results for all of them by considering G-DCST.

Organization. In Section 2, we present the formal definitions and notation used throughout the paper; in Section 3 we present our NP-complete results; in Section 4, our positive results; in Section 5, we show how to model the many constrained spanning tree problems as special cases of our problem; and in Section 6, we discuss our results and pose some open questions.

Definitions and notation

Graphs. For missing basic definitions on graph theory, we refer the reader to [START_REF] West | Introduction to graph theory[END_REF]. Let G be a simple graph (henceforth called simply a graph), and D be a digraph. We denote by E(G), E(D) the edge set of G and arc set of D, respectively. Also, we denote an edge {u, v} of G by uv, and arc with head v and tail u of D by (u, v). We say that

D is symmetric if (v, u) ∈ E(D) whenever (u, v) ∈ E(D). A (di)graph G (D) is complete if uv ∈ E(G) ({(u, v), (v, u)} ⊆ E(D))
for every pair of vertices u and v in G (D). It is empty if has no edges (no arcs).

If C ⊆ V (G) is such that uv ∈ E(G) for every u, v ∈ V (G), u = v, then we call C a clique. And if there are no edges between vertices in C, we say that C is an independent set.

A vertex v ∈ V (G) is called universal if N (v) = V (G) \ {v},
where N (v) stands for the set of neighbors of v. A tree T is called a star if it has a universal vertex v, called center. Similarly, an out-star (in-star ) is a directed graph D with a vertex v such that any other vertex is an out-neighbor (in-neighbor) of v and V (D) \ {v} is an independent set.

Definition of the problems. Let G = (V, E) be a graph and D = (E, A) be a digraph whose vertices are the edges of G. We say that e 1 ∈ E is a D-dependency of e 2 ∈ E if (e 1 , e 2 ) ∈ A. For each e ∈ E, we define its D-dependency set as dep D (e) = {e ′ ∈ E : (e ′ , e) ∈ A}, and for

E ′ ⊆ E, let dep D (E ′ ) = ∪ e∈E ′ dep D (e)
; from now on we omit D from the subscript whenever it is clear from the context. Also, let ℓ, u : E → N be functions that assign a non-negative integer to each edge of G. We say that a subgraph H of G (ℓ, u)-satisfies D if ℓ(e) ≤ |dep(e) ∩ E(H)| ≤ u(e), for every e ∈ E(H).

We introduce the Generalized Dependency Constrained Spanning Tree problem as, given a graph G, a digraph D = (E(G), A), and functions ℓ, u : E(G) → N, deciding whether there exists a spanning tree T of G such that T (ℓ, u)-satisfies D. We abbreviate this with G-DCST(G, D, ℓ, u). Observe that it corresponds to the feasibility problem. If we are also given a weight function w : E → R, then we define the Generalized Dependency Constrained Minimum Spanning Tree problem as the problem of finding a spanning tree T * of G that minimizes the weight sum and that (ℓ, u)-satisfies D; this problem is denoted by G-DCMST.

Polynomial reductions and Exponential Time Hypothesis. Given problems Π and Π ′ , we write Π P Π ′ if there exists a polynomial reduction from Π to Π ′ . This means that problem Π ′ is at least as hard as problem Π. The Exponential Time Hypothesis (denoted by ETH) of Impagliazzo et al. [START_REF] Impagliazzo | On the Complexity of k-SAT[END_REF][START_REF] Impagliazzo | Which Problems Have Strongly Exponential Complexity[END_REF] states that the 3-SAT problem cannot be solved in time 2 o(n+m) , where n is the number of variables and m the number of clauses of the input formula. In particular, if it is possible to reduce 3-SAT to problem Π and the produced instance has size linear in the size of the input formula, then the ETH implies that problem Π cannot be solved in time 2 |x| either, where |x| denotes the size of the input of Π. We refer the reader to [START_REF] Arora | Computational Complexity: A Modern Approach[END_REF] for basic background on computational complexity.

Parameterized complexity. We refer to [START_REF] Cygan | Parameterized Algorithms[END_REF] for a recent monograph on parameterized complexity. Here, we recall only some basic definitions. A parameterized problem is a decision problem whose instances are pairs (x, k) ∈ Σ * × N, where k is called the parameter. A parameterized problem L is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f , and a constant c such that, given an instance I = (x, k) of L, we get that A (called an FPT algorithm) correctly decides whether I ∈ L in time bounded by f (k) • |I| c . For instance, the Vertex Cover problem parameterized by the size of the solution is FPT.

Within parameterized problems, the class W[1] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF] for the formal definitions), a parameterized problem being W[1]-hard can be seen as a strong evidence that this problem is not FPT. The canonical example of W[1]-hard problem is Independent Set parameterized by the size of the solution. The class W [START_REF] Almeida | Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[END_REF] of parameterized problems is a class that contains W [START_REF] Akgün | Min-degree constrained minimum spanning tree problem: New formulation via Miller-Tucker-Zemlin constraints[END_REF], and such that the problems that are W [START_REF] Almeida | Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations[END_REF]-hard are even more unlikely to be FPT than those that are W[1]-hard (again, see [START_REF] Cygan | Parameterized Algorithms[END_REF] for the formal definitions). The canonical example of W[2]-hard problem is Dominating Set parameterized by the size of the solution.

Matroids. We state here some basic tools about matroids that we will use in the algorithms of Section 4, and we refer to [START_REF] Lawler | Combinatorial optimization: Networks and matroids[END_REF][START_REF] Oxley | Matroid theory[END_REF] for more background. A (finite) matroid M is a pair (E, I), where E is a finite set, called the ground set, and I is a family of subsets of E, called the independent sets, satisfying the following properties:

1. The empty set is independent, that is, ∅ ∈ I.

Every subset of an independent set is independent, that is, for each

A ′ ⊆ A ⊆ E, if
A ∈ I then A ′ ∈ I. This is called the hereditary property.

3. If A, B ∈ I with |A| > |B|, then there exists x ∈ A \ B such that B ∪ {x} ∈ I. This is called the augmentation property.

Every graph or multigraph G = (V, E) gives rise to a so-called graphic matroid having E as ground set, and a set

F ⊆ E is independent if and only if G[F ] is acyclic. Given a collection E = {E 1 , E 2 , . . . , E k } of pairwise disjoint sets, and integers {d 1 , . . . , d k } such that 0 ≤ d i ≤ |E i | for every i ∈ [k] = {1, . . . , k}, the partition matroid with ground set E = k i=1 E i has S ⊆ E as an independent set if and only if |S ∩ E i | ≤ d i for every i ∈ [k].
The Matroid Intersection Theorem, proved by Edmonds [START_REF] Edmonds | Matroid intersection[END_REF], states that the problem of finding a largest common independent set of two matroids over the same ground set can be solved in polynomial time.

NP-completeness results

In this section, we present our NP-complete results. First, we impose in Section 3.1 constraints on the structure of D (also getting constraints on G as a byproduct), and then we focus in Section 3.2 on hardness results imposing constraints on functions ℓ and u.

Constraints on D

We prove result (i). First, we consider the case where D is a forest of out-stars with at most three vertices. Later we show that the orientation of D in the reduction can be changed to get a forest of directed paths of length at most two. In addition, in Theorem 3, we modify the reduction to obtain D as a forest of in-stars with at most three vertices, thus closing all the possible orientations of forest of paths of length at most two. Proof. Notice that, given a spanning tree T , one can check whether T (ℓ, u)-satisfies D in polynomial time; hence, G-DCST(G, D, ℓ, u) is in NP. To prove NP-completeness, we present a reduction from (3, 2, 2)-SAT to G-DCST. In the (3, 2, 2)-SAT problem, we are given a CNF formula φ where each clause has at most three literals, and each variable appears at most twice positively and at most twice negatively. This problem is well-known to be NP-complete [START_REF] Cook | The complexity of theorem-proving procedures[END_REF][START_REF] Garey | Computers and intractability[END_REF]. So consider a CNF formula φ on n variables and m clauses; we build an instance (G, D, ℓ, u) of G-DCST as follows (follow the construction in Figure 1):

• Add to G vertex v, and vertices v x , v x, and w x related to each variable x, and at most three vertices {v 1 c , v 2 c , v 3 c } related to each clause c (these vertices represent the literals in c). Then, make v adjacent to every other vertex; v x adjacent to v x for every variable x; and add for each clause c a path (v

1 c , v 2 c ) or (v 1 c , v 2 c , v 3 c
), depending on how many literals c has (observe that we can suppose that c has at least two literals). Edge vv x will be interpreted as the true assignment of x, while edge vv x as the false one.

• For each variable x, add arc (v x v x, vw x ) to D. For every variable x and each occurrence of x in a clause c, say as the i-th literal in c, add to D arc (vv x , vv i c ) if x appears positively in c, or arc (vv x , vv i c ) if x appears negatively in c.

• Finally, let ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G). In Figure 1(a), we represent a variable gadget together with a gadget of a clause containing three literals. In Figure 1(b), for a variable x, we represent the dependency between v x v x and vw x , and also the arcs leaving vv x and vv x when x appears positively in c 1 and c 2 , and negatively in c 3 , being related to the first literal in each of these clauses.

v x v w x v x v 1 c v 2 c v 3 c (a) Graph G. v x v x vw x vv x vv 1 c 1 vv 1 c 2 vv x vv 1 c 3 (b) Digraph D.
One can see that G is an outerplanar chordal graph, and that each component (different from the one containing v x v x and vw x ) of D is an out-star from vv x or vv x, for some variable x; we get ∆ + (D) ≤ 2 by the constraint in the number of appearances of a literal.

To show the correctness of the reduction, consider first a satisfying assignment of φ. We build a spanning tree T of G with the following edges: for each variable x, add to T v x v x, vw x , and either

vv x if x is true, or vv x, if x is false; for each clause c = (ℓ 1 ∨ ℓ 2 ∨ ℓ 3 ), add path (v 1 c , v 2 c , v 3 c
) and an edge vv i c for some i ∈ {1, 2, 3} such that ℓ i is a true literal (analogously when c has only two literals). Because, for every variable x, vw x , v x v x and exactly one edge among {vv x , vv x} are chosen, and for every clause c exactly one edge among

{vv 1 c , vv 2 c , vv 3 c } is chosen, apart from the path (v 1 c , v 2 c , v 3 c ), one can see that T is
indeed a spanning tree of G. The dependencies can also be seen to be satisfied since we only choose an edge vv i c if the corresponding literal is true (hence the dependency is chosen too).

Conversely, let T be a solution for G-DCST(G, D, ℓ, u). For each variable x, because vw x is a cut edge and (v x v x, vw x ) ∈ E(D), we get that {vw x , v x v x} ⊆ E(T ). Besides, for each variable x, since vv x and vv x form a cut and also form a cycle with v x v x, we get that exactly one between vv x and vv x is in T . We then assign x to true if vv x ∈ E(T ), and to false otherwise. Now, consider a clause c = (ℓ 1 ∨ ℓ 2 ∨ ℓ 3 ); since the edges {vv 1 c , vv 2 c , vv 3 c } form a cut, at least one of them is in T , say vv 1 c ∈ E(T ) and say that x is the variable related to ℓ 1 . If ℓ 1 = x, then (vv x , vv 1 c ) ∈ E(D), which implies that vv x ∈ E(T ) and that x is true. And if ℓ 1 = x, then (vv x, vv 1 c ) ∈ E(D), which implies that vv x ∈ E(T ) and that x is false (therefore ℓ 1 is true). In any case, c is satisfied. The case where c has only two literals is analogous.

Finally, for the lower bound 2 o(n+m) , just observe that the constructed instance has size linear in the size of the given formula.

Observe that when either ∆ -(D) = 0 or ∆ + (D) = 0, we get that D is the empty graph, and that G-DCST(G, D, ℓ, u) reduces to deciding whether G is connected. Also, by the previous theorem, we get that the problem is NP-complete if ∆ -(D) = 1, thus giving us a dichotomy with regard to the value of ∆ -(D). Concerning ∆ + (D), the previous theorem tells us that the problem becomes NP-complete for ∆ + (D) = 2. With a small modification on the previous reduction, we can also get a dichotomy with regard to ∆ + (D). Proof. Consider the same construction from the Theorem 1, except that each out-star with two leaves is turned into a directed path of length two. Observe that if (vv i c , uv x , vv j c ′ ) is a path in D, then the previous arguments might not work simply because we might be forced to pick edge vv i c when variable x is set to true (i.e., edge uv x is chosen). However, in this case we can remove some of the edges of the path (v 1 c , v 2 c , v 3 c ) in order to avoid cycles. A similar argument is made for out-stars containing a vertex of type vv x .

Recall that L-DCST(G, D) and A-DCST(G, D) denote the dependency constrained spanning tree problem (G-DCST) where at least one dependency (if any exists) or all dependencies are satisfied, respectively. Also, note that, if ∆ -(D) ≤ 1, then we get that L-DCST(G, D) and A-DCST(G, D) coincide with G-DCST(G, D, ℓ, u) by assigning ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G). Thus, the following corollary, which strengthens the results in [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF], is a direct consequence of the previous two theorems. In [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], it is shown that CCMST is NP-complete if the conflict graph is a forest of paths of length at most two. An orientation of such a forest may lead to directed paths, out-stars, or in-stars. The NP-completeness of G-DCST in the first two cases is proved in Theorems 1 and 2. The case of in-stars is approached next. Proof. Notice that a spanning tree T of G can be checked to (l, u)-satisfy D in polynomial time, thus G-DCST(G, D, ℓ, u) is in NP. To prove NP-completeness, we again make a reduction from (3, 2, 2)-SAT to G-DCST. This way, consider a CNF formula φ on n variables and m clauses. We build an instance (G, D, ℓ, u) of G-DCST as follows (see Figure 2):

v v x v x w x (a) Graph G (variable gad- get). v a ℓ i c b ℓ i c w ℓ i c v ℓ 1 c v ℓ 2 c v ℓ 3 c (b) Graph G (clause gad- get). vw x v x v x a ℓ i c b ℓ i c vw ℓ i c va ℓ i c vv ℓ i c vb ℓ i c vv ℓ i (
• Start by adding a vertex v, which will be universal. For each variable x, add to G vertices v x , v x , and w x , making them adjacent to v, and add edge v x v x ; see Figure 2(a). Selecting edge vv x will correspond to the true assignment for x, and vv x to the false one.

• For each clause c = (ℓ 1 ∨ℓ 2 ∨ℓ 3 ) with three literals, add to G vertices

{v ℓ i c , a ℓ i c , b ℓ i c , w ℓ i c | i ∈ [3]},
and make them adjacent to v. Then, add path (v ℓ 1 c , v ℓ 2 c , v ℓ 3 c ), and edges

{a ℓ i c b ℓ i c | i ∈ [3]}; see Figure 2(b)
. Proceed analogously if c has two literals. For each literal ℓ i , selecting edge va ℓ i c will indicate that c is satisfied by ℓ i , and selecting edge vb ℓ i c will indicate that c must be satisfied by some of its other literals.

• For each variable x, add arc (v x v x , vw x ) to D. For each clause c and each literal ℓ i of c, add arcs (a ℓ i c b ℓ i c , vw ℓ i c ), (va ℓ i c , vv ℓ i c ), and (vb ℓ i c , vv ℓ i ) to D; see Figure 2(c).

• Finally, let ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G).

Observe that G is an outerplanar chordal graph, and that each component of D is an in-star. We get ∆ -(D) ≤ 2 by the constraint in the number of appearances of a literal.

To show the correctness of the reduction, consider first a satisfying assignment of φ. We build a spanning tree T of G as follows. For each variable x, choose edges v x v x and vw x ; then choose edge vv x if x is true, and edge vv x otherwise. For each clause c with three literals, add edges

{a ℓ i c b ℓ i c , vw ℓ i c | i ∈ [3]}. Also, for each i ∈ [3], add {vv ℓ i c , va ℓ i c } if ℓ i is true; otherwise, add vb ℓ i c . Finally, use path (v ℓ 1 c , v ℓ 2 c , v ℓ 3 c
) to connect any possibly disconnected vertex. Proceed analogously if c has two literals. Denote by X the set of variables of φ, and by C the set of clauses; also, write ℓ i ∈ c to denote the fact that literal ℓ i appears in c. We first show that T is a spanning tree of G. It is easy to see that T spans {v x , v x , v, w x | x ∈ X}, and also every vertex of degree 1 in G. Now, given a clause c, because each literal ℓ i in c is either true or false, we get that either va ℓ i c or vb ℓ i c is in T , and since a ℓ i c b ℓ i c ∈ E(T ) we get that T also spans

{a ℓ i c , b ℓ i c | c ∈ C, ℓ i ∈ c}.
Finally, for each clause c, we know that at least one of its literals is true, which means that at least one of the edges linking the path (v ℓ 1 c , v ℓ 2 c , v ℓ 3 c ) to v is chosen, and since it is always possible to choose edges from this path to connect any possible remaining disconnected vertex, we are done. Now, we prove that dependencies are satisfied. Dependencies in

{(v x v x , vw x ) | x ∈ X}, and in {(a ℓ i c b ℓ i c , vw ℓ i c ) | c ∈ C, ℓ i ∈ c}
are all satisfied since all the involved edges are contained in T . Dependencies in {(va ℓ i c , vv ℓ i c ) | c ∈ C, ℓ i ∈ c} are also valid because we only add these edges together. Finally, given a variable x, if x is true, then we choose edge vv x , and vb ℓ i c for each clause c such that x is the i-th literal of c; and if x is false then we choose edge vv x , and vb ℓ i c for each clause c such that x is the i-th literal of c. This settles the last type of dependencies.

Conversely, let T be a solution for G-DCST(G, D, ℓ, u). For each variable x, because vw x is a cut edge and (v x v x , vw x ) ∈ E(D), we get that {vw x , v x v x } ⊆ E(T ). Besides, for each variable x, since vv x and vv x form a cut and also form a cycle with v x v x , we get that exactly one between vv x and vv x is in T . We then assign x to true if vv x ∈ E(T ), and to false otherwise. Now, consider a clause c = (ℓ 1 ∨ ℓ 2 ∨ ℓ 3 ); since the edges {vv ℓ 1 c , vv ℓ 2 c , vv ℓ 3 c } form a cut, at least one of them is in T , say vv ℓ 1 c ∈ E(T ). Hence, because (va

ℓ 1 c , vv ℓ 1 c ) ∈ A(D), we get that va ℓ 1 c ∈ E(T ). But then, since a ℓ 1 c b ℓ 1 c ∈ E(T ), we have that vb ℓ 1 c / ∈ E(T ), which in turn implies that vv ℓ 1 /
∈ E(T ) because of the dependency (vb ℓ 1 c , vv ℓ 1 ). We then conclude that vv ℓ 1 must be chosen, henceforth ℓ 1 is a true literal in c. The case where c has only two literals is analogous.

Finally, since the constructed instance has size linear in the size of φ, we obtain the claimed lower bound 2 o(n+m) under the ETH.

Let us observe that, similarly to Corollary 1, the results in Theorem 3 can be stated to A-DCST(G, D), since this problem is equivalent to G-DCST(G, D, dep, dep). This also extends the achievements from [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF].

Constraints on functions ℓ and u

In this subsection, we examine the complexity of G-DCST(G, D, ℓ, u) by focusing on functions ℓ and u. Recall that, given constants c, c ′ , G-DCST(G, D, c, c ′ ) denotes the problem restricted to instances where ℓ(e) = c and u(e) = c ′ for every e ∈ E(G). Given a function f : E → N and a positive integer c, we denote by f + c the function obtained from f by adding c to f (e) for every e ∈ E. The following lemma will be useful. Proof. Choose any v ∈ V (G), and let G ′ be obtained from G by adding ℓ + c + 1 vertices of degree one pending in v; denote the new edges by e 1 , . . . , e ℓ+c+1 . Now, add the symmetric clique on vertices {e 1 , . . . , e ℓ+c+1 } to D, and add e i e to D, for every i ∈ [c] and every e ∈ E(G). Let G ′ and D ′ be the obtained graph and digraph, respectively. Finally, let ℓ ′ (e) = ℓ + c and u ′ (e) = u + c, for every e ∈ E(G ′ ). We prove that (G,

D, ℓ, u) is a yes-instance of G-DCST if and only if (G ′ , D ′ , ℓ ′ , u ′ ) is a yes-instance of G-DCST.
First, let T be a spanning tree of G that (ℓ, u)-satisfies D. Let T ′ be obtained from T by adding e 1 , . . . , e ℓ+c+1 . Clearly T ′ is a spanning tree of G ′ ; we prove that T ′ (ℓ ′ , u ′ )-satisfies First, we analyze the cases where ℓ = 0. Recall that in CCST, whenever an edge e is chosen, no dependencies of e can be chosen; this translates to having ℓ(e) = u(e) = 0 for every e ∈ E(G). So in a sense, when one considers instances (G, D, ℓ, u) of G-DCST where ℓ(e) = 0 for each e ∈ E(G), one can think of the problem as a "weak" version of CCST. It thus makes sense to ask whether this version turns out to be polynomial. Indeed, we notice that G-DCST(G, D, ℓ, u) with ℓ = 0 and u(e) ≥ |dep D (e)|, for each e ∈ E(G), is an easily solvable problem since every spanning tree of G trivially (ℓ, u)-satisfies D. In the following theorem, we see that this is not the case when u is a constant function. Proof. Recall that CCST(G, D) is NP-complete [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF] and equivalent to G-DCST(G, D ′ , 0, 0) when D ′ is an arbitrary orientation of D. Given an instance (G = (V, E), D) of CCST, where D is an undirected graph with V (D) = E, we construct and equivalent instance (G ′ , D ′ , 0, c) of G-DCST as follows (cf. Figure 3)

D ′ . Let e ∈ E(G ′ ). If e ∈ E(
• Let G ′ be obtained from G by adding a new vertex p and, for each i ∈ [c] and each edge e ∈ E(G), adding a new vertex p i e . Then, make p adjacent to every p i e , and to an arbitrary vertex q ∈ V (G). More formally, G ′ = (V ∪ V ′ , E ∪ E ′ ), where

V ′ = {p} ∪ {p i e : e ∈ E, i ∈ [c]
} and

E ′ = {pq} ∪ {pp i e : e ∈ E, i ∈ [c]}.
• Let D ′ be obtained from an arbitrary orientation of D by adding an arc (pp i e , e) for every e ∈ E(G) and every i ∈ [c].

The constructed instance has size clearly polynomial on the size of (G, D)

(recall that c is a constant). Note that G ′ [V ′ ∪ {q}] is a star. Now, we show that (G, D) is a yes-instance of CCST if and only if (G ′ , D ′ , 0, c) is a yes-instance of G-DCST.
First, let T be a solution for CCST(G, D), and let T ′ be obtained from T by adding E ′ . Clearly T ′ is a spanning tree of G ′ ; hence it remains to show that T ′ (0, c)-satisfies D ′ . For this, consider e ∈ E(T ′ ). If e ∈ E(T ), then because T (0, 0)-satisfies D, we have that Conversely, let T ′ be a spanning tree of G ′ that (0, c)-satisfies D ′ , and let T = T ′ [V ]. Because p separates V ′ \ {p} from V , we know that T is connected and, therefore, it is a spanning tree of G; so it remains to show that T (0, 0)-satisfies D. For this consider e ∈ E(T ). Since each edge in E ′ is a cut edge in G ′ , we get that E ′ ⊆ E(T ′ ).

E(T ′ ) ∩ dep D ′ (e) = {pp

Positive results

In this section, we present some polynomial cases of the G-DCST problem. Whenever possible, we deal with the optimization version instead, i.e., we consider that we are also given a weight function w and that the objective is to find a spanning tree that (ℓ, u)-satisfies D having minimum weighted sum-weight. This is denoted by G-DCMST(G, D, ℓ, u, w).

Similarly to the previous section, we first focus in Section 4.1 on constraints on the dependency graph D, and then in Section 4.2 on constraints on the functions ℓ and u. Finally, we present in Section 4.3 a simple exponential-time algorithm to solve the problem.

Constraints on D

We start by investigating the case where D is a collection of directed paths of length at most one (note that there might be some edges of G that are isolated vertices in D). So, given a graph G = (V, E) and a digraph D = (E, A), write E as {e 1 , . . . , e m } and assume that A = {(e i , e i+t ) : i ∈ {1, . . . , t}}, for some t ≤ ⌊ m 2 ⌋. Let S = {e i : i ∈ {t + 1, . . . , 2t}}, i.e., S is the set of the edges e ∈ E(G) with dep(e) = ∅. The idea is to find a subset of edges S ′ ⊆ S that connects the components of G -S and such that the dependencies of S ′ do not form a cycle in G. Let C = {C 1 , . . . , C k } be the set of connected components of G -S, and let H be the multigraph obtained from G by contracting each C i to a single vertex (loops are removed). Observe that there is an injection from the multiedges of H to the edges in S. Hence, given S ′ ⊆ S, we can pick H(S ′ ) to be the subgraph of H induced by S ′ , i.e., H(S ′ ) has C as vertex set, and there is an edge between C i , C j , i = j, for each edge e ∈ S ′ with one endpoint in C i and the other one in C j . Observe that some of the edges of S might appear inside a component. However, as we will see, these edges can actually be ignored, and this is why we do not need to add the loops in H. Proof. First, consider S ′ ⊆ S such that H(S ′ ) is a spanning tree of H and (V, dep(S ′ )) is acyclic. Observe that, because (V, dep(S ′ )) is acyclic, S ′ ⊆ S, and S ∩ dep(S ′ ) = ∅, we get that each C i is a connected component of G -S. Thus, we can add edges of G -S to (V, dep(S ′ )) so as to obtain a spanning forest F of G having connected components with the same vertex sets as C 1 , . . . , C k . After this, just add edges of S ′ to F ; because H(S ′ ) is a spanning tree of H, we get that the obtained graph T connects all components of F without forming a cycle (i.e., T is a spanning tree of G). Finally, since dep(S ′ ) ⊆ E(T ) and S ∩ E(T ) = S ′ , we get that T satisfies D.

Conversely, let T = (V, E T ) be a feasible solution of DCST(G, D). As T is a spanning tree of G, we get that the edges in E T ∩ S must connect the components of G -S, i.e., H(E T ∩S) is connected. Thus, choose S ′ as the edge set of any spanning tree of H(E T ∩S). We get that S ′ also forms a spanning tree of H, and since S ′ ⊆ E T and T satisfies D, we get that dep(S ′ ) ⊆ E T and therefore (V, dep(S ′ )) cannot contain a cycle.

In the following theorem we use the Matroid Intersection Theorem [START_REF] Edmonds | Matroid intersection[END_REF] to get result (a).

Theorem 5. Let G = (V, E) be a graph, D = (E, A) be a digraph such that each component is a directed path of length at most 1, and ℓ, u be such that ℓ(e) = u(e) = |dep(e)| ∈ {0, 1} for every e ∈ E(G). Then DCST(G, D) can be solved in polynomial time.

Proof. Given E ′ ⊆ E(G), denote by G(E ′ ) the subgraph (V (G), E ′ ). Let H be ob- tained as before. Also, let I 1 = {S ′ ⊆ S | G(dep(S ′ )) is acyclic} and I 2 = {S ′ ⊆ S | H(S ′
) is acyclic}. We have that (S, I 1 ) and (S, I 2 ) are matroids (on a common ground set S), since they are equivalent to the graphic matroids of the graph (V, dep(S)) and of the multigraph H, respectively. According to Lemma 2, DCST(G, D) is feasible if and only if there is

S ′ ∈ I 1 ∩ I 2 such that |S ′ | = k -1,
where k is the number of components of G ′ = (V, E \ S). The existence of such S ′ can be checked in polynomial time using the Matroid Intersection Theorem [START_REF] Edmonds | Matroid intersection[END_REF].

Constraints on ℓ and u

Recall that CCMST(G, G c , w) is equivalent to G-DCMST(G, D, 0, 0, w) when D is a symmetric digraph. From a result in [START_REF] Zhang | The minimum spanning tree problem with conflict constraints and its variations[END_REF] for the CCMST problem, we get that G-DCMST(G, D, 0, 0, w) is solvable in polynomial time when D is the union of complete digraphs. We generalize this result for upper bound functions that have the same value on each clique (result (b)).

Theorem 6. Let (G, D, 0, u, w) be an instance of G-DCMST such that D = D 1 ∪D 2 ∪• • •∪D k is the union of k disjoint complete digraphs and, for each i ∈ [k], there exists u i ∈ [|V (D i )|] such that u(e) = u i -1 for every e ∈ V (D i ).
Then, G-DCMST(G, D, 0, u, w) can be solved in polynomial time.

Proof. Note that, in this case, a solution for G-DCMST(G, D, 0, u, w) can have at most u i edges from D i , for each i ∈ [k]. We show that solving such an instance can be formulated as a matroid intersection problem.

Observe that a subgraph T of G (0, u)-satisfies D if and only if

|E(T )∩D i | ≤ u i for every i ∈ [k].
Therefore, if M is the partition matroid on E(G) defined by {V (D 1 ), . . . , V (D k )} and {u 1 , . . . , u k }, we get that T ⊆ G is a solution for our problem if and only if T is a spanning tree of G and E(T ) is an independent set of M . Hence, if M ′ is the graphic matroid associated with G (where the independent sets are the sets of edges inducing a spanning tree of G), we can solve our problem in polynomial time by applying the Matroid Intersection Theorem [START_REF] Edmonds | Matroid intersection[END_REF] to the matroids M and M ′ .

Observe that the same approach used in the previous theorem does not work when the values of u can differ inside the same clique. For instance, suppose that D 1 is the complete digraph on edges {e 1 , . . . , e 4 } and that u(e 1 ) = 1 and u(e i ) = 2 for every i ∈ {2, 3, 4}. Then S 1 = {e 1 , e 2 } and S 2 = {e 2 , e 3 , e 4 } are acceptable subsets within a solution, however because of e 1 , there does not exist e ∈ S 2 \ S 1 such that S 1 ∪ {e} is an acceptable subset. This means that the augmentation property (cf. Section 2) is not satisfied and the subsets that define feasible solutions do not form a matroid.

Exponential exact algorithm

In this section, we present an exponential exact algorithm for G-DCST(G, D, ℓ, u), as states result (c). Recall that, as a consequence of Theorem 3 in [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF] for the optimization problems L-DCMST and A-DCMST, we get that the optimization problem G-DCMST(G, D, ℓ, u, w) is W[2]hard when parameterized by n = |V (G)|. The importance of the algorithm below, despite its simplicity, is that it separates the complexity of the feasibility and the optimization problems. Proof. It suffices to observe that, given a subset S ⊆ E(G), one can test in time O(n + m) whether S forms a spanning tree of G, and whether the constraints imposed by D, ℓ, u are satisfied by S. Because there are 2 m possible subsets to be tested, the theorem follows.

Modeling other constrained problems

As discussed in the introduction, the spanning tree problem has been investigated under the most various constraints. In this section, we show that some of them can be modeled as special cases of our problem. We have already remarked that this is the case for the Conflict Constrained Spanning Tree problem. One should also notice that, in all the reductions presented below, when the feasibility version reduces to our problem, so does the optimization version. It is a matter of observing that the graph in the source instance is a subgraph of the graph in the G-DCST instance, and that the reduction preserves the solution value when keeping the weights of the initial edges and setting to zero the weights of the new edges.

In Subsection 5.1, we present a reduction from Forcing CST (denoted by FCST), in Subsection 5.2, a reduction from Maximum Degree CST (denoted by MDST), and in Section 5.3, from Minimum Degree CST and Fixed-Leaves Minimum Degree CST (denoted by mDST and FmDST, respectively).

Forcing constrained spanning trees

Recall that, given graphs G and D such that V (D) = E(G), FCST consists in deciding whether G has a spanning tree T such that |E(T ) ∩ {e, f }| ≥ 1 for every ef ∈ E(D). Proof. Let (G, D) be an instance of FCST, and construct G ′ , D ′ as follows (cf. Figure 4). Choose any v ∈ V (G), and let G ′ be obtained from G by adding, for each ee ′ ∈ E(D), a pendant degree one vertex in v; denote the new edge by p ee ′ . Then, let D ′ be the digraph with vertex set E(G ′ ) and arcs (e, p ee ′ ) and (e ′ , p ee ′ ) for every ee ′ ∈ E(D). Finally, let ℓ(e) = 0 if e ∈ E(G), and ℓ(e) = 1 otherwise. We prove that (G, D) is a yes-instance of FCST if and only (G, D, ℓ, 2) is a yes-instance of G-DCST.

First, let T be a solution for FCST, and let T ′ be obtained from T by adding p ee ′ for every ee ′ ∈ E(D). Clearly T ′ is a spanning tree of G ′ , and since |E(T ) ∩ {e, e ′ }| ≥ 1 for every ee ′ ∈ E(D), we get that |E(T ′ ) ∩ dep D ′ (p ee ′ ) | ≥ 1. The reverse implication can be proved similarly.

Max-degree constrained spanning trees

Given a graph G = (V, E) and a positive integer k, recall that in the MDST(G, k) problem we want to find a spanning tree T such that d T (v) ≤ k, for every v ∈ V (G). We prove that a generalized version of this problem reduces to ours. In MDST(G, d * ), instead of being given an integer k, we are given a function d * : V (G) → N that separately sets upper bounds to the degrees of the vertices. Proof. Let (G, d * ) be an instance of MDST. We build an equivalent instance (G ′ , D, 0, u) of G-DCST as follows (cf. Figure 5).

• G ′ = (V ∪ V ′ , E ∪ E ′ )
, where V ′ = {v ′ | v ∈ V } has a copy of each vertex, and

E ′ = {vv ′ | v ∈ V } connects each vertex v ∈ V to its copy v ′ ∈ V ′ . • D = (E ∪ E ′ , A)
, where A = {(uv, uu ′ ), (uv, vv ′ ) | uv ∈ E}.

• u(e) = 0, for each e ∈ E, while u(vv ′ ) = d * (v), for each v ∈ V .

Observe that dep(vv ′ ) is the set of edges incident to v in G for every v ∈ V , and that dep(e) = ∅ for every e ∈ E. Also, note that because ℓ(e) = u(e) = 0 = |dep(e)| for every e ∈ E, and ℓ(e) = 0 for every e ∈ E ′ , the only real constraints being imposed by D are upper bounds on the chosen dependencies for edges in E ′ . More specifically, we get that a spanning tree

T ′ of G ′ (ℓ, u)-satisfies D if and only if |E(T ′ ) ∩ dep(vv ′ )| ≤ d * (v) for every vv ′ ∈ E ′ ∩ E(T ′ ).
Note that each v ′ has degree one in G ′ , which implies that every edge in E ′ must be part of every spanning tree of G ′ . Thus, we get that (V, E T ) ⊆ G is a tree that satisfies the maximum degree constraints if and only if

(V ∪ V ′ , E T ∪ E ′ ) (ℓ, u)-satisfies D. u v u ′ v ′ (a) G ′ . uv uu ′ vv ′ (b) D.

Minimum degree constrained spanning trees

Given a graph G and a positive integer k, recall that the mDST(G, k) problem consists in finding a spanning tree T of G such that d T (v) ≥ k for every nonleaf vertex v ∈ V (T ). We introduce a generalized version of this problem, denoted by G-mDST(G, ℓ, u), where we replace the integer k by functions ℓ, u : V → N and require that each nonleaf vertex

v of T satisfies ℓ(v) ≤ d T (v) ≤ u(v). Clearly, mDST(G, k) is a special case of G-mDST(G, ℓ, u) where ℓ(v) = k and u(v) = d(v) for every v ∈ V (G).
Theorem 10. G-mDST P G-DCST.

Proof. Given an instance (G = (V, E), ℓ, u) of G-mDST, we build an instance (G ′ , D, ℓ ′ , u ′ ) of G-DCST as follows (cf. Figure 6):

• G ′ = (V ∪ V ′ , E ∪ E ′ ), where V ′ = {v 1 , v 2 , v 3 | v ∈ V } and E ′ = {vv 1 , vv 2 , v 1 v 3 , v 2 v 3 | v ∈ V }; • D = (E ∪ E ′ , A 1 ∪ A 2 ), where A 1 = {(uv, vv 1 ), (uv, vv 2 ) | uv ∈ E} and A 2 = {(v 2 v 3 , v 1 v 3 ), (v 1 v 3 , v 2 v 3 ) | v ∈ V };
• For each e ∈ E, let ℓ ′ (e) = u ′ (e) = 0; and for each v ∈ V , let ℓ ′ (vv 1 ) = ℓ(v), u ′ (vv 1 ) = u(v), and ℓ ′ (e) = u ′ (e) = 1, for each e ∈ {vv 2 , v 1 v 3 , v 2 v 3 }.

Observe that, for each v ∈ V and i ∈ {1, 2}, we have that dep(vv i ) is the set of edges incident to v in G. We show that (G, ℓ, u) is a yes-instance of G-mDST if and only (G ′ , D, ℓ ′ , u ′ ) is a yes-instance of G-DCST.

First, let T = (V, E T ) be a solution for G-mDST(G, ℓ, u). We expand

T into T ′ = (V ∪ V ′ , E T ′ ) ⊆ G ′
, where E T ′ is equal to E T together with the following edges. For each v ∈ V , add v 1 v 3 and v 2 v 3 , and if v is a leaf in T then add vv 2 , otherwise add vv 1 . Observe that T ′ is a spanning tree of G ′ such that T = T ′ [V ]. It remains to show that the D-dependencies are satisfied. Every edge e ∈ E T has dep(e) = ∅ and ℓ ′ (e) = u ′ (e) = 0, so ℓ ′ (e) ≤ |dep(e) ∩ E(T ′ )| ≤ u ′ (e) trivially follows. The remaining types of edges in E T ′ \ E T are analyzed below: (i) v i v 3 , for v ∈ V and i ∈ {1, 2}: recall that v 1 v 3 is the unique dependency of v 2 v 3 , and vice-versa, and they are both in

u v v 1 v 2 v 3 u 1 u 2 u 3 (a) G ′ . uv uu 1 uu 2 vv 1 vv 2 u 1 u 3 u 2 u 3 v 1 v 3 v 2 v 3 (b) D.
T ′ . Hence 1 = ℓ ′ (v i v) ≤ |dep(v i v) ∩ E(T ′ )| ≤ u ′ (v i v) = 1.
(ii) vv 2 : by construction of T ′ , we get that v is necessarily a leaf in T . Since exactly one edge of dep(vv 2 ) is in E T ′ , namely the edge incident to v in T , we have that

1 = ℓ ′ (vv 2 ) ≤ |dep(vv 2 ) ∩ E(T ′ )| ≤ u ′ (vv 2 ) = 1.
(iii) vv 1 : by construction of T ′ , we get that v in T is not a leaf in T . From the feasibility of T , we know that ℓ

(v) ≤ d T (v) ≤ u(v), i.e., at least ℓ(v) and at most u(v) edges of dep(e v 1 ) are in E T ⊆ E T ′ , which implies that ℓ(v) = ℓ ′ (vv 1 ) ≤ |dep(vv 1 ) ∩ E(T ′ )| ≤ u ′ (vv 1 ) = u(v). Conversely, suppose that T ′ = (V ∪ V ′ , E T ′ ) is a solution for G-DCST(G ′ , D, ℓ ′ , u ′ ). We show that T = T ′ [V ] is a solution for G-mDST(G, ℓ, u).
Due to the dependency constraints, we get that v 1 v 3 and v 2 v 3 are in T ′ , for each v ∈ V . From this, and since vv 1 and vv 2 are a cut in G ′ , exactly one of vv 1 and vv 2 is in T ′ , for each v ∈ V . Take v ∈ V . If vv 1 is in T ′ , then there are at least ℓ(v) and at most u(v) edges incident to v in T ′ . And if vv 2 is in T ′ , then there is exactly one edge uv ∈ E in E T ′ . Therefore, either ℓ(v) ≤ d T (v) ≤ u(v) or d T (v) = 1. Since T ′ is a spanning tree of G ′ , T is a spanning tree of G, and thus T is a solution of GD-MST(G, ℓ, u, w).

Finally, given a graph G, a subset C ⊆ V , and a function ℓ : C → Z + , recall that FmDST(G, C, ℓ) denotes the problem of finding a spanning tree T of G such that d T (u) ≥ ℓ(u) for every u ∈ C, and d T (v) = 1 for every v ∈ V \ C (i.e., the set of leaves is prefixed). Observe that the same reduction of Theorem 10 can be applied to this problem by removing edge e v 2 for each v ∈ C, and edge e v 1 for each v ∈ V \ C. We then get the following: Theorem 11. FmDST P G-DCST.

Conclusion

In this paper, we investigated a dependency constrained spanning tree problem that generalizes many previously studied spanning tree problems with local constraints, as for instance degree constraints. We then inherit all of the NP-completeness results for these problems, as well as polynomial results and practical approaches to our problem will therefore hold for these other problems. Interestingly, there are other spanning tree problems that impose global constraints on the tree, as for instance, a bound on the diameter of the produced tree [START_REF] Camerini | Complexity of spanning tree problems: Part I[END_REF][START_REF] Camerini | On the complexity of finding multi-constrained spanning trees[END_REF], or on the number of leaves [START_REF] Garey | Computers and intractability[END_REF][START_REF] Lu | The power of local optimization: Approximation algorithms for maximum-leaf spanning tree[END_REF]. A good question therefore is whether problems with this kind of constraints can be modeled within our framework. Concerning positive results, we have proved that G-DCST(G, D, dep, dep) can be solved in polynomial time when D is an oriented matching. We ask whether this also holds for the optimization problem (recall that G-DCMST(G, D, 0, 0) is polynomial in this case [START_REF] Darmann | Minimum spanning trees with conflict graphs[END_REF]). The latter result is important in the face of the fact that, as a byproduct of a result in [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF], we get that no algorithm running in time 2 O(n) exists for the optimization problem, unless ETH fails. Also, the results presented in Section 3.1 imply that no algorithm that runs in time 2 o(n+m) exists for the feasibility problem under the ETH, which means that the algorithm presented in Section 4.3 is asymptotically optimal. We mention that our algorithm can also be seen as an FPT algorithm parameterized by m. We ask whether the problem is FPT under other parameters. In order to identify parameters for the above question, note that the maximum degree of the input graph G is not enough, since a particular case of the problem is already NPcomplete restricted to graphs with maximum degree at most three [START_REF] Luiz | Two dependency constrained spanning tree problems[END_REF]. Similarly, the maximum degree of the dependency graph D is not enough either, as another particular case of the problem is NP-complete even if D is a forest of paths of length at most two (see e.g. [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], as well as our results presented in Section 3.1).

A promising candidate parameter for obtaining FPT algorithms is the treewidth of the input graph G (see [START_REF] Cygan | Parameterized Algorithms[END_REF] for the definition); note that the treewidth of the underlying graph of D is not enough by the last sentence of the above paragraph, since forests have treewidth one. Suppose that, in order to use Courcelle's Theorem [START_REF] Courcelle | The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs[END_REF] or any of its optimization variants [START_REF] Arnborg | Easy problems for treedecomposable graphs[END_REF], one tries to express the G-DCST problem in monadic second-order (MSO) logic. In order to guarantee that the dependencies of D are satisfied for every edge e of the desired spanning tree of the input graph G, one would probably need to evaluate the functions ℓ(e) and u(e) inside the eventual MSO formula, and this seems to be a fundamental hurdle since these values are a priori unrelated to the treewidth of G. Nevertheless, for the particular case of G-DCST (or G-DCMST) where both functions ℓ and u are constants (or even equal to some constant value that depends on the treewidth of G), it is indeed possible, using standard techniques, to write such an MSO formula expressing the problem, and therefore it is FPT parameterized by the treewidth of the input graph. Note that this restriction of the G-DCST problem is NP-complete by Corollary 2, for every pair of positive integers ℓ, u with ℓ ≤ u. The next natural step would be to consider as parameters both the treewidth of G and the maximum degree of D.

  (i) ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G), D is a forest of oriented paths of length at most two where all components are directed paths, out-stars, or in-stars, and G is an outerplanar chordal graph with diameter at most two. Furthermore, this problem cannot be solved in time 2 o(n+m) unless the ETH fails, where n = |V (G)| and m = |E(G)|;

  (a) G-DCST can be solved in polynomial time when D is an oriented matching, and ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G); (b) G-DCMST can be solved in polynomial time when ℓ = 0, D is a collection of symmetric complete digraphs D 1 , . . . , D k , and u(e) = u(e ′ ) whenever e, e ′ are within the same component of D; (c) G-DCST can be solved in time O(2 m • (n + m)), where n = |V (G)| and m = |E(G)|.

Theorem 1 .

 1 G-DCST(G, D, ℓ, u) is NP-complete, even when ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G), D is a forest of out-stars of maximum degree two, and G is an outerplanar chordal graph with diameter at most two. Furthermore, this problem cannot be solved in time 2 o(n+m) unless the ETH fails, where n = |V (G)| and m = |E(G)|.

Figure 1 :

 1 Figure 1: Illustration of the reduction from (3, 2, 2)-SAT in Theorem 1.In Figure1(a), we represent a variable gadget together with a gadget of a clause containing three literals. In Figure1(b), for a variable x, we represent the dependency between v x v x and vw x , and also the arcs leaving vv x and vv x when x appears positively in c 1 and c 2 , and negatively in c 3 , being related to the first literal in each of these clauses.

Theorem 2 .

 2 G-DCST(G, D, ℓ, u) is NP-complete, even when ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G), D is a union of directed paths with length at most two, and G is a chordal outerplanar graph with diameter two. Furthermore, this problem cannot be solved in time 2 o(n+m) unless the ETH fails, where n = |V (G)| and m = |E(G)|.

  c) Digraph D (variable and literal gadgets).

Figure 2 :

 2 Figure 2: Illustration of the reduction from (3, 2, 2)-SAT used in Theorem 3.

Theorem 3 .

 3 G-DCST(G, D, ℓ, u) is NP-complete, even when ℓ(e) = u(e) = |dep(e)| for every e ∈ E(G), D is a forest of in-stars of maximum in-degree two, and G is an outerplanar chordal graph with diameter at most two. Furthermore, this problem cannot be solved in time 2 o(n+m) unless the ETH fails, where n = |V (G)| and m = |E(G)|.

Lemma 1 .

 1 Let c, ℓ, u be positive integers with u ≥ ℓ. Then, instances (G, D, ℓ, u) and (G ′ , D ′ , ℓ + c, u + c) of G-DCST are equivalent.

  G), because at least ℓ and at most u dependencies of e are in T , and because E(T ′ ) ∩ dep D ′ (e) = (E(T ) ∩ dep D (e)) ∪ {e 1 , . . . , e c }, we get that at least ℓ + c and at most u + c dependencies of e are in T ′ . And if e ∈ {e 1 , . . . , e ℓ+c+1 }, we get that E(T ′ ) ∩ dep D ′ (e) = {e 1 , . . . , e ℓ+c+1 } \ {e} and again the constraints hold. On the other hand, let T ′ be a spanning tree of G ′ ; we know that {e 1 , . . . , e ℓ+c+1 } ⊆ E(T ′ ). Let T be obtained from T ′ by removing these edges, and consider e ∈ E(G). It follows that |dep D (e) ∩ E(T )| = |(dep D ′ (e) ∩ E(T ′ )) \ {e 1 , . . . , e c }| = |dep D ′ (e) ∩ E(T ′ )|c, and since ℓ + c ≤ |dep D ′ (e) ∩ E(T ′ )| ≤ u + c we get that T (ℓ, u)-satisfies D.

Theorem 4 .

 4 Let c be a positive integer. Then G-DCST(G, D, 0, c) is NP-complete.

  1 e , . . . , pp c e } and therefore 0 ≤ |E(T ′ ) ∩ dep D ′ (e)| = c. And if e ∈ E ′ , we have that dep D ′ (e) = ∅ and trivially 0 = |dep D ′ (e) ∩ E(T ′ )| ≤ c.

Corollary 2 .

 2 Therefore, since |E(T ′ ) ∩ dep D ′ (e)| ≤ c and {pp 1 c , . . . , pp c e } ⊆ E(T ′ ) ∩ dep D ′ (e), we get that E(T ′ ) ∩ (E(G) \ E ′ ) = ∅, i.e., |E(T ) ∩ dep D (e)| = 0, as we wanted to show. Combining Lemma 1 and Theorem 4, we get result (ii), that is, G-DCST(G, D, ℓ, u) is NP-complete for every combination of constant values ℓ and u. For every pair of positive integers ℓ, u with ℓ ≤ u, we have that G-DCST(G, D, ℓ, u) is NP-complete. Proof. Let c = uℓ. By Theorem 4, we have that G-DCST(G, D, 0, c) is NP-complete, and by Lemma 1, we have that G-DCST(G, D, ℓ, c + ℓ = u) also is.As we have already mentioned, if u(e) = |dep(e)| for every e ∈ E(G), then G-DCST(G, D, 0, u) is easy since any spanning tree (0, u)-satisfies D. Hence, it is natural to ask whether the problem continues to be easy when u(e) is just slightly smaller than |dep(e)|. The following corollary is trivially obtained from previous results. It answers the

e 1 e 2 (

 2 b) Gc.

Figure 3 :

 3 Figure 3: Illustration of the reduction for CCMST.

Lemma 2 .

 2 Let G = (V, E) be a graph, D = (E, A) be a digraph, before, and ℓ, u be such that ℓ(e) = u(e) = |dep(e)| ∈ {0, 1} for every e ∈ E(G). If there exists S ′ ⊆ S such that H(S ′ ) is a spanning tree of H and (V, dep(S ′ )) is acyclic, then G-DCST(G, D, ℓ, u) is feasible. Conversely, any feasible solution of G-DCST(G, D, ℓ, u) contains such a subset S ′ .

Theorem 7 .

 7 G-DCST(G, D, ℓ, u) can be solved in time O(2 m • (n + m)), where n = |V (G)| and m = |E(G)|.

Theorem 8 .

 8 Denote by G-DCST * the problem G-DCST restricted to instances (G ′ , D ′ , ℓ, 2) such that ℓ(e) ∈ {0, 1} for every e ∈ E(G ′ ) and ∆ -(D ′ ) = 2. Then, FCST P G-DCST * .

Figure 4 :

 4 Figure 4: Illustration of the reduction for FCST.

Theorem 9 .

 9 Denote by G-DCST * * the problem G-DCST restricted to instances (G, D, 0, u). Then, MDST P G-DCST * * .

Figure 5 :

 5 Figure 5: Illustration of the reduction for MDST.

Figure 6 :

 6 Figure 6: Illustration of the reduction for G-mDST.

Question 1 .

 1 Can instances of CST problems with global constraints be modeled as G-DCST instances?Concerning NP-completeness results, we have investigated the problem under restrictions on the dependency digraph D, and on the lower and upper bound functions ℓ and u. Among other restrictions, we have proved that G-DCST is NP-complete when D is either a forest of directed paths, a forest of out-stars, or a forest of in-stars, and each component has at most three vertices. In the first two cases, we have considered all possible values for constant functions ℓ, u. The following cases for in-stars remain open.Question 2. What is the complexity of G-DCST(G, D, ℓ, u) when D is a forest of in-stars with at most three vertices and (ℓ, u) = (0, 1) or, for every e ∈ E(G) such that dep(e) = ∅, ℓ(e) = 1 and u(e) ∈ {1, 2}?

Question 3 .

 3 What is the complexity of G-DCMST(G, D, dep, dep) when D is an oriented matching? Finally, we have proved that G-DCMST can be solved in polynomial time when ℓ = 0, D is a collection of symmetric graphs D 1 , . . . , D k , and u(e) = u(e ′ ) whenever e, e ′ are within the same component, and that G-DCST(G, D, ℓ, u) can be solved in time O(2 m • (n + m)) by a naive brute-force algorithm, where n = |V (G)| and m = |E(G)|.

Question 4 .

 4 Under which parameters is G-DCST or G-DCMST FPT?

We can always assume that 0 ≤ ℓ(e) ≤ u(e) ≤ |dep(e)|, and so ℓ(e) = u(e) = 0 if dep(e) = ∅.

This means that ℓ(e) = k and u(e) = k ′ ≥ k, for all e ∈ E(G) such that dep(e) = ∅, and ℓ(e) = u(e) = 0 if dep(e) = ∅.

Conflict constraints: Recall that, in the Conflict Constrained (Minimum) Spanning Tree problem, we are given a pair of graphs G and D such that V (D) = E(G), and we want to know whether there exists a spanning tree (find a minimum spanning tree) T of G such that E(T ) ∩ dep(e) = ∅ for every e ∈ E(T ). We denote the feasibility problem by CCST and the optimization problem by CCMST. Note that, if we consider D ′ as an arbitrary orientation of D (i.e., each edge e 1 e 2 in D gives rise to either (e 1 , e 2 ) or (e 2 , e 1 ) in D ′ ), then we get that such a tree exists if and only if there exists a spanning tree T that (0, 0)satisfies D ′ . This means that our problem generalizes this one and therefore inherits the NP-complete results, as well as might help with some polynomial cases. Also, observe that the problems related to results (ii) when ℓ = 0, (iii) and (b) can be seen as generalizations of the conflict constrained problems in the sense that ℓ = 0 (i.e., no lower bound constraint is imposed), but u = 0.

Problems CCST and CCMST have been introduced in [START_REF] Darmann | Paths, trees and matchings under disjunctive constraints[END_REF], where CCMST is proved to be polynomial-time solvable if the conflict graph is a matching, and CCST is proved to be NPcomplete if the conflict graph is a forest of paths of length at most two. From what is said previously, we then get that G-DCMST(G, D, 0, 0, w) is polynomial when D is an oriented matching, and G-DCST(G, D, 0, 0) is NP-complete when D is an orientation of a forest of paths of length at most two. When D is one of these digraphs, observe that ∆ The CCST and CCMST problems have also been investigated in [START_REF] Zhang | The minimum spanning tree problem with conflict constraints and its variations[END_REF], where the authors prove that, if the input graph G is a cactus, then CCST is polynomial, while CCMST is still NP-hard. They further show that the optimization problem is polynomial if the conflict graph D can be turned into a collection of cliques by the removal of a constant number of vertices, i.e., there exists a subset E ′ ⊆ E(G) = V (D) such that D -E ′ is a collection of cliques, and |E ′ | is bounded by a constant. We prove something similar here for the generalized problem (result (b)).

In [START_REF] Mamadou | Trees in graphs with conflict edges or forbidden transitions[END_REF], the authors investigate a conflict constrained problem where the conflict graph is only allowed to contain an edge ee ′ if e and e ′ share an endpoint in G (they called these forbidden transitions). Among other results, they prove that the feasibility problem is NP-complete even if the input graph G is a complete graph. Practical approaches to the conflict constrained problem have been presented in [START_REF] Carrabs | Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach[END_REF][START_REF] Samer | A branch and cut algorithm for minimum spanning trees under conflict constraints[END_REF][START_REF] Zhang | The minimum spanning tree problem with conflict constraints and its variations[END_REF].

Another interesting, recently defined, problem that can be modeled as a conflict con-