The unilateral 2-linkage problem
Abstract
We study a new variant of the classical linkage problem for digraphs, which we call {\bf unilateral linkages.} A digraph D is {\bf unilaterally k-linked} if it satisfies that for every choice of 2k distinct vertices s1,s2,…,sk,t1,t2,…,tk there are vertex disjoint directed paths P1,…,Pk in D such that Pi is either an (si,ti)-path or a (ti,si)-path for each i∈ [k]. This is a relaxation of the property of D being k-linked, where we insist that each Pi must go from si to ti. 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 {\bf 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.
Related
- Noncommutative Hourglasses II 1/2: Derived Category of Birational Linkage with Well-Formed Singularities
- A nonlinear rod linkage model: zero-energy chains and continuum consistency
- Probabilistic linkage with graphs: leveraging cluster structure to improve the accuracy of entity resolution at scale
- Causal Record Linkage
- Gestational age and device-measured physical activity in adolescents and adults: A linkage of the HUNT Study and Medical Birth Registry
BibTeX
@misc{bangjensen2026unilateral,
title = {{The unilateral 2-linkage problem}},
author = {Jørgen Bang-Jensen and Xiaoying Chen and Panpan Cheng and Jin Yan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36895},
eprint = {2610.36895},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36895},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - The unilateral 2-linkage problem
AU - Jørgen Bang-Jensen
AU - Xiaoying Chen
AU - Panpan Cheng
AU - Jin Yan
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36895
UR - https://arxiv.org/abs/2610.36895
AB - We study a new variant of the classical linkage problem for digraphs, which we call {\bf unilateral linkages.} A digraph D is {\bf unilaterally k-linked} if it satisfies that for every choice of 2k distinct vertices s_1,s_2,…,s_k,t_1,t_2,…,t_k there are vertex disjoint directed paths P_1,…,P_k in D such that P_i is either an (s_i,t_i)-path or a (t_i,s_i)-path for each i∈ [k]. This is a relaxation of the property of D being k-linked, where we insist that each P_i must go from s_i to t_i. 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 {\bf 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.
ER -