# Disjoint $X$-paths in bidirected graphs

Source: [Disjoint $X$-paths in bidirected graphs](<https://www.sota2.com/research/paper/68fa5d161e209131ce9d6f4c>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T05:37:13.274Z

Authors: Jana K. Nickel

Published: 2025-02-27T07:14:31.000Z

## Abstract

Let $B$ be a bidirected multigraph with signing $\\sigma$, 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$, $\\sigma(v,e)=-$ or $v\\in T\\setminus S$, $\\sigma(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\\lvert S\\cap T \\right\\rvert +\\sum \\lfloor \\tfrac{1}{2} \\left\\lvert V(C)\\cap (X\\cup S\\cup T) \\right\\rvert \\rfloor \\geq 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\\H{o}s-P\\'osa property for $X$-paths in bidirected multigraphs.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2502.19835>)

[PDF](<https://arxiv.org/pdf/2502.19835.pdf>)
