Disjoint $X$-paths in bidirected graphs

Abstract

Let $B$ be a bidirected multigraph with signing $\ddot{I}ƒ$, let $X$ be a set of vertices in $B$, and let $k$ be a non-negative integer. For any pair of vertex sets $S,T\subset V(B)$ satisfying $X\cap S=X\cap T$, we denote by $B_{S,T}$ the multigraph with the same vertex set as $B$ and with edge set consisting of those edges $e$ of $B$ each of whose endvertices $v$ satisfies $v\notin S\cup T$ or $v\in S\setminus T$, $\ddot{I}ƒ(v,e)=-$ or $v\in T\setminus S$, $\ddot{I}ƒ(v,e)=+$. We prove that $B$ admits a set of $k$ pairwise disjoint $X$-paths if and only if for any $S,T\subseteq V(B)$ with $X\cap S=X\cap T$, the inequality $\left|S\cap T\right|+\sum \lfloor \frac{1}{2}\left|V(C)\cap (X\cup S\cup T)\right|\rfloor \ge k$ holds where the sum is indexed by the components of $B_{S,T}$. This result is a generalization of a result of Gallai from undirected graphs to bidirected ones. Furthermore, we will deduce from this a kind of an Erdős-Pósa property for $X$-paths in bidirected multigraphs.