The unilateral 2-linkage problem

We study a new variant of the classical linkage problem for digraphs, which we call { unilateral linkages.} A digraph D is { unilaterally k-linked} if it satisfies that for every choice of $2k$ distinct vertices s₁,s₂,…,sₖ,t₁,t₂,…,tₖ there are vertex disjoint directed paths P₁,…,Pₖ in D such that Pᵢ is either an (sᵢ,tᵢ)-path or a (tᵢ,sᵢ)-path for each i∈ [k]. This is a relaxation of the property of D being k-linked, where we insist that each Pᵢ must go from sᵢ to tᵢ. Clearly every k-linked digraph is also unilaterally k-linked. It is easy to see that the unilateral linkage problem is NP-complete for general digraphs and that it is trivial for semicomplete digraphs (digraphs with no pair of non-adjacent vertices). We show how Thomassen's construction of highly connected digraphs which are not 2-linked can be modified to show that there is no connectivity which guarantees that a digraph is unilaterally 2-linked. We show that every 4-strong split digraph and every 5-strong semicomplete multipartite digraph is unilaterally 2-linked. Both bounds are best possible. A digraph is { co-bipartite} if its vertex set can be covered by two induced semicomplete digraphs. We prove that every 6-strong co-bipartite digraph is unilaterally 2-linked. Here we do not know whether the correct answer is 5. We also prove that every 16-strong digraph with independence number at most 2 is unilaterally 2-linked.