A network N is formed by a (multi)digraph D together with a capacity function u : A ( D ) → R + , and it is denoted by N = ( D , u ) . A flow on N is a function x : A ( D ) → R + such that x ( a ) ≤ u ( a ) for all a ∈ A ( D ), and it is said to be k -splittable if it can be decomposed into up to k paths. We say that a flow is λ -uniform if its value on each arc of the network with positive flow value is exactly λ , for some λ ∈ R + * . We consider the problem of decomposing a flow over an arc-coloured network with minimum cost, that is, with minimum sum of the cost of its paths, where the cost of each path is given by its number of colours. We show that this problem is NP -Hard for general flows on networks. When we restrict the problem to λ -uniform flows, we show that it can be solved in polynomial time for networks with at most two colours. Moreover, we prove that it is NP -Hard for general networks with three colours and for acyclic networks with at least five colours.

In this work, for a given oriented graph D, we study its interval and hull numbers, denoted by ⃗in (D) and ⃗hn (D), respectively, in the oriented geodetic, ⃗P3 and ⃗P*3 convexities. This last one, we believe to be formally defined and first studied in this paper, although its undirected version is well-known in the literature. Concerning bounds, for a strongly oriented graph D and the oriented geodetic convexity, we prove that ⃗hn g(D) ≤ m(D)-n(D) + 2 and that there is at least one such that ⃗hn g(D) = m(D) - n(D). We also determine exact values for the hull numbers in these three convexities for tournaments, which imply polynomial-time algorithms to compute them. These results allow us to deduce polynomial-time algorithms to compute ⃗hn P3 (D) when the underlying graph of D is split or cobipartite. Moreover, we provide a meta-theorem by proving that if deciding whether ⃗ing(D) ≤ k or ⃗hn g(D) ≤ k is NP-hard or W[i]-hard parameterized by k, for some i ϵ Z*+, then the same holds even if the underlying graph of D is bipartite. Next, we prove that deciding whether ⃗hn P3 (D) ≤ k or ⃗hn P3* (D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is bipartite; that deciding whether ⃗in P3(D) ≤ k or whether ⃗in P3*(D) ≤ k is NP-complete, and the same for ⃗hn P3*(D) ≤ k even if D has no directed cycles and the underlying graph of D is a chordal bipartite graph; and that deciding whether ⃗in P3(D) ≤ k or whether ⃗in P3*(D) ≤ k is W[2]-hard parameterized by k, even if the underlying graph of D is split. Finally, we also argue that the interval and hull numbers in the ⃗P3 and ⃗P*3 convexities can be computed in polynomial time for directed graphs with underlying graph of bounded tree-width by using Courcelle's theorem.

The grid theorem of Robertson and Seymour [ J. Combin. Theory Ser. B, 41 (1986), pp. 92--114] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the grid theorem in digraphs was conjectured by Johnson et al. [ J. Combin. Theory Ser. B, 82 (2001), pp. 138--154] and proved by Kawarabayashi and Kreutzer [ Proceedings of STOC, 2015, pp. 655--664]. Namely, they showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor, and stated that their proof can be turned into an \sf XP algorithm, with parameter $k$, that either constructs a decomposition of the appropriate width or finds the claimed large cylindrical grid as a butterfly minor. In this paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this \sf XP algorithm into a fixed-parameter tractable (\sf FPT) algorithm. Toward this, our main technical contributions are two \sf FPT algorithms with parameter $k$. The first one either produces an arboreal decomposition of width $3k-2$ or finds a haven of order $k$ in a digraph $D$, improving on the original result for arboreal decompositions by Johnson et al. [ J. Combin. Theory Ser. B, 82 (2001), pp. 138--154]. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices $T$ in \sf FPT time with parameter $|T|$, a result that we consider to be of its own interest.

A target set selection model is a graph G with a threshold function τ : V(G) → N upper-bounded by the vertex degree. For a given model, a set S0 ⊆ V(G) is a target set if V(G) can be partitioned into non-empty subsets S0, S1,....,St such that, for all i∈{1,....,t}, Si contains exactly every vertex v having at least τ(v) neighbors in S0∪⋯∪Si−1. We say that t is the activation time tτ(S0) of the target set S0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set S0 that maximizes tτ(S0). That is, given a graph G, a threshold function τ in G, and an integer k, the objective of the TSS-time problem is to decide whether G contains a target set S0 such that tτ(S0)≥k. Let τ*=maxV∈V(G)τ(v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C: if C has bounded local treewidth, the problem is FPT parameterized by k and τ*; otherwise, it is NP-complete even for fixed k = 4 and τ* = 2. We also prove that, with τ = 2, the problem is NP-hard in bipartite graphs for fixed k = 5, and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S0 in a given tree maximizing tτ(S0).

For two positive integers k and $$\ell $$ ℓ , a $$(k \times \ell )$$ ( k × ℓ ) -spindle is the union of k pairwise internally vertex-disjoint directed paths with $$\ell $$ ℓ arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $$\ell \ge 1$$ ℓ ≥ 1 , finding the largest k such that an input digraph G contains a subdivision of a $$(k \times \ell )$$ ( k × ℓ ) -spindle is polynomial-time solvable if $$\ell \le 3$$ ℓ ≤ 3 , and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.