Directed Disjoint Paths in Restricted Digraph Classes

Definitions and mathematical statement

Let $k\geq 1$ be a fixed integer, rather than part of the variable input. Let $\mathcal C$ be a class of finite digraphs. An instance consists of a digraph $G=(V,A)\in\mathcal C$ and an ordered list of terminal pairs $(s_1,t_1),\ldots,(s_k,t_k)\in V\times V$. Here $A$ denotes the set of directed edges (arcs). A directed path from $s_i$ to $t_i$ follows arcs in their prescribed directions. Write $A(P)$ for the arcs used by a path $P$. The required feasibility condition is \[ \exists P_1,\ldots,P_k\quad \left[\text{each }P_i\text{ is a directed }s_i\text{--}t_i\text{ path}\right] \quad\text{and}\quad A(P_i)\cap A(P_j)=\varnothing\quad(1\leq i<j\leq k). \] Paths may share vertices; the disjointness requirement concerns arcs.

Classification question. Determine restricted digraph classes $\mathcal C$ for which, for every fixed positive integer $k$, there is an algorithm deciding this feasibility condition on all instances with $G\in\mathcal C$ in time polynomial in the input encoding length $L$. More explicitly, for each such $\mathcal C$ and fixed $k$, the desired algorithm has running time bounded by a polynomial $p_{\mathcal C,k}(L)$. No uniform polynomial bound independent of $k$ is requested.

Unresolved scope and conventions. The source does not specify a universe of candidate restricted classes or a criterion for a complete classification. It also does not specify whether digraphs are simple or may have parallel arcs or loops, whether terminal vertices must be distinct, or whether length-zero paths are permitted when $s_i=t_i$. These conventions must be fixed before obtaining a fully specified decision problem; no terminal-distinctness hypothesis is imposed here. The polynomial-time formulation above treats membership in $\mathcal C$ as an input promise; the source does not state whether recognition of $\mathcal C$ is also required.

Short English statement

For each fixed number $k$ of ordered terminal pairs, identify restricted classes of finite digraphs in which one can decide in polynomial time whether all pairs can be connected by directed paths sharing no arcs. Shared vertices are allowed. The intended range of graph classes and several graph and terminal conventions remain unspecified. The supplied record labels the question partially solved; this draft does not independently verify that assessment.

Sources

• Local UnsolvedMath registry: permanent ID $30001426$, title "Directed Disjoint Paths in Restricted Digraph Classes," exact source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. The supplied record gives proposed year 2010 and names no individual proposer.
• Supplied source citation: Graph Theory (2010), Oberwolfach Reports, pp. 521--580, DOI 10.4171/owr/2010/11. https://doi.org/10.4171/owr/2010/11. The supplied background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference: "Disjoint paths in tournaments, 2015." https://doi.org/10.1016/j.aim.2014.11.011.
• Supplied literature reference: "Oberwolfach Report 11/2010." https://doi.org/10.4171/owr/2010/11.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem partially solved and reports polynomial algorithms for several restricted digraph classes, including bounded independence number and semicomplete digraphs for fixed $k$, while describing the broader classification question as unresolved. This is supplied dated curation, not independently verified; the background expressly requests independent verification of time-sensitive status and cited claims.
• The supplied registry assigns statement status corrected_verified and reports that the mathematical content was checked against the official Oberwolfach report, with notation, context, and question form normalized without changing the source-level claim. This verification assertion is part of the supplied record and has not been independently checked here.