Abstract
The so-called weak-2-linkage problem asks for a given digraph (Formula presented.) and distinct vertices (Formula presented.) of (Formula presented.) whether (Formula presented.) has arc-disjoint paths (Formula presented.) so that (Formula presented.) is an (Formula presented.) -path for (Formula presented.). This problem is NP-complete for general digraphs but the first author showed that the problem is polynomially solvable and that all exceptions can be characterized when (Formula presented.) is a semicomplete digraph, that is, a digraph with no pair of nonadjacent vertices. In this paper we extend these results to paths which are both edge-disjoint and arc-disjoint in semicomplete mixed graphs, that is, a mixed graph (Formula presented.) in which every pair of distinct vertices has either an arc, an edge, or both an arc and an edge between them. We give a complete characterization of the negative instances and explain how this gives rise to a polynomial algorithm for the problem.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Journal of Graph Theory |
ISSN | 0364-9024 |
DOI | |
Status | E-pub ahead of print - 4. nov. 2024 |