Abstract. We prove that for every set [Formula: see text] of vertices of a directed graph [Formula: see text], the maximum number of vertices in [Formula: see text] contained in a collection of vertex-disjoint cycles in [Formula: see text] is at least the minimum size of a set of vertices that hits all cycles containing a vertex of [Formula: see text]. As a consequence, the directed tree-width of a directed graph is linearly bounded in its cycle-width, which improves the previously known quadratic upper bound. We further show that the corresponding statement in bidirected graphs is true and that its edge-variant holds in both undirected and directed graphs, but fails in bidirected graphs. The vertex-version in undirected graphs remains an open problem.

Abstract. We give an approximate Menger-type theorem for the case when a graph [Formula: see text] contains two [Formula: see text] paths [Formula: see text] and [Formula: see text] such that [Formula: see text] is an induced subgraph of [Formula: see text]. More generally, we prove that there exists a function [Formula: see text], such that for every graph [Formula: see text] and [Formula: see text], either there exist two [Formula: see text] paths [Formula: see text] and [Formula: see text] such that the distance between [Formula: see text] and [Formula: see text] is at least [Formula: see text], or there exists [Formula: see text] such that the ball of radius [Formula: see text] centered at [Formula: see text] intersects every [Formula: see text] path.